MC558 - Lab L5

Diretrizes

Objetivo: Dado um grafo simples, encontrar uma (Δ+1)-coloração própria para suas arestas, onde Δ é o grau máximo do grafo.
Submissão: Devem ser enviados os seguintes arquivos:
- Arquivo JSP: a ser desenvolvido durante a aula de laboratório do dia 31/10. Deve ser enviado para o e-mail divulgado na sala, com a tag "[MC558] Lab04", até o final da aula de laboratório.
- complexidade.pdf: arquivo que descreve a complexidade do algoritmo implementado. Neste arquivo também devem estar as diferenças entre o JSP e a implementação (se houver). Deve ser enviado até quarta-feira (21/11), como resposta ao e-mail em que foi enviado o JSP.
- código: conjunto de arquivos *.cpp e *.h, além de um makefile, que devem ser submetidos via servidor (página a ser divulgada; o login é o mesmo usado nos labs anteriores). A submissão deve ser feita até quarta-feira (21/11) às 23:59. Ao submeterem, vocês devem organizar todos os arquivos *.cpp e *.h dentro de um arquivo .zip. O arquivo .zip também deve conter um arquivo makefile para compilar o código. Em anexo há dois exemplos de submissão (lab05.zip e lab05-pli.zip).
Implementação:
Entrada: o único parâmetro do programa é o nome do arquivo que especifica um grafo simples no formato do Lemon.
Saída: a resposta é dada pela saída padrão (std::cout). Deve ser impressa uma (Δ+1)-coloração própria das arestas do grafo de entrada, obedecendo as seguintes regras:
- Uma linha por aresta;
- Cada linha deve conter: o rótulo da aresta e uma cor, separados por um tab ("\t");
- Os rótulos das arestas devem ser os mesmos da entrada (coluna "label" do arquivo de entrada);
- As cores devem ser inteiros, por exemplo, {0, 1, 2, 3, ...} ou {1, 2, 3, 4, ...}
Nos arquivos em anexo há exemplos de como deve ser impressa a resposta.
Testes: Durante a submissão é possível testar se o programa está funcionando corretamente. Para isso, o programa é executado com 10 casos de teste abertos. Como a resposta é computada no momento da submissão, algumas medidas foram tomadas para que o usuário não fique esperando muito tempo por uma resposta: (1) somente um subconjunto dos casos de teste oficiais é executado (10 de um total de 40) e (2) estipulamos um timeout de 10 segundos por caso de teste.

Critérios de Avaliação: A nota da atividade será a soma das notas obtidas em cada um dos critérios abaixo:

JSP: clareza e corretude. Nota entre 0-5. Também determina quem será Série A (metade ou mais da nota máxima) e Série B (os restantes).
Corretude da Implementação: número de casos de teste executados corretamente. Nota entre 0-3.
Running time: será feita uma lista em ordem decrescente do tempo de execução médio para resolver uma instância (tempo total / núm. acertos). Os trabalhos serão separados em dois grupos: Série A, que competirá pelas notas mais altas, e Série B. Nota entre 0-1.
Complexidade do algoritmo: verificar se a análise de complexidade do algoritmo está correta (arquivo complexidade.pdf). Nota entre 0-1.

Curiosidade: Não encontramos uma função do Lemon para computar coloração de arestas. Será que existe? Para contornar isso, implementamos dois métodos: (1) um exato ("lab05-pli.zip"), que usa o resolvedor de programação inteira do Lemon, mas que funciona só para casos bem pequenos, e requer que se instale o pacote glpk antes; (2) uma heurística ("lab05.zip"), que começa colorindo as arestas incidentes em vértices de maior grau.

Notas

	Pesos:	5	1	1	3
		JSP	Complexidade	Running Time	Corretude	Nota Final
101977	Davi Stuart Zilli	4	0	0	0	2
102113	Eric Carvalho Oakley	6	0	0	0	3
108171	Fabiani de Souza	8.5	0	0	0	4.25
104941	Flávia Pisani	10	10	9	9.5	9.75
103147	Lucas Gasparetto Farris	10	0	0	0	5
108227	Maurício Bertanha	8.5	0	0	0	4.25
103958	Renato Tadeu Lochetti	7.5	0	0	0	3.75
106991	Waldir Rodrigues de Almeida	9	10	10	10	9.5

MC558 Home