Estrutura de dados do SGB (Stanford GraphBase)

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 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 poderá declarar variáveis como

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 struct 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

Cada struct 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

Cada struct 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 de objetos do tipo Vertex; o campo vertices de Graph contém o endereço desse vetor. Assim, se g é um grafo então

O índice que dá a posição de um vértice v no vetor de vértices é a diferença entre os endereços v e gvertices, ou seja, o número

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 structs 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 deve começar com

Exercícios 1

Faça uma figura da estrutura SGB que representa o grafo do exemplo 1 do capítulo O que é um grafo?.
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.
Escreva um fragmento de código C que conte o número de arcos de um grafo g e compare esse número com gm.
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 varcs ≡ NULL.)
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 structs 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;

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 uma cidade-sede. Podemos usar os utility fields z e y, por exemplo, para guardar essas informações: a altitude da cidade v será vz.I e a sede da comarca será vy.V. Podemos dizer que a altitude de v é valtitude e que a sede da comarca é vsede se adotarmos

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

Exercícios 2

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 saida e o de entrada em um utility field entrada.

#define saida u.I
#define entrada v.I
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.
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 vdentro ≡ 1 e fora de X se vdentro ≡ 0.
Escreva uma função que encontre 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 field uu e o segundo no utility field vv.
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: vfonte vale 1 se v é fonte e 0 em caso contrário. (Grafos bipartidos dirigidos ocorrem com frequê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 é

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. (O grafo não é verdadeiramente aleatório: uma vez dados os valores de todos os parâmetros, o grafo gerado é 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 3

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))

A documentação do seu programa deve fazer uma pequena descrição de cada grafo.
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.
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.
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.