Implementação do Algoritmo de Johnson, com a biblioteca igraph do Python, para identificar todos os ciclos existentes em um grafo direcionado.
Código fonte utilizado no trabalho "Conflito de Interesses (Lei 12.813/2013): Contratos, Parentes e Grafos", apresentado no 7º Seminário Internacional sobre Análise de Dados na Administração Pública, em 22/10/2021 (Vídeo da Apresentação no YouTube).
python -m busca_ciclos_no_grafo <csv_edges_input> <txt_cycles_output> [<cycle_limit_length> <cycle_limit_node_type>]
[INPUT] Caminho do arquivo CSV das arestas do grafo.
[OUTPUT] Caminho do arquivo TXT com os ciclos identificados.
[OPCIONAL] Número limite de vértices do ciclo. Caso não seja informado, serão buscados ciclos de qualquer tamanho.
[OPCIONAL] Tipo do vértice a ser considerado na contagem do "cycle_limit_length". Caso não seja informado, serão considerados vértices de qualquer tipo.
python -m busca_ciclos_no_grafo ./edges.csv ./cycles.txt
python -m busca_ciclos_no_grafo ./edges.csv ./cycles.txt 8
python -m busca_ciclos_no_grafo ./edges.csv ./cycles.txt 2 C
- igraph
O arquivo sample.csv é um exemplo do CSV das arestas do grafo (argumento csv_edges_input), a partir de dados simulados.
O caderno (Jupyter Notebook) Demonstracao.ipynb contém uma demonstração da identificação de ciclos no grafo instanciado com os dados de sample.csv.