Para a representação de grafos na entrada e saída ao longo da disciplina vamos utilizar a linguagem de descrição de grafos dot que é implementada pelo pacote de software GraphViz.
Para uma amostra da linguagem dot veja esta galeria de grafos.
A biblioteca cgraph implementa (entre outras coisas) uma estrutura de dados para a manipulação de grafos e um interpretador ("parser") da linguagem dot.
O pacote GraphViz é distribuido livremente para diversas plataformas.
Em particular, nas distribuições de GNU/Linux baseadas na distribuição Debian, basta instalar o pacote libgraphviz-dev. Recomenda-se também instalar os pacotes graphviz (utilitários, especialmente para desenhar grafos) e graphviz-doc (documentação adicional). Estes pacotes estão instalados nos servidores da rede do Departamento de Informática.
O objetivo deste trabalho é implementar um programa para a decomposição de um grafo em seus blocos (subgrafos maximais sem vértices de corte).
O programa deve ler um grafo da entrada padrão e deve escrever na saída padrão os seus blocos, um bloco por linha.
Cada bloco deve deve ser escrito como uma lista de (nomes de) vértices em ordem (lexicográfica) crescente, todos na mesma linha, separados por brancos.
Por exemplo, a saída correspondente ao grafo exemplo.dot é
d b f a h i a c g e g
Observe que as linhas (blocos) podem estar em qualquer ordem mas os vértices em cada linha (bloco) devem estar em ordem crescente.
O trabalho deve ser entregue sob a forma de um arquivo de nome fulano.tar.gz, onde fulano é o login name do autor.
O arquivo fulano.tar.gz, uma vez expandido, deve criar (somente) os seguintes arquivos.
| fulano/readme.txt: | |
|---|---|
| arquivo que deve ser usado para comunicar tudo que seja relevante para a correção do trabalho. | |
| fulano/blocos.c: | |
| a implementação, que deve ser feita em linguagem C. | |
A correção será feita a partir da compilação com este makefile.
O arquivo fulano.tar.gz deve ser entregue como anexo de mensagem enviada para renato.carmo.rc@gmail.com. O "Subject:" desta mensagem deve ser "Entrega do trabalho".
O prazo para a entrega é 25/2/2023, às 23h59min.
O trabalho não é obrigatório. A média final dos alunos que não entregarem o trabalho será a média das notas obtidas nas provas; A média final dos alunos que entregarem o trabalho será a média da nota do trabalho (com peso 30%) somada à média das notas obtidas nas provas (com peso 70%).
O trabalho pode ser feito em grupo?
Não, o trabalho deve ser feito individualmente.
Descobri um erro depois que entreguei o trabalho. Posso entregar uma versão corrigida?
Você pode entregar o trabalho mais de uma vez. A última versão entregue dentro do prazo é a que será corrigida.
Meu trabalho tem um bug. O que vai acontecer com minha nota?
Haverá algum desconto, dependendo da gravidade do bug. O desconto será menor se o bug for relatado no arquivo readme.txt, indicando que você estava ciente do problema quando entregou.
Tenho outra pergunta/dúvida a respeito do trabalho.