malbarbo.pro.br

6898 Algoritmos em Grafos

Edição 2014/1 - Ciência da Computação

Trabalho / Diversão com algoritmos em grafos

Introdução

O objetivo deste trabalho é a implementação da estrutura de lista de adjacências e alguns algoritmos em grafos.

O trabalho é em equipe de até duas pessoas. O compartilhamento de informações entre as equipes é permitido (e aconselhado), mas o compartilhamento de código não é permitido. Trabalhos que tenham porções significativas de código iguais, ou copiados da internet, serão anulados. Veja a resolução Nº 008/2007-COU para as possíveis sansões disciplinares.

Descrição

O objetivo deste trabalho é a implementação da estrutura de lista de adjacências e diversos algoritmos em grafos.

Existem dois desafios neste trabalho. O primeiro é implementar os algoritmos e obter o tempo de execução previsto na teoria. O segundo é escrever um código limpo e organizado.

O programa deve receber dois parâmetros na linha de comando. O primeiro parâmetro é o nome do algoritmo e o segundo é o arquivo do grafo. O programa deve executar o algoritmo para o grafo e escrever na saída padrão o resultado da execução do algoritmo.

Formato do arquivo de entrada

Os arquivos de entrada estão em uma versão simplificado do formato tgf. O arquivo consiste de um conjunto de vértices e um conjunto de arestas. Exemplo:

a
2
verde
4
#
a 2
verde 3
verde 2
2 3

Os conjuntos de vértices e arestas são separados por uma linha com o caractere #. Cada vértice é especificado em uma linha e pode ter qualquer nome (sem espaço). Cada aresta é especificada por um par de vértices separados por espaço. Desta forma, o grafo do exemplo tem o conjunto $\{a, 2, verde, 4\}$ de vértices e o conjunto $\{(a, 2), (verde, 3), (verde, 2), (2, 3)\}$ de arestas.

Este formato de arquivo pode representar tanto grafos não orientados quanto grafos orientados, ficando a critério da aplicação interpretar o significado das arestas.

Se as arestas têm peso, o mesmo pode ser adicionado como um terceiro item em cada aresta. Desta forma, a linha a b 20 representa a aresta $(a, b)$ com peso 20.

Algoritmos

Os seguintes algoritmos devem ser implementados:

bfs: Algoritmo de busca em largura. O grafo de entrada é orientado e as arestas não têm peso. O vértice de origem $s$ é o primeiro vértice no arquivo de entrada. Para cada vértice $v$ acessível a partir de $s$, uma linha deve ser escrita na saída contendo os vértice $s$ e $v$ e a distância $d$ entre $s$ e $v$ encontrada pelo algoritmo. Por exemplo, se o vértice inicial é o vértice $a$ e os vértices $b$ (distância 1), $c$ (distância 2) e $d$ (distância 2) são acessíveis a partir de $a$, a saída deve ser

a a 0
a c 2
a d 2
a b 1

Observe que o vértice $a$ é acessível a partir dele mesmo com a distância 0. Além disso, a ordem da saída não é importante.

scc: Componentes fortemente conexas. O grafo de entrada é orientado e as arestas não têm peso. Cada scc deve ser escrita em uma linha com os vértices separados por espaços. Por exemplo, se um grafo contém 3 sccs, a primeiro com os vértices $a$ e $b$, a segunda com o vértice $c$ e a terceira com os vértices $d$, $e$ e $f$, a saída deve ser

b a
d f e
c

Observe que ordem dos vértices na componente e a ordem dos componentes não é importante.

bf: Algoritmo de Bellman-Ford para encontrar caminhos mais curtos. O grafo de entrada é orientado e as arestas têm peso. O vértice de origem $s$ é o primeiro vértice no arquivo de entrada. Para cada vértice $v$ acessível a partir de $s$, uma linha deve ser escrita na saída contendo um caminho mais curto de $s$ para $v$ e o custo do caminho. Por exemplo, se um caminho mínimo entre $s$ e $v$ é $\langle s, w, u, v \rangle$ e tem custo 23, a saída deve conter a linha

s w u v 23

bfall: Algoritmo bf executado com cada vértice do grafo como origem. A entrada e a saída tem o mesmo formato do algoritmo bf.

dk: Algoritmo de Djkistra para encontrar caminhos mais curtos. A entrada e a saída tem o mesmo formato do algoritmo bf.

dkall: Algoritmo dk executado com cada vértice do grafo como origem. A entrada e a saída tem o mesmo formato do algoritmo bf.

fw: Algoritmo de Floyd-Warshall para encontrar caminhos mais curtos. A entrada e a saída tem o mesmo formato do algoritmo bf.

Desenvolvimento

Para facilitar o desenvolvimento do trabalho, está disponível um “projeto” com os arquivos iniciais de código, um programa testador e um Makefile para compilar, testar e enviar o programa.

Para fazer o download e utilizar este projeto é necessário ter os seguintes programas instalados: git, make e python2.7. No Ubuntu ou Debian estes programas podem ser instalados com o comando

apt-get install git make python2.7

Para fazer o download do projeto, execute o comando (pode demorar um pouco)

git clone http://malbarbo.pro.br/git/graphun

Após a execução deste comando, um diretório chamado graphun terá sido criado. No diretório graphun/src existe um diretório para cada linguagem que pode ser utilizada para implementar o trabalho, você deve usar o comando

chmod -f +x src/lang/{run,build}

para avisar o testador sobre a linguagem que será utilizada. Observe que você deve trocar a palavra lang pelo nome do diretório da linguagem escolhida.

Todos os arquivos de código devem ficar no diretório src/lang/. Além disso, já existe um arquivo principal, onde a função principal do seu programa deve ser definida.

Linguagens

O trabalho pode ser implementado em uma das seguintes linguagens:

Atenção: Só é permitido a utilização das bibliotecas padrão de cada linguagem/ambiente.

Testes

Cada algoritmo será testado com alguns grafos pequenos e alguns grafos maiores. Os grafos pequenos são enumerados de 1 a 5. Os grafos grandes são enumerados com valores maiores que 5. Os grafos grandes são úteis para verificar o tempo de execução dos algoritmos.

Algoritmos que resolvem o mesmo problema são executados para um subconjunto igual de testes. Isto permite fazer comparações dos tempos de execução dos algoritmos.

Veja os arquivos testes/alg/desc.txt para a descrição dos casos de teste.

Veja o arquivo testes/tempo-ref.txt para os tempos de execução obtidos pela implementação do professor.

Para executar os testes, entre no diretório graphun e execute um dos comandos

make testar       # testa todos os algoritmos
make testar-bfs   # testa a implementação do algoritmo bfs
make testar-scc   # testa a implementação do algoritmo scc
make testar-bf    # testa a implementação do algoritmo bf
make testar-bfall # testa a implementação do algoritmo bfall
make testar-dk    # testa a implementação do algoritmo dk
make testar-dkall # testa a implementação do algoritmo dkall
make testar-dkfw  # testa a implementação do algoritmo fw

Envio do trabalho

Para enviar o trabalho, execute o comando

make enviar

O script de envio criará um arquivo compactado com os arquivos a serem entregues para correção e enviará para a página do professor.

Após enviar o trabalho, o aluno deverá entrar na página da disciplina (o endereço será impresso na tela depois do envio), imprimir e assinar o termo de autoria. O termo de autoria é um documento em que o aluno afirma que ele é o autor do código do trabalho que ele enviou e que portanto, não copiou parte significativa do programa de outra pessoa ou da internet.

O termo de autoria assinado deve ser entregue pessoalmente ao professor na próxima aula após a data de entrega do trabalho.

Avaliação

O trabalho será avaliado de acordo com os critérios:

Dicas