Esse projeto é um software open source para visualização de grafos feito em C++. O REPL pode ser usado para analises rápidas de propriedades de um grafo.
Para exemplos, assista ao vídeo.
- CMake 2.6+
- gcc & g++ 5.5+
- SFML 2.4+ (headers)
- TGUI 0.8 (headers)
Um script simples para Ubuntu 18.04+
sudo add-apt-repository ppa:texus/tgui-0.8
sudo apt-get update
sudo apt-get install libsfml-dev libtgui-dev
Ou utilizando o Dockerfile provido no repositório (preferencial).
# Boas práticas
mkdir build && cd build
# Gere os scripts de compilação de teste para sua plataforma
cmake ..
# Compilar
make
# Testar
make tests
# Gerar documentação em /docs
make docs
# Executar
make run
# Executar o REPL
make repl
O REPL possui dois tipos de comando: atribuição e operação.
>>> var1 = var2
A variável var1 passa a representar o grafo representado por var2.
>>> var = import file_name
A variável var passa a representar o grafo armazenado em file_name. Se a leitura do arquivo falhar, var passa a representar um grafo vazio.
>>> var1 = mst var2
A variável var1 passa a representar a árvore geradora mínima do grafo representado por var2.
>>> var > describe
Exibe informações sobre o grafo representado por var.
>>> var > show
Exibe o grafo representado por var.
>>> var > edit
Exibe o grafo representado por var, salvando as modificações efetuadas.
>>> var > reaches a b
Verifica se o vértice a alcança o vértice b no grafo representado por var.
>>> var > scc
Exibe as componentes fortemente conexas do grafo representado por var.
>>> var > shortestPath a b
Computa o peso do caminho mínimo do vértice a para o vértice b no grafo representado por var.
>>> var > coloring
Computa uma coloração mínima para var. O algoritmo é polinomial quando var é cordal e TODO quando não é.
>>> var > chromaticNumber
Computa o número cromático, i.e. o menor número de cores necessárias para se colorir o grafo. O algoritmo é polinomial quando var é cordal e TODO quando não é.
>>> var > greedyColoring
Computa uma coloração usando um algoritmo guloso na ordem dos vértices. Linear no tamanho do grafo.
>>> var > maximumCliqueSize
Computa o tamanho da clique máxima. Disponível apenas para grafos cordais.
>>> var > artPoints
Encontra os vértices cujas remoções aumentam o número de componentes conexas do grafo.
>>> var > bridges
Encontra as arestas cujas remoções aumentam o número de componentes conexas do grafo.
>>> var > topoSort
Encontra uma ordenação topológica dos vértices do grafo.
>>> var > center
Computa o centro da árvore var.
>>> var > diameter
Computa o diâmetro da árvore var.
>>> var > matching
Computa o matching máximo do grafo.
>>> var > tikz file [scale]
Exporta o grafo em formato tikz para LaTeX no arquivo 'file'. O campo 'scale' é opcional, e altera a escala da imagem.