Tarefa A

Programming is best regarded as the process of creating works of literature, which are meant to be read.
— D.E. Knuth, Literate Programming

Tarefa de programação A: exibição de grafos do SGB

Escreva e teste um programa que exiba informações sobre alguns dos grafos gerados pelo SGB (Stanford GraphBase). Seu programa deve ser capaz de analisar os grafos

random_graph (p, q, 1, 1, 1, NULL, NULL, 0, 0, 0),
subsets (q, 1, 1−p, 0, 0, 0, 1, 0),
games (p, 0, 0, 0, 0, 0, 0, q),
miles (p, 0, 0, 1, 0, q, 0),
o grafo dos movimentos da dama num tabuleiro de xadrez p-por-q.

Para executar o seu programa, o usuário deverá escolher um dos cinco grafos e especificar os valores dos parâmetros p e q. Para ter acesso às funções que geram esses grafos, seu programa deverá incluir os header files apropriados (gb_rand.h, gb_basic.h, gb_games.h, gb_miles.h, etc.)

Para cada grafo, o seu programa deve calcular e imprimir as seguintes informações:

O nome do grafo. Esse nome está no campo id do grafo.
O número de vértices do grafo.
O número de arcos. Conte o número de arcos diretamente e compare-o com gm; se houver diferença, imprima mensagem apropriada e aborte a execução do programa.
O número de laços, de arcos paralelos e de arcos antiparalelos. Aproveite para dizer se o grafo é ou não simétrico.
O grau de saída e o grau de entrada de cada vértice. Guarde esses graus em utility fields.
Os graus de saída e entrada do conjunto dos 5 primeiros vértices. Os 5 primeiros vértices são vertices[0], … , vertices[4]. Se o grafo tiver menos que 5 vértices, imprima uma desculpa apropriada.
O número de componentes e o tamanho de cada componente. Imprima uma pequena tabela com o número de vértices de cada componente.
Os nomes de todos os vértices, agrupados por componente. Em cada componente, os nomes dos vértices devem ser impressos em ordem decrescente de grau de saída.
A matriz de adjacências do grafo. Se o grafo tiver mais que 60 vértices, dê uma desculpa apropriada e não imprima a matriz.

Recomendações

O seu programa deve aceitar três parâmetros na linha de comando. O primeiro parâmetro deve ser rand, subsets, games, miles ou dama, correspondendo aos grafos random_graph, subsets, games, miles e o grafo das damas respectivamente. O segundo e o terceiro parâmetros devem ser os valores de p e q. Por exemplo, a linha de comando
```
    exiba dama 8 8
```
deve provocar a geração e análise do grafo dos movimentos da dama sobre um tabuleiro de xadrez 8-por-8.
Use os dispositivos padrão de entrada e saída (stdin e stdout). O programa não pode exigir que o usuário responda perguntas via teclado.
Todos os comandos de entrada e saída devem ficar na função main. A função main só deve cuidar da entrada (isto é, do processamento da linha de comando), da saída, e da chamada de outras funções.
Use a imaginação para inventar boas interfaces entre main e as demais funções. Por exemplo, a função que calcula os componentes pode reunir os vértices de cada componente em um lista encadeada circular; os links de uma tal lista ficarão nos utility fields de vértices e a função main poderá então imprimir os vértices dos componentes percorrendo essas listas.
Cada função de seu programa deve fazer um serviço bem definido; não escreva funções que fazem dois ou mais serviços não-relacionados.
Documente cada função de seu programa, ou seja, diga o que a função faz. Não suje o programa com comentários misturados ao código.
Para cada uma das funções geradoras de grafos usada pelo seu programa, você deve dar uma descrição, curta mas precisa, do grafo que a função gera. Em particular, deve explicar o significado dos parâmetros p e q em cada caso. Mas não deve perder tempo com explicações sobre os outros parâmetros, a menos que isso seja necessário para descrever o grafo.
Brinque com o seu programa. Tente várias combinações de parâmetros. Examine os resultados. Faça desenhos num papel de rascunho, para melhor ver os grafos. Tente derrubar o SGB usando valores extremos dos parâmetros.