malbarbo.pro.br

5189 Algoritmos em Grafos

Edição 2013/1 - Informática

Trabalho / Algoritmos elementares em grafos

Introdução

O objetivo deste trabalho é a implementação da estrutura de lista de adjacências e algoritmos elementares 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.

Data de entrega: até o dia 05/05/2013 às 23:00h.

Descrição

Implementar algoritmos que trabalham com grafos requer uma estrutura de dados para representar o grafo e um conjunto de algoritmos elementares. Uma vez implementado estes requisitos, implementar novos algoritmos em grafos torna-se (em geral) uma atividade mais simples.

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

O desafio deste trabalho é criar uma infraestrutura para a implementação de algoritmos em grafos. O desafio não é implementar os algoritmos, isto porque os algoritmos estão descritos no livro, de forma que se existe uma boa infraestrutura o código dos algoritmos pode ser (em geral) facilmente escrito.

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.

ts: Ordenação topológica. O grafo de entrada é orientado e as arestas não têm peso. Os vértices devem ser escritos (um por linha) na saída na ordem topológica encontrada.

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.

mst: Árvore gerado mínima. Você pode escolher implementar o algoritmo de Kruskal ou o algoritmo de Prim. O grafo de entrada é não orientado e as arestas têm peso. A saída deve ser as arestas que fazem parte da árvore geradora mínima. Cada aresta deve ser escrita em uma linha, os dois vértices da aresta devem ser separados por espaço. Por exemplo, se a árvore geradora mínima contém as arestas $(a, b)$, $(a, c)$ e $(b, d)$, a saída deve ser

a b
d b
a c

Observe que a ordem das arestas não é importante.

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

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

Após a execução deste comando, um diretório chamado grafun terá sido criado. No diretório grafun/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 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.

Execução dos testes

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

make testar      # testar todos os algoritmos
make testar-bfs  # testar a implementação do algoritmo bfs
make testar-ts   # testar a implementação do algoritmo ts
make testar-scc  # testar a implementação do algoritmo scc
make testar-mst  # testar a implementação do algoritmo mst

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 trabalho deve ser enviado até as 23:00h do dia 05/05/2013. O termo de autoria assinado deve ser entregue pessoalmente ao professor no dia 06/05/2013 no horário da aula.

Avaliação

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