Projeto de Gradução no curso de Ciência da Computação (PGC) da UFABC. Visa ser um pacote Python com implementação de alguns algoritmos para o problema de coloração em grafos. O PGC é desenvolvido por Wesley Lima de Araujo e orientado pela Professora Doutora Carla Negri Lintzmayer. O projeto dá continuidade a um trabalho de Iniciação Científica (IC) já desenvolvido por aluno e orientadora sobre o mesmo tema, porém, o enfoque da IC era um estudo teórico.
Para desenvolvimento do pacote está sendo usada a ferramenta Poetry que automatiza uma parte considerável dos processos de criar e atualizar um pacote disponível no PyPi. Para usar o pacote instale-o usando pip pip install graphcol
.
Algoritmos já implementados no pacote:
- Algoritmos de coloração heurísticos gulosos:
- Guloso
- DSatur
- RLF
- Algoritmos de coloração metaheurísticos:
- Coloração Tabu
- Hill-Climbing
- Evolucionário Híbrido
- Colônia de Formigas
- Algoritmos exatos:
- Lawler
Controle semântico das versões: x.y.z
, já avisando que não segue o versionamento semântico padrão.
x
-> Versão major, passará a contar 1 na primeira entrega final da biblioteca (todos os algoritmos listados implementados).y
-> Versão minor, alterada quando algum algoritmo/funcionalidade novo for implementado com sucessoz
-> Versão patch, atualizada na correção de falhas e/ou adição de testes
Controle de versões:
0.4.0
-> Implementação do DSatur exato, testes pré-lançamento oficial
Como já dito, estamos usando o framework Poetry para automatizar boa parte das atividades necessárias para a publicação do pacote.
Seguem os principais comandos usados na publicação de uma nova versão do pacote:
poetry check
(Verifica se o .toml do projeto está OK)poetry build
(Builda os arquivos .tar.gz e .whl da versão)poetry publish
(Publica o pacote no PyPi)
Para realização dos testes unitários dos algoritmos utilizamos a ferramenta pytest que fornece diversas funcionalidades para facilitar o teste de funções e classes implementadas na linguagem Python.
Os testes realizados aqui visavam assegurar o bom funcionamento dos algoritmos implementados através da validação da qualidade da solução. Por exemplo, o algoritmo DSatur tem garantia matemática que para grafos bipartidos o resultado devolvido é exato, então sua implementação é testada com alguns grafos bipartidos e se nenhum deles foge desse resultado. Também temos algumas das heurísticas que apresentam garantia que o resultado devolvido é sempre uma solução viável, esse é outro teste que realizamos.
Até o momento as seguintes implementações possuem testes unitários sobre instâncias de grafos:
- Guloso
- DSatur
- RLF
- TabuCol
- Hill-Climbing
- Evolucionário
- Colônia
Para entender melhor os testes veja as definições dos casos nos arquivos dentro da pasta teste
. São os arquivos com nome começando em test_
.
Outra etapa do projeto de PGC é a realização de experimentos com os algoritmos implementados. Para realizar esses testes usaremos Jupyter Notebooks que encontram-se na pasta experimentos.
Os testes serão realizados sobre o benchmark do DIMACS que disponibiliza cerca de 80 instâncias do problema de coloração de grafos. Algumas dessas instâncias já possuem o número cromático do grafo. Dentre essas instâncias disponibilizadas nesse branchmark 20 foram escolhidas para realização dos experimentos com os algoritmos implementados na biblioteca. As instâncias usadas encontram-se na pasta experimentos -> instancias
Cada grafo encontra-se em arquivos de texto no padrão DIMACS para problemas de coloração de grafos. Na pasta de experimentos, basta executar o script instancias.sh
que baixa e descompacta um .tar
com as instâncias.
Para adicionar ambiente virtual como kernel dos notebooks:
- Ative o ambiente virtual -
source experimentos_graphcol/bin/activate
- Adicione o ambiente virtual aos kernels -
python3 -m ipykernel install --user --name=experimentos_graphcol
- Installe os pacotes dependências -
pip install -f requirements.txt
- Abra o JupyterLab -
jupyter lab
Segue uma breve descrição de cada um dos arquivos componentes desse repositório.
graphcol
├── experimentos --> Pasta com experimento e análise experimental
│ ├── analises.ipynb --> Notebook com análises realizadas
│ ├── instancias --> Pasta com instâncias utilizadas nos experimentos
│ │ ├── anna.col
│ │ ├── david.col
│ │ ├── games120.col
│ │ ├── homer.col
│ │ ├── huck.col
│ │ ├── instancias.sh
│ │ ├── jean.col
│ │ ├── miles1000.col
│ │ ├── miles250.col
│ │ ├── miles500.col
│ │ ├── miles750.col
│ │ ├── myciel3.col
│ │ ├── myciel4.col
│ │ ├── myciel5.col
│ │ ├── myciel6.col
│ │ ├── queen5_5.col
│ │ ├── queen6_6.col
│ │ ├── queen7_7.col
│ │ ├── queen8_12.col
│ │ ├── queen8_8.col
│ │ └── queen9_9.col
│ ├── requirements.txt --> Dependências usadas na análise experimental
│ ├── resultados --> Pasta com resultados do experimento
│ │ ├── Dados experimento - Metaheurísticas.csv
│ │ └── Dados experimentos - Gulosos.csv
│ └── testes_gulosos_metaheuristicos.py --> Código do experimento
├── graphcol --> Pasta base do pacote
│ ├── dist --> Pasta com objetos do pacote
│ ├── graphcol --> Pasta com implementações em código
│ │ ├── exatos.py --> Implementações dos algoritmos exatos
│ │ ├── gulosos.py --> Implementações dos heurísticas gulosas
│ │ ├── __init__.py
│ │ ├── metaheuristicas.py --> Implementações das metaheurísticas
│ │ └── visual.py --> Implementação de componente para visualizar coloração
│ ├── poetry.lock --> Lock de dependências usadas no desenvolvimento
│ ├── pyproject.toml --> Arquivo de configuração do pacote
│ └── README.rst --> Arquivo de documentação no PyPi
├── LICENSE --> Arquivo com licença do projeto
├── README.md --> Arquivo README do projeto com documentação básica
└── testes --> Pasta com testes unitários do projeto
├── grafos_aleatorios.py
├── __pycache__
│ ├── grafos_aleatorios.cpython-39.pyc
│ ├── test_exatos.cpython-39-pytest-7.2.0.pyc
│ ├── test_gulosos.cpython-39-pytest-7.2.0.pyc
│ └── test_metaheuristicos.cpython-39-pytest-7.2.0.pyc
├── test_exatos.py
├── test_gulosos.py
└── test_metaheuristicos.py