Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

 

Estrutura de dados do SGB

O SGB (= Stanford GraphBase) de Knuth usa uma estrutura de dados sofisticada, definida em C, para representar grafos na memória do computador.  As partes mais importantes da estrutura serão resumidas a seguir; os detalhes devem ser estudados na seção 1 do capítulo 2 do Stanford GraphBase e no módulo GB_GRAPH do SGB.

Graph, Vertex e Arc

Cada grafo é representado por um  struct  (= registro) do tipo  Graph.  Cada vértice é representado por um  struct  do tipo  Vertex,  e cada arco é representado por um  struct  do tipo  Arc.  Um programa que trabalhe com essa estrutura de dados declarará variáveis como 

Graph * g;  
Vertex * v;  
Arc * a;

Em lugar de  "g aponta para um grafo"  ou  "g é o endereço de um grafo",  diremos simplesmente  "g é um grafo".  Analogamente, diremos  "v é um vértice"  em lugar de  "v aponta para um vértice"  ou  "v é o endereço de um vértice".

O leque de saída de um vértice v é armazenado em uma lista encadeada (= linked list).  Na falta de um nome melhor, vou dizer que esta é a lista de saída do vértice v. É claro que cada arco pertence a uma e uma só lista de saída.

Cada registro do tipo  Vertex  tem um campo  arcs  que aponta para o primeiro arco da lista de saída do vértice.  Também tem um campo  name  que contém o endereço de uma cadeia de caracteres (= string) que é o "nome" do vértice.  Assim, se v é um vértice (ou seja, se v é do tipo  Vertex *)  então

v–>arcs  é o início da lista de saída de v (ou vale NULL) e
v–>name  é o nome de v.

Cada registro do tipo  Arc  tem um campo  next  que contém o endereço do próximo arco na lista de saída a que o arco pertence (é claro que esse outro arco terá a mesma ponta inicial que  a).  Também tem um campo  tip  que contém o endereço da ponta final do arco.  Assim, se  a  é um arco então

a–>next  é outro arco na lista de saída a que  a  pertence (ou vale NULL) e
a–>tip  é a ponta final de  a.

Cada registro do tipo  Graph  tem um campo  n  que armazena o número de vértices do grafo, um campo  m  que armazena o número de arcos, e um campo  id  que aponta para o nome do grafo.  O conjunto de todos os vértices do grafo é armazenado em um vetor (= array) de objetos do tipo  Vertex;  o campo  vertices  de  Graph  contém o endereço desse vetor.  Assim, se g é um grafo então

g–>n  é número de vértices de g,
g–>m  é número de arcos de g,
g–>id  é o nome de g e
g–>vertices  é o endereço do vetor de vértices de g.

Diremos, informalmente, que o "índice" ou "posição" de um vértice v no vetor de vértices é a diferença entre os endereços  v  e  g–>vertices, ou seja, o número

v – g–>vertices .

É evidente que esse número estará entre 0 e  g–>n – 1. 

Formalmente, a estrutura de dados que representa um grafo é definida assim: 

typedef struct {
    Vertex * vertices;
    long n, m;
    char * id;
} Graph;

typedef struct vertex_struct {
    struct arc_struct * arcs;
    char * name;
} Vertex;

typedef struct arc_struct {
    struct vertex_struct * tip;
    struct arc_struct * next; 
} Arc;

Mas essas definições estão incompletas: os registros  Vertex ,  Arc,  e  Graph  têm mais alguns campos "auxiliares" de que falarei adiante.

Essas estruturas, bem como os protótipos de várias funções básicas de criação e manipulação de grafos, estão no header file gb_graph.h.  Portanto, qualquer programa que usa as estruturas do SGB começa com 

#include "gb_graph.h"

Exercícios

  1. Faça uma figura da estrutura SGB que representa o grafo do exemplo 1 do capítulo O que é um grafo?.

  2. Escreva uma função C que imprima os nomes dos vértices de um grafo g.  Escreva uma função que imprima os nomes das pontas inicial e final de cada arco. 

  3. Escreva um fragmento de código C que conte o número de arcos de um grafo g e compare esse número com  g–>m. 

  4. Escreva um fragmento de código C que imprima uma lista de todos os sorvedouros de um grafo dado.  [Um vértice v é sorvedouro se v–>arcs == NULL.]

  5. Escreva um fragmento de código C que imprima uma lista de todas as fontes de um grafo dado.

Utility fields

Para facilitar a vida do usuário, os registros  Graph,  Vertex  e  Arc  têm alguns campos auxiliares conhecidos como utility fields.  Cada um desses campos é um  union  (no sentido C) do tipo  util  e pode armazenar o endereço de um vértice, ou o endereço de um arco, ou o endereço de um grafo, ou um string, ou um inteiro. 

typedef union {
    struct vertex_struct * V;
    struct arc_struct * A;
    struct graph_struct * G;
    char * S;
    long I;
} util;

O registro  Vertex  tem 6 desses campos (além dos campos  arcs  e  name): 

util u, v, w, x, y, z;

Suponha, por exemplo, que os vértices do meu grafo representam cidades.  Suponha que cada cidade tem uma certa altitude acima do nível do mar e pertence a uma comarca que tem um cidade-sede.  Podemos usar os utility fields z e y, por exemplo, para guardar essas informações: a altitude de uma cidade v será  v–>z.I  e a sede da comarca será  v–>y.V.  É claro que podemos dizer que a altitude de v é  v–>altitude  e que a sede da comarca é  v–>sede  se adotarmos 

#define altitude z.I
#define sede y.V

O registro  Arc  tem apenas dois utility fields, que atendem pelos nomes  a  e  b.  O registro  Graph  tem 6 utility fields:  uu, vv, ww, xx, yy e zz.

Exercícios

  1. Escreva um fragmento de código C que calcule o grau de saída de um vértice v.  Escreva um fragmento de código que calcule o grau de entrada de v.  Grave o grau de saída de cada vértice em um utility field saída e o de entrada em um utility field entrada.  
    #define saída u.I
#define entrada v.I

  2. Escreva um fragmento de código C que calcule o número de vizinhos de um vértice v.  Grave o número de vizinhos em um utility field vizinhos. 

  3. Escreva um fragmento de código C que calcule o grau de saída e o grau de entrada de um conjunto X de vértices.  O conjunto X é especificado por um utility field: um vértice v está em X se  v–>dentro == 1  e fora de X se  v–>dentro == 0.

  4. Escreva uma função que determine o grau de saída mínimo e o grau saída máximo dos vértices de um grafo g.  Grave o primeiro no utility fiels uu e o segundo no utility field vv.

  5. Um grafo é bipartido dirigido se cada um de seus vértices é uma fonte ou um sorvedouro.  Escreva uma função que receba um grafo no formato SGB e decida se o grafo é ou não bipartido dirigido.  Em caso afirmativo, sua função deve rotular todos os vértices:  v–>fonte vale 1 se v é fonte e 0 em caso contrário.   [Grafos bipartidos dirigidos ocorrem com freqüência em aplicações práticas. Exemplo:  cada vértice é um programa (software) ou uma máquina (harware); um arco liga um programa p a uma máquina m se e só se p pode ser executado na máquina m.]

Funções que geram grafos

O SGB tem muitas funções que geram grafos interessantes.  O grafo do exemplo 1 do capítulo O que é um grafo?, por exemplo, foi gerado pela função random_graph.  Mais especificamente, aquele grafo é 

random_graph (9,10,1,1,1,NULL,NULL,0,0,79) .

Trata-se de um grafo pseudo-aleatório com 9 vértices e 10 arcos. A "semente" do gerador de números pseudo-aleatórios é 79.  [Apesar do caráter aleatório, o grafo gerado a partir de dados valores dos parâmetros é sempre o mesmo.]  O valor 1 do terceiro parâmetro significa que o grafo poderá ter laços; o valor 1 do quarto parâmetro significa que o grafo poderá ter arcos paralelos.

Exercícios

  1. Escreva e teste um programa CWEB que "exiba" algum dos grafos SGB, ou seja, imprima os nomes de seus vértices e sua matriz de adjacências.  Aplique essa função pelo menos aos seguintes grafos do SGB: 
    random_graph (n,m,1,1,1,NULL,NULL,0,0,0)
econ (n,2,t,0)
miles (n,0,0,1,0,d,0)
games (n,0,0,0,0,0,0,s)
subsets (q,1,1-p,0,0,0,1,0)
gunion (board(p,q,0,0,-1,0,0), board(p,q,0,0,-2,0,0))

    [Cuidado! Não confunda o dígito "1" com a letra "l".  Na fonte courier do MS Explorer é praticamente impossível distinguir os dois caracteres.]  A documentação do seu programa deve fazer uma pequena descrição de cada grafo.

  2. Melhore o programa de exibição do exercício anterior:  imprima a matriz de adjacências de tal forma que os vértices de cada componente fiquem juntos.  Veja a tarefa A.

  3. Escreva uma função que receba um grafo no formato SGB e decida se o grafo é ou não bipartido dirigido.  Em caso afirmativo, sua função deve imprimir uma matriz de adjacências especial cujas linhas correspondem às fontes e cujas colunas correspondem às não-fontes.

  4. Faça figuras (com lapis e papel) dos seguinte grafos: 
    econ(8,2,10000,0)
subsets(2,1,-3,0,0,0,1,1)
subsets(2,1,-4,0,0,0,1,1)
board(5,4,0,0,-1,0,1)
board(5,4,0,0,-1,1,1)

    (Sugestão: use uma adaptação do tarefa A para "ver" os grafos.

 

URL of this site:  www.ime.usp.br/~pf/algoritmos_em_grafos/
Last modified: Tue Dec 8 13:52:26 BRST 2009
Paulo Feofiloff
IME-USP