(revisado em Wed Apr 20 11:02:20 2011)
O objetivo do trabalho é a implementação dos algoritmos de busca em um grafo dado.
A entrada deve ser lida da entrada padrão (stdin) e deve ser um
arquivo texto com números inteiros. O primeiro número, N, é a quantidade
de vértices (os vértices são indexados com os números de 1 a N). Os
números seguintes vem em pares e representam as arestas (pares de
vértices). O vértice inicial para as buscas será sempre o vértice 1.
Exemplo (ciclo de 4 vértices):
4 1 2 1 3 2 4 3 4
A saída deve ser escrita na saída padrão (stdout) e deve ser formada
por um conjunto de linhas, cada linha com quatro números inteiros
separados por espaço. Estes números representam o vértice, o pai do
vértice na árvore gerada pela busca, o timestamp de entrada na
estrutura e o timestamp de saída. Os timestamps são contados a
partir de 1 (um). As linhas devem estar ordenadas pelo índice do
vértice. Vértices não visitados devem ter 0 nos índices que representam
o pai e os timestamps de entrada e saída.
Exemplo (busca em profundidade):
1 0 1 8 2 1 2 7 3 4 4 5 4 2 3 6
O trabalho deve ser feito de forma que possa ser compilado e executado nas servidoras de computação do Departamento de Informática.
Alguns arquivos devem ser levados em consideração para a confecção do trabalho. Os arquivos são:
libgraph.h: biblioteca de grafo;
search.h: biblioteca de busca;
selector.h: biblioteca para conjunto de vertices e seletor;
busca.c: exemplo de uso da busca.
O trabalho consiste em implementar uma busca genérica simples
(search) que use a biblioteca libgraph para representar o grafo
e que use como conjunto de vértices sendo visitados (conjunto L) um
conjunto fornecido pela biblioteca selector. Note que o tipo de
busca depende de como os vértices de um conjunto L são escolhidos.
Para que tudo funcione, é preciso implementar a libgraph. Além
disso, é preciso implementar duas versões para a selector. A
primeira versão deve se chamar depth e o resultado esperado é o de
uma busca em profundidade. A segunda versão deve se chamar breadth e
o resultado esperado é o de uma busca em largura.
A implementação de search não deve depender da implementação de
libgraph nem de select, e deve ter a interface como em
search.h.
O modo de usar as diferentes versões de selector deve ser somente na
hora de gerar o executável, e deve estar refletido no makefile que
deve ser entregue.
Se for feito em linguagem C, deve usar os arquivos .h fornecidos pelo
professor. Se fizer em outra linguagem, deve procurar manter o mesmo
padrão de interface usado nos arquivos .h fornecidos pelo professor.
Além dos arquivos fonte, deve acompanhar um makefile e um arquivo
README explicando o que foi feito e com o nome dos autores. Qualquer
particularidade deve estar descrita neste texto.
Para compilar vou usar o comando make (sem nenhum parâmetro),
portanto preparem o makefile para fazer isso. O resultado do make deverá
ficar no mesmo diretório onde está o makefile. Os executáveis devem ter
os nomes dfs (busca em profundidade) e bfs (busca em largura).
O trabalho deve ser empacotado em um arquivo
login1-login2-login3.tar.gz, onde login1-login2-login3 é uma string com
os logins dos integrantes da equipe nas servidoras do DInf. Ao
descompactar este arquivo deverá ser criado um diretório de nome
login1-login2-login3 que conterá todos os demais arquivos. O make
deverá funcionar dentro deste diretório (não em subdiretórios).
Este arquivo deve ser enviado por e-mail ao endereço do professor (andre) com o assunto "CI065-trab1" (exatamente).
O trabalho pode ser feito em equipes de 2 ou 3 (três) alunos de graduação ou por 1 (um) aluno de pós-graduação.