Apresentação do gvpr

by

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]:
41.jpg

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

Anúncios

Uma resposta to “Apresentação do gvpr”

  1. Conectividade de redes mesh « Tecnologias sem Fio Says:

    […] Apresentação do gvprhttps://tecnologiassemfio.wordpress.com/2010/02/05/apresentacao-do-gvpr/ Acessado em […]

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s


%d blogueiros gostam disto: