O problema do Carteiro Chinês

Trabalho de Conclusão de Curso desenvolvido por Gabriel Fernandes de Oliveira no ano de 2020, com a orientação do Prof. Carlos Eduardo Ferreira.

Para mais informações sobre o desenvolvimento deste trabalho acesse a página linux.ime.usp.br/~gafeol/mac0499/.

Compilando o documento

Para conseguir compilar o latex, é necessário instalar os seguintes pacotes:

texlive-latex-base
texlive-lang-portuguese
texlive-science
texlive-bibtex-extra
biber

Depois de instalados, basta rodar make que o pdf será compilado, e os arquivos auxiliares serão deletados.

Organização

Arquivos LaTeX

Os arquivos LaTeX estão todos dispostos na pasta tex.

O documento principal é o main.tex, que tem todas as importações de pacotes e arquivos auxiliares além do resumo do trabalho, em português e inglês.

Cada capítulo da monografia tem um arquivo .tex dedicado presente na pasta capitulos/:

• euler.tex trata da teoria de caminhos eulerianos.
• pcc.tex possui o texto principal, sobre o problema do carteiro chinês e suas variantes.
• code.tex serve como uma referência para o código desenvolvido, explicando complexidade de soluções e organização de algoritmos.
• prb.tex contém o capítulo de apêndice, que trata de 3 problemas resolvidos relacionados aos temas tratados no trabalho.

Usou-se BibTex para formatar as citações do trabalho. No arquivo ref.bib estão configuradas todas referências bibliográficas da monografia.

Código

Os arquivos de código estão dispostos na pasta code/, e seus respectivos testes se encontram na pasta test/.

Todos os códigos foram desenvolvidos usando C++17.

A implementação do Emparelhamento Perfeito Mínimo foi baseada na implementação de Dilson Pereira e adaptada para esse projeto em um fork próprio.

A implementação do algoritmo de Chu-Liu para encontrar a arborescência geradora mínima em um digrafo foi baseada na implementação do time "el-vasito" disponibilizada em seu caderno de referência para a ICPC.

Testes de Código

Os testes foram desenvolvidos usando a ferramenta "googletest" da Google.

Para entender os usos básicos e motivações de se usar o googletest, segue essa apresentação.

Para realizar os testes, certifique-se de que a pasta test/gtest foi devidamente clonada. Se a mesma estiver vazia, basta cloná-la usando o comando:

git clone [email protected]:google/googletest.git test/gtest

Após isso, basta rodar make -C test que todos os testes serão executados.

Se desejar rodar apenas um conjunto específico de testes, inclua o nome do conjunto desejado após o make, por exemplo:

# Para rodar os testes de grafos nao direcionados
make grafo -C test/
make graph -C test/

# Para todar os testes de emparelhamento
make matching -C test/

Cobertura de testes

Para checar a cobertura de testes manualmente, primeiramente configure a variável de ambiente CODECOV_TOKEN. Minha sugestão é adicioná-la a um arquivo secret, ignorado pelo github, no formato:

export CODECOV_TOKEN=aaaaaaaa-aaaa-aaaa-aaaa-aaaaaaaaaaaa

Após isso basta rodar source secret.

Tendo definida tal variável, pode-se testar manualmente a cobertura dos testes rodando:

make -C test/
bash <(curl -s https://codecov.io/bash) -t $CODECOV_TOKEN

Se o comando rodou como esperado, a última linha do mesmo deverá ser da forma:

[...]
-> View reports at https://codecov.io/github/gafeol/chinese-postman/commit/f81abd57f0e0238709a4000cd179163b32124ddb

Acessando o link dado pode-se observar o resultado de cobertura dos testes atualmente adicionados ao projeto. Este teste de cobertura nos oferece informações muito importantes, como por exemplo: quais linhas de código nunca foram executadas nos testes.