Apresentação do gvpr

Ricardo Andrade Dalla Bernardina

DOT [1] é uma linguagem que permite definir grafos [2]. Ela foi usada inicialmente no programa de mesmo nome dot, hoje parte do pacote graphviz [3], que tem muitas ferramentas para visualização e manipulação de grafos.

Um exemplo de arquivo para construção de grafos é explicado aqui. A primeira coisa que deve ser feita é dar uma nome para o grafo, e depois de escolhido (supondo que seja g para o exemplo ) colocar:

    graph g {}

Tudo que virá depois no arquivo estará dentro das chaves após graph g.

Após isso é necessário criar os nós e para isso escrevemos:
X [label="node"]; -- sendo X o identificador do nó e node o nome do nó.

Podem ser incluídos tantos nós quanto forem necessários.

Após isso, para se colocar as arestas deve-se escrever os identificadores dos nós que estão ligados pela aresta (não está sendo considerado grafo dirigido) e entre eles colocar "--"; isto é: dois hífens seguidos. Por ex.: X -- Y; é a aresta que conecta os nós X e Y.

Após isso é só salvar o arquivo, rodar um programa de visualização como o dot [4] e o grafo estará pronto -- por exemplo, na forma de uma imagem JPEG.

Abaixo encontra-se uma figura do código [5]:


No pacote graphviz encontra-se a ferramenta gvpr [6], muito poderosa, mas pouco conhecida, que permite manipular e -- de forma geral -- reescrever grafos.

Agora será mostrada uma pequena apresentação do programa descstat.g [7], que usa a ferramenta gvpr para calcular o maior grau e menor grau de um grafo qualquer, além de calcular a média, variância, desvio padrão e coeficiente de variação dos graus dos nós dos grafos.

Antes de tudo vale lembrar que o gvpr só interpreta grafos na linguagem DOT, sendo inútil para outras linguagens de definição de grafos. No ambiente gvpr, é definida uma linguagem de programação, que possui os seguintes elementos

• BEGIN, que é realizado apenas uma vez no começo da programa;


• END que é realizado apenas no final do programa e uma única vez também;


• existe também o BEG_G, que é realizado para todos os grafos no começo de cada um;


• e o END_G, que do mesmo modo é realizado para todos os grafos, só que no final deles;


• por último tem o N que entra em todos os nós do grafo.

BEG_G e END_G devem estar entre BEGIN e END. Por sua vez, N deve estar entre BEG_G e END_G. A sintaxe de comandos e declarações é bastante similar, quando não igual, àquela do C [8].

Assim no programa descstat.g foram declaradas as variáveis no BEGIN, os valores delas foram inicializados no BEG_G, pois eles devem ser reinicializados no início de cada grafo. Dentro do N são totalizados os graus de todos os nós de cada grafo. O grau de um nó é obtido pela expressão $.degree, onde $ significa o nó atual e degree é o grau do nó. Por sua vez, $G significa o grafo atual. Esses graus são necessários para os cálculos que são o objetivo do programa. Todos eles são finalizados no END_G, que também apresenta os valores na tela. O trecho em N é apresentado a seguir:

N {
    if ($.degree > maxd) {
        maxd = $.degree;
    }

    if ($.degree < mind) {
        mind = $.degree;
    }

    mean += $.degree;
    var  += $.degree * $.degree;
}

Referências

[1] The DOT Language
Acessado em 29/01/2010

[2] Teoria dos grafos
Acessado em 29/01/2010

[3] Graphviz - Graph Visualization Software
Acessado em 29/01/2010

[4] Drawing graphs with dot
Acessado em 02/02/2010

[5] 4.dot
Acessado em 29/01/2010

[6] gvpr(1) - Linux man page
Acessado em 29/01/2010

[7] descstat.g
Acessado em 02/02/201

[8] C (linguagem de programação)
Acessado em 02/02/2010