Curitiba,

setembro 2003 # 135

Graph viz: uma ferramenta para a geração de grafos

Autor: Ioquir Afonso Sotile

Introdução

Minha dissertação de mestrado trata da descoberta de dependências entre serviços de software, descobertas a partir da análise do tráfego de rede. Cada dependência é representada basicamente pelas informações origem, destino e serviço utilizado. Em determinado momento é necessário representar as dependências de forma gráfica, transformando estas informações, a princípio desconexas umas das outras, em um mapa de relacionamentos que permita a visualização das relações indiretas de dependência.

A possibilidade de construir um programa para gerar o mapa de dependências surgiu, mas sabia-se que seria descartada caso fosse considerado muito grande o esforço necessário. Por isso partiu-se em busca de uma forma de importar as relações de dependências para um gráfico do Visio ou de ferramenta equivalente, de uma biblioteca gráfica de programação que pudesse ser utilizada ou mesmo de uma ferramenta já existente para a geração dos gráficos. Para minha felicidade, nestes tempos de Internet, listas e principalmente software livre, já havia algo pronto: o GraphViz, que se demonstrou ideal para a aplicação.

Grafos

Um grafo é uma abstração matemática, útil na resolução de vários tipos de problemas. Essencialmente, um grafo consiste de um conjunto de vértices e um conjunto de arestas, onde uma aresta é algo que conecta dois vértices no grafo. Um grafo G(V,E) é um conjunto finito não vazio V e um conjunto E de pares (u,v) não ordenados de elementos de V. Em um grafo não direcionado, as arestas são pares não ordenados e conectam dois vértices em ambas as direções, neste caso (u,v) e (v,u) são duas maneiras de referenciar a mesma aresta, o que não acontece para os grafos direcionados.

Esta definição de um grafo é um tanto quanto vaga: ela não diz o que representam os vértices e arestas. Podem ser cidades e as estradas que as conectam, ou páginas Internet com seus hyperlinks. Estes detalhes são deixados de lado na definição de um grafo por uma razão: não são parte necessária da abstração do grafo. Ignorando os detalhes, pode-se construir uma teoria que é reutilizável e pode auxiliar na resolução de vários tipos de problemas.

Um grafo pode ser representado matematicamente por:

V = {v, b, x, z, a, y }
E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) }
G = (V, E)

A Figura 1 é a representação gráfica deste grafo. A aresta (x,x) é chamada de laço. As arestas (b,y) e (b,y) são arestas paralelas. Laços e arestas paralelas aparecem em multigrafos mas não costumam ser permitidas em grafos direcionados e não direcionados.

Figura 1 - Multigrafo direcionado

Na Figura 2 o mesmo grafo é representado, mas agora como não direcionado. A repetição de aresta (b,y), o laço (x,x) e a aresta (a,z) que repete a (z,a) foram removidas.

Figura 2 - Grafo não direcionado

O Pacote GraphViz

O GraphViz é um conjunto de programas, de código fonte aberto, para a automatização do desenho de grafos. O pacote, cujo código fonte e executáveis estão disponíveis para as plataformas mais comuns, inclui ferramentas para a criação de representações hierárquicas de grafos direcionados (dot), de representações no modelo spring para grafos não direcionados (neato), uma interface ajustável escrita em LEFTY (dotty), uma interface gráfica ajustável (tcldot) escrita com a biblioteca libgraph tlc7.6, e uma interface web, o webdot.

As ferramentas do GraphViz rodam em modo stand-alone, mas interfaces para sistemas e bancos de dados externos podem ser utilizadas. Isso envolve criar scripts dotty ou tcldot para mudar o comportamento do editor de grafos e para fazê-lo comunicar-se com os arquivos ou programas externos.

O GraphViz tem componentes para a criação de representações hierárquicas de árvores e grafos acíclicos direcionados e representações físicas virtuais (modelo spring) de grafos não direcionados, que podem ser utilizados em áreas como projetos de bancos de dados, engenharia de software, projeto de redes, entre outros.

Os algortimos utilizados pelo GraphViz são eficientes a ponto de construirem grafos com centenas de nós, com qualidade comparável a grafos gerados manualmente com ferramentas de CAD. Para isso, buscando revelar características interessantes dos dados e evitar distrações e irrelevâncias, são seguidos alguns princípios visuais simples:

- Favorecer o reconhecimento e leitura de objetos individuais. Através de rótulos de texto, formato, cores e estilos, facilitar a identificação de objetos.
- Evitar o cruzamento ou superposição de elementos.
- Facilitar a leitura do diagrama, diminuindo o movimento dos olhos para buscar nós e caminhos, origens e destinos. - Revelar padrões, enfatizando simetria, paralelismo e regularidade, que tornam o grafo mais fácil de ler e memorizar.

A maior vantagem do GraphViz é que o programador não precisa se preocupar com a disposição dos nós (ou vértices): o programa arranja-os de forma a obter a melhor e mais clara disposição. É possível agrupar e influenciar a disposição dos nós de maneira rápida e fácil, o que permite ao desenvolvedor concentrar-se nos dados.

Os módulos do GraphViz utilizam como entrada uma descrição do grafo na linguagem dot, bastante simples. Já a saída pode ser feita em vários formatos gráficos vetoriais ou de mapa de bits como: ps2, jpeg e gif. Os grafos podem ser gerados a partir de descrições armazenadas em um arquivo texto ASCII, que tem tamanho bastante reduzido. A Figura 3 apresenta em linguagem dot as definições necessárias para gerar os grafos ilustrados nas Figura 1 e Figura 2. Percebe-se que basta apenas indicar as arestas. Na definição dada na Figura 3(b), foram removidos os laços, arestas paralelas e redundantes, pois o GraphViz representa-os mesmo em grafos não direcionados.

Figura 3 - Definição na linguagem dot de um grafo simples direcionado (a) e não direcionado (b)

Figura 4 - Definição na linguagem dot do grafo direcionado de uma Máquina Finita de Estados

O GraphViz permite a utilização de variações da abstração básica de grafo, onde um vértice é representado por um ponto e as arestas não possuem atributos. Os exemplos a seguir acompanham o pacote e demonstram tanto a facilidade de uso quanto o poder da ferramenta. A Figura 4 apresenta o código na linguagem dot para o grafo de uma máquina finita de estados e a Figura 5 o grafo resultante.

Figura 5 - Grafo de uma Máquina Finita de Estados, gerado a partir da definição

As Figura 6 e Figura 7 ilustram a utilização do GraphViz para a criação de grafos bem diferentes dos tradicionais, no caso uma tabela hashing.

Figura 6 - Definição de um grafo de hashing na linguagem dot

Figura 7 - Representação hashing gerada a partir de definição em linguagem dot

Outros exemplos, que não serão colocados aqui, mostram a utilização de diretivas do dot para a alteração do símbolo utilizado nos nós, das setas das arestas, da divisão em camadas e agrupamento em blocos, entre outros.

De pacotes de rede para grafo de dependências

Uma primeira etapa da análise de pacotes de rede, buscando informações de dependências, gera informações básicas, no formato endereço IP de origem, endereço IP de destino, porta TCP utilizada e serviço representado pelo número da porta TCP, como as ilustradas na Figura 8, em que cada linha ou registro representa uma dependência.

Figura 8 – Informações de dependências obtidas a partir do tráfego de rede

Um programa simples, escrito em linguagem C, transforma as informações básicas das dependências em um arquivo de definição no formato dot. O resultado da transformação dos dados da Figura 8 é ilustrado abaixo, e o grafo resultante na Figura 10.

Figura 9 – Arquivo de definição de grafo gerado de informações obtidas da análise de rede

Figura 10 - Grafo de dependências entre hosts e serviços

Apenas com os dados obtidos da análise do tráfego TCP/IP da rede não é possível determinar quais serviços utilizam quais serviços, mas apenas que determinados hosts utilizam determinados serviços em outros hosts. Por isso foi utilizada a facilidade de agrupamento em blocos, definida no arquivo dot como um subgraph e visualizada na forma de retângulos que contém os nós do bloco.

Conclusão

O GraphViz demonstrou-se ideal para a resolução do problema básico de transformar informações desconexas sobre dependências entre serviços em uma representação gráfica legível. Isso é suficiente para a validação dos dados e para a construção de protótipos. No caso de sua utilização em um sistema de gerência de dependências, terão de ser exploradas outras facilidades como a sua utilização como um módulo de programa, utilização na web, a alteração do grafo após a sua construção e a possibilidade de visualização e navegação hierárquica entre grafos e subgrafos.

O GraphViz não trata de grafos animados, ou seja: não é possível alterar o grafo ou suas propriedades em tempo real. Isso pode ser contornado fazendo-se com que o grafo seja recriado se o arquivo dot sofrer alterações.

Cada um dos nós de um grafo gerado com a ferramenta dotty pode conter um ponteiro (URL). Uma aplicação bem construída pode permitir ao usuário navegar por vários níveis de abstração do grafo. Na verdade, os ponteiros apontariam para grafos gerados com diferentes níveis de abstração.

Características como boa qualidade dos grafos gerados, simplicidade de definição na linguagem dot, ser de cógido aberto, estar disponível para várias plataformas, ter odesenvolvimento promovido pela ATT, fazem do GraphViz um produto sem similar.

Referências:

1. FOWLER, M. Graphviz. Disponível em: <http://www.perladvent.org/2001/9th/>. Acesso em: 19 set. 2003.

2. GRAPHVIZ examples. Disponível em: <http://www.research.att.com/sw/tools/graphviz/examples/> Acesso em: 19 set. 2003.

3. GRAPH VISUALIZATION PROJECT. Disponível em: <http://www.graphviz.org/>. Acesso em: 05 set. 2003.

4. HUSSMAN, D. Exploring Graphviz’ dotty application in a pure Perl/Tk canvas. Disponível em: <http://perlhorizons.com/02/08/28/101240>. Acesso em: 19 set. 2003.

5. OVERVIEW of Graphviz source package. Disponível em: <http://packages.qa.debian.org/g/graphviz.html>. Acesso em: 19 set. 2003.

6. PORTAL OFICIAL DO GRAPHVIZ. Disponível em: <http://www.research.att.com/sw/tools/graphviz/>. Acesso em: 05 set. 2003.

7. PORTS/GRAPHICS/GRAPHVIZ. Disponível em: <http://www.freebsd.org/cgi/cvsweb.cgi/ports/graphics/graphviz/>. Acesso em: 19 set. 2003

8. REVISÃO da teoria elementar dos grafos. Disponível em:
<http://www.boost.org/libs/graph/doc/graph_theory_review.html>. Acesso em: 05 set. 2003.

9. SIEK, J. et al. The Boost Graph Library (BGL). Disponível em: <http://www.boost.org/libs/graph/doc/index.html>. Acesso em: 19 set. 2003.

10 . SOME applications that use Graphviz. Disponível em: <http://www.research.att.com/sw/tools/graphviz/webapps.html>. Acesso em: 19 set. 2003.

11. SZWARCFITER, J. Grafos e algoritmos computacionais. 2. ed. Rio de Janeiro: Campus, 1986.

sotile@celepar.gov.br