1ª Competição de Caminhos Mínimos do DECOM

[Regras] [Material] [Implementação] [Problemas] [Formato E/S] [Esqueletos] [Experimentos] [Datas] [Grupos] [Resultados]

Regras

Grupos de no máximo 3 pessoas
Os códigos serão checados quanto a sua corretude
Os programas devem respeitar o formado de Entrada e Saída definido
O código deve respeitar as regras de implementação
Serão premiados os 3 primeiros colocados, do seguinte modo:

nota do trabalho = nota máxima + 1
nota do trabalho = nota máxima + 0,5
nota do trabalho = nota máxima
os restantes serão avaliados de acordo com a correção normal de trabalhos

O grupo vencedor irá fazer uma apresentação para a turma descrevendo sua implementação

Material a ser entregue

Código em C, incluindo instruções para compilação. Essas instruções podem, por exemplo, indicar opções que devem ser usadas na compilação do código em C. (ex.: -O2 -ffast-math). Devem ser oferecidas as seguintes implementações:

Algoritmo de Dijkstra para para computação de c.m. de uma fonte para todos os outros vértices;

a fonte deve ser sorteada com a função rand a cada execução do algoritmo de Dijkstra dentro do programa.

Algoritmo Floyd-Warshall (FW) para computação dos caminhos mínimos de todos os vértices para todos os outros do grafo;

a implementação de FW deve incluir um teste para a existência de ciclos de custo negativo no grafo. Caso um seja encontrado, o algoritmo deve concluir imediatamente sua execução e indicar o ciclo encontrado.

Documentação impressa incluindo:

explicação da implementação, incluindo referências bibliográficas;
tabelas contendo os resultados dos experimentos realizados.

Regras de Implementação

Os códigos devem ser escritos em C, sem o uso de bibliotecas adicionais, exceto a biblioteca padrão da linguagem ou da biblioteca GNU.

Os seguintes padrões* C são aceitos:

ANSI C 89
ANSI C 99
GNU C

*O compilador GCC permite a compilação com validação de códigos com a flag -std. Ex.: (-std=c99).

Códigos com vazamento de memória ou problemas do tipo serão penalizados com -1 pontos. Os códigos serão testados com a ferramenta valgrind.

Problemas Teste*

Instância	Vértices	Arestas	Testar
rome99c.gr	3.353	8.859	Dijkstra
USA-road-d.NYc.gr.bz2	264.346	730.100	Dijkstra
rg300_768.gr	300	768	Floyd-Warshall
rg300_4730.gr	300	4.730	Floyd-Warshall
comp-2007-2-22c.gr.gz	600	276.666	Floyd-Warshall

* soluções devem ser checadas; caminhos mínimos pré-computados para rome99: spathsRome99c.gr.bz2 (lembre-se que entre dois nós pode haver mais de um caminho ótimo possível). outros: nspathsRg300_768.txt.bz2 .
* alguns problemas vieram da competição do DIMACS.

* problemas adicionais serão colocados nos próximos dias.

* os problemas teste para o algoritmo Floyd-Warshall (FW) podem incluir valores negativos nos custos dos arcos. A implementação de FW, quando encontrar um ciclo de custo negativo, deve abortar a computação e como saída deve somente indicar o caminho que indica o ciclo de custo negativo encontrado.

Formato de Entrada e Saída e Parâmetros

O programa deve receber os seguintes argumentos, quando chamado pela linha de comando:

prog <arquivoProblema> <nrExecuções> <flagDepuração>

Onde <flagDepuração> pode receber valor 0 ou 1. Como exemplo:

prog rome99.gr 1000 1

Indica que o programa irá ler o grafo do arquivo rome99.gr, executando o algoritmo de caminhos mínimos 1000 vezes e ao final irá imprimir/salvar informação de depuração.

A informação de depuração que deve ser gerada, quando solicitada, é a seguinte:

arquivo spaths.txt

O arquivo spaths.txt deve conter todos os caminhos mínimos computados para cada par de vértices (s,t), sendo s diferente de t . Cada linha contém a informação sobre o caminho mínimo de um par (s,t), no formato:

[s,t](dist) n1 n2 n3 ... nn

Onde:

s: nó fonte
t: nó destino
dist: distância calculada entre s e t
n1 n2 n3 ... nn: caminho computado entre s e t, incluindo todos os nós intermediários no formato: s n2 n3 ... t

Experimentos

Os experimentos computacionais para avaliação do código serão executados em um computador com as seguintes características:

Processador AMD Athlon II Dual-Core M320
2,7 Gigabytes de memória RAM
Linux, Kernel 2.6.32
GCC 4.4.3

Para cada problema teste, será considerado o tempo médio em 3 chamadas ao programa. Em cada uma das chamadas, será passado <nrExecuções> com valor suficiente para que o tempo total de cada chamada não seja inferior a 15 segundos. Finalmente, o tempo de cada execução será computado dividindo-se pelo parâmetro utilizado.

Datas

20 de setembro: início formal dos trabalhos

Indicação dos membros do grupo

6 de outubro: entrega obrigatória dos trabalhos para avaliação preliminar
18 de outubro: entrega da versão final dos trabalhos
20 de outubro: divulgação dos resultados

Avaliação

Será avaliado o tempo computacional que cada programa leva em cada um dos problemas disponibilizados. O tempo será medido com o comando time, disponível nos ambientes Unix, usando-se a média de 3 execuções seguidas. Em cada problema será feita uma ordenação dos resultados, iniciando pelo programa mais rápido. Nessa seqüência, cada programa receberá uma quantidade de pontos de acorto com sua posição na lista de resultados, do seguinte modo:

1º lugar: 25 pontos
2º lugar: 18 pontos
3º lugar: 15 pontos
4º lugar: 12 pontos
5º lugar: 10 pontos
6º lugar: 8 pontos
7º lugar: 6 pontos
8º lugar: 4 pontos
9º lugar: 2 pontos
10º lugar: 1 pontos

Esqueletos

Segue o esqueleto das implementações, de modo a ficaram em conforme com as necessidades acima descritas:

Dijkstra

dijkstra( arquivoGrafo, nrExecucoes, depurar )
{
   srand(0);      // inicializa semente gerador aleatório
   ler arquivoGrafo com n nós e m arcos
   se depurar nrExecuções = 1
   para i de 1 até nrExecuções faça:
   {
     se depurar
       s = 0
     senão
       s = rand()%n;
     calcule caminhos mínimos de s para todos os outros vértices do grafo
   }
   se (depurar)
     imprima caminhos mínimos descobertos considerando o último s sorteado
}

Floyd-Warshall

fwarshall( arquivoGrafo, nrExecucoes, depurar )
{
   ler arquivoGrafo
   se depurar nrExecuções = 1
   para i de 1 até nrExecuções faça:
   {
     calcule caminhos mínimos todos para todos os vértices do grafo
        caso encontre algum ciclo de custo negativo, guarde-o e aborte a execução;
   }
   se (depurar)
     imprima todos os caminhos mínimos descobertos, ou, no caso da
       existência de um ciclo de custo negativo, imprima o ciclo descoberto
}

Grupos

Grupo	Componentes
A	Filipe Danniel
B	Johnnatan Kayran Vitor
C	Aline Marcos Roger
D	Silmara Pollyanna
E	Alessander
F	Ademir Thiago Donizetti Lucas
G	Suellen Antonio Carlos
H	Bruno Saulo Victor Hugo
I	Marco Túlio Rafael Samuel
J	Néli
K	Fernando Thiago Luís Leandro