MC558 - Lab L4

Diretrizes

• Objetivo: Dado um grafo planar, encontrar uma 5-coloração própria para seus vértices.
• Submissão: Devem ser enviados os seguintes arquivos:
  • Arquivo JSP: a ser desenvolvido durante a aula de laboratório do dia 17/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é quinta-feira (01/11), como resposta ao e-mail em que foi enviado o JSP.
• Implementação: 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é quinta-feira (01/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 está um exemplo de submissão.
• Entrada: o único parâmetro do programa é o nome do arquivo que especifica um grafo planar no formato do Lemon.
• Saída: a resposta é dada pela saída padrão (std::cout). Deve ser impressa uma 5-coloração própria do grafo de entrada, obedecendo as seguintes regras:
  • Uma linha por vértice;
  • Cada linha deve conter: o rótulo do vértice e uma cor, separados por um tab ("\t");
  • Os rótulos dos vértices devem ser os mesmos da entrada (coluna "rotulo" do arquivo de entrada);
  • As cores devem ser inteiros, por exemplo, {0, 1, 2, 3, 4} ou {1, 2, 3, 4, 5}
  No arquivo em anexo há um exemplo 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 pequenos. 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 e (2) estipulamos um timeout de 10 segundos por caso de teste. Em breve será incluído o teste automático com todas as instâncias oficiais (40 ao total), onde ajustaremos o timeout se necessário.