MAC110 - Introdução à Computação

BCC - 1o. Semestre de 1999

Exercício-Programa 2

Componentes Conexos de Grafos

Sinopse

Veja este diretório para o exemplo ep2exemplo.c, para a rotina de geração de grafos, etc. Veja aqui como compilar (use o Makefile dado neste diretorio; ele é próprio para a rede GNU/Linux do IME).
Veja este diretório para as várias saídas gráficas vistas em sala.
Estes são executáveis para você experimentar:
- Para GNU/Linux: ep2_X, ep2_X_static, ep2_PS, ep2_PS_static.
- Para DOGS (compilado com djgpp): ep2std.exe (147102 bytes)
Exemplos de execução: saida.txt
Opcional. Veja este diretório para mais detalhes sobre a biblioteca gb_flip de Knuth. O gb_flip é um módulo do Stanford GraphBase de Knuth (usado na disciplina MAC328 - Teoria dos Grafos).

Descrição deste Exercício

São dois os objetivos deste exercício: (1) você terá de produzir com seu EP saídas gráficas (o pacote gráfico padrão é o do livro de Roberts); (2) você manipulará objetos de tamanho considerável e para tanto você precisará tomar cuidado com a representação dos dados e com o algoritmo que você utilizará. Introduzimos o problema com um exemplo. Suponha que você tenha o seguinte grafo: g1.ps (use o programa ghostview ou gv para visualizar este arquivo no X; alternativamente, voce pode imprimir este arquivo em qualquer impressora que entenda arquivos PostScript). Os vértices deste grafo são os pares (i,j), onde

0 <= i <
7

e 0<= j < 5. O vértice no canto inferior esquerdo é o vértice (0,0) e o vértice no canto superior direito é o vértice (6,4).

Estamos interessados no vértice central (3,2). Estamos, na verdade, interessados no componente conexo deste vértice, isto é, o grafo definido pelos vértices que são alcançáveis a partir de (3,2) pelas arestas. Você pode imaginar que os 7 * 5 = 35 vértices deste grafo representam cruzamentos entre ruas e que as 29 arestas representam ruas trafegáveis. A nossa tarefa então seria descobrir o conjunto de ruas e cruzamentos alvancáveis se estamos no cruzamento de coordenadas (3,2). A resposta é dada por este grafo: g2.ps.

Em geral, dado um grafo como acima (com M colunas e N linhas de vértices), o seu EP deve determinar o componente conexo do vértice (M/2,N/2) (a divisão aqui é a divisão inteira). Note que no exemplo acima, M = 7 e N = 5.

A entrada. A entrada do seu problema é, portanto, um grafo. Este grafo será dado através de um módulo, o módulo grafo_aleat. Este módulo tem a interface grafo_aleat.h. Estude esta interface! Voce pode encontrar a implementação deste módulo neste diretório. Entretanto, você não precisa entender como as funções de grafo_aleat.h são implementadas. Estude o programa-exemplo ep2exemplo.c para ver como podemos utilizar este módulo de geração de grafos. Note que, para gerar um grafo usando o módulo grafo_aleat, precisamos dos parâmetros M, N, p (a probabilidade de uma potencial arestas estar efetivamente presente no grafo a ser gerado), e seed, um inteiro que determina o comportamento do gerador de números aleatórios usado na implementação desta módulo. Note que este módulo deve, dado o mesmo conjunto de parâmetros, gerar o mesmo grafo quando compilado e executado em plataformas diversas.
A saída. O ideal é que você possa gerar suas saídas como o arquivo g2.ps acima, isto é, como arquivos PostScript. Para tanto, use a versão standard das bibliotecas de Roberts. Você pode usar a versão xwindows para obter resultados na tela (bom para depuração). Sugiro também que o seu programa possa gerar uma saída gráfica representando o grafo todo (não apenas o componente conexo procurado); você pode verificar a correção de seu programa em exemplos pequenos examinando as saídas.
O algoritmo. Há vários algoritmos para você encontrar o componente conexo de um dado vértice em um grafo (estes algoritmos são conhecidos pelo nome genérico de `algoritmos de busca' ou `exploração'). A minha sugestão é que cada um de vocês procure encontrar um algoritmo razoável, experimentando trabalhar com grafos pequenos, com lápis e papel!

Execute o seu programa com os seguintes parâmetros e compare o resultado com os arquivos deste diretório.

(M, N, p, seed) = (19, 17, 0.5, 31415)
(M, N, p, seed) = (19, 17, 0.5, 3415)
(M, N, p, seed) = (19, 17, 0.5, 3115)
(M, N, p, seed) = (19, 17, 0.5, 145)
(M, N, p, seed) = (19, 17, 0.5, 21613)
(M, N, p, seed) = (19, 17, 0.5, -314115)
(M, N, p, seed) = (250, 230, 0.5, 31415)
(M, N, p, seed) = (250, 230, 0.5, 3415)
(M, N, p, seed) = (250, 230, 0.5, 3115)
(M, N, p, seed) = (250, 230, 0.5, 145)
(M, N, p, seed) = (250, 230, 0.5, 21613)
(M, N, p, seed) = (250, 230, 0.5, -314115)

Outros valores para testar:

(M, N, p, seed) = (500, 500, 0.5, 5727)
(M, N, p, seed) = (500, 500, 0.51, 5727)
(M, N, p, seed) = (500, 500, 0.49, 5727)

Observações importantes

Data de Entrega: você deve entregar o seu programa até as 18:00 do dia 7 de junho de 1999, na secretaria do Departamento de Ciência da Computação, Sala 256, Bloco A. Se por algum acaso a secretaria fechar antes deste horário, você deve me procurar. Caso não me encontre (e isto é necessário somente neste caso), você deve enviar o seu programa por correio eletrônico para mim, até as 18 horas daquele dia.
Programas entregues com atraso valerão muito pouco.
O EP é estritamente individual. Exercícios semelhantes receberão nota 0.
Exercícios com erros de sintaxe receberão nota 0.
Endente o seu programa sistematicamente. Uma má apresentação do código resultará em nota menor.
Coloque comentários apropriados em seu programa. Programas sem documentação receberão nota baixa.

Coloque um cabeçalho bem informativo, como o seguinte

  /***********************************************************************
   *
   * Nome do Aluno ...            Numero USP ...
   *
   * Curso ...                    Data ...
   *
   * Nome do Professor ...
   *
   * Exercicio Programa Numero ...
   *
   * Compilador usado ...
   *
   **********************************************************************/

Entregue em um envelope (preferencialmente de plástico transparente):
- Um disquete com o código do seu programa. Identifique o disquete com uma etiqueta. Observação. Note que o monitor vai compilar o seu programa, de forma que não é necessário incluir um executável. Se voce tiver familiaridade com estas coisas e o seu programa envolver a compilação separada de vários módulos, você pode incluir um Makefile para facilitar o processo de compilação.
- Uma listagem do programa.
- Quaisquer saídas que você achar importantes (com as respectivas entradas, em forma eletrônica, quando cabível). A abrangência dos seus testes também será considerada na nota. Saber testar bem um programa é também muito importante.
Uma regra básica é a seguinte: do ponto de vista do monitor, quanto mais convenientemente apresentado estiver o seu programa, melhor será a disposição dele para dar uma nota generosa.
Guarde uma cópia de seu material até o fim do semestre!

Página de principal de MAC110 (BCC - 1o. semestre de 1999).

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Thu Jun 3 00:18:38 EST 1999