Grafos

Aplicação, desenvolvida em Python 3.10.4, com o principal foco na utilização e, também, manipulação de Grafos.

Índice

Instalação
Tipos de Grafos suportados
Implementações feitas
Modelos de arquivos de entrada
Criando grafos
Aplicando Teoremas em grafos
Fazendo Buscas em grafos
Gerando Árvores
Otimizando Rotas
Licença

1) Instalação

Não tem nada muito complexo, basta baixar os arquivos e usá-lo.

2) Tipos de Grafos suportados

Você pode criar-los utilizando a classe "Graph.py"

3) Implementações feitas

1. Na classe "Graph"

Matriz de adjacência
Grau/Valência de vértices
Busca de vértices
Busca de arestas
Densidade do grafo
Frequência do grafo
Adição e/ou Remoção de vértices
Adição e/ou Remoção de arestas
Peso de uma aresta
Verificação de existência de arestas e vértices
Tradução de rótulo para índice e vice-versa
Busca por adjacentes de determinado vértice
Busca por vértices de grau máximo e mínimo
Busca por vértices de determinado grau
Criação de grafos a partir da leitura de arquivos JSON

2. Na classe "Hamiltonian"

Fecho Hamiltoniano
Teorema de Dirac
Teorema de Ore
Teorema de Bondy Chvatal

3. Na classe "Euler"

Verificação de grafos Eulerianos
Verificação de grafos Semi-Eulerianos
Circuito Euleriano

4. Na classe "BreadthFirstSearch"

Busca em Largura (BFS)
Nível dos vértices (BFS)
Árvore Geradora (BFS)

5. Na classe "DepthFirstSearch"

Busca em Profundidade (DFS)
Nível de profundidade dos vértices (DFS)
Árvore de Profundidade (DFS)

6. Na classe "ShortestMinimumPath"

4) **Modelos de arquivos de entrada (JSON)**

Segue, abaixo um simples modelo de um grafo 3-regular, com 4 (quatro) vértices.

{
    "Vertexes": [
        ["A", "B", "C", "D"]
    ],
    "Edges": [
        ["A", "B"], ["A", "C"], ["A", "D"],
        ["B", "A"], ["B", "C"], ["B", "D"],
        ["C", "A"], ["C", "B"], ["C", "D"],
        ["D", "A"], ["D", "B"], ["D", "A"]
    ]
}

É bem simples na verdade, na chave "Vertexes" você insere os vértices, os seus rótulos, que o grafo possui e na chave "Edges", você coloca os arcos que o grafo contem, por exemplo: ["A", "B"], indica um arco, saindo de "A" e indo até "B" com peso 1, pois nenhum peso foi fornecido (em casos como esse, o valor 1 é atribuído por padrão), para definir arcos com pesos, basta inserir um novo elemento, o qual indicará o peso do arco, ou seja: ["A", "B", 3], que, por fim, criaria um arco, saindo de "A" e indo até "B", com um peso de 3.

5) Criando grafos

Caso preferir, você pode criar, também, grafos utilizando os próprios métodos da classe "Graph".

Criaremos, novamente, um grafo 3-regular de 4 (quatro) vértices, por exemplo:

# Inicializamos a classe Graph.
graph = Graph()

# Adicionamos os 4 (quatro) vértices "A", "B", "C" e "D".
graph.add_vertexes(("A", "B", "C", "D"))

# Adicionamos os arcos.
graph.add_edge_undirected(("A", "B")) # A <--> B
graph.add_edge_undirected(("A", "C")) # A <--> C
graph.add_edge_undirected(("A", "D")) # A <--> D
graph.add_edge_undirected(("B", "C")) # B <--> C
graph.add_edge_undirected(("B", "D")) # B <--> D
graph.add_edge_undirected(("C", "D")) # C <--> D

# Caso queira adicionar peso aos arcos, basta passar um segundo 
# parâmetro na função "add_edge_undirected", o qual representaria o peso.
# Ex:. graph.add_edge_undirected(("A", "C"), 3)

E pronto! você criou um grafo.

6) Aplicando Teoremas em grafos

-"Legal, temos um grafo, mas como faço para aplicar teoremas nele?"

# Com o grafo montado, basta incializar a classe desejada, passando
# o grafo criado como parâmetro durante sua inicialização.
graph = Graph()
# ... criação do grafo.

# "Hamiltonian" para teoremas hamiltonianos.
# "Euler" para teoremas eulerianos.
hamiltonian = Hamiltonian(graph)
euler = Euler(graph)

# Para aplicar o Teorema de Dirac:
hamiltonian.is_graph_dirac()

# Para aplicar o Teorema de Ore:
hamiltonian.is_graph_ore()

# Para aplicar o Teoream de Bondy Chvatal:
hamiltonian.is_graph_bondy()

# Para aplicar o Teorema Euleriano:
euler.is_graph_euler()

# Para aplicar o Teorema Semi-Euleriano.
euler.is_graph_semi_euler()

Pronto! você aplicous os teoremas no grafo.

7) Fazendos Buscas em grafos

Seguindo a mesma lógica, para aplicar as buscas em um grafo basta:

# Com o grafo montado, basta inicializar a classe desejada, passando
# o grafo criado como parâmetro durante sua inicialização.
graph = Graph()
# ... criação do grafo.

# Inicializamos o "BFS", para as buscas em largura.
bfs = BreadthFirstSearch(graph)

# Para realizar a Busca em Largura, você deve definir um ponto de 
# partida, pode ser um vértice qualquer do grafo. 
bfs.apply_bfs("A")

# Inicializamos o "DFS, para as buscas em profundidade.
dfs = DepthFirstSearch(graph)

# A ideia para a Busca em Profundidade é as mesma da BFS, basta
# chamar o método e passar um ponto de partida.
dfs.apply_dfs("A")

Pronto! você fez buscas em um grafo.

8) Gerando árvores

"Depois de brincar com as buscas em largura/profundidade, você resolve montar suas árvores."

# Com o grafo montado e as classes inicializadas (DFS ou BFS).
graph = Graph() 
# ...
bfs = BreadthFirstSearch(graph)
# ...
dfs = DepthFirstSearch(graph)
# ...

# Em ambas as funções, para geração de árvore, um ponto de partida
# deve ser passado como parâmetro, pois o própria método irá aplicar
# a busca no grafo fornecido e, a partir daí, gerará á Árvore.

# Basta chamar seus métodos e passar, também, um ponto de partida.
bfs.get_bfs_tree("A") # Retorna um objeto "Graph", representando a Árvore.

# Para a Árvore do DFS.
dfs.get_dfs_tree("A") # Retorna um objeto "Graph", representando a Árvore.

Pronto! você gerou grafos em árvores a partir de uma busca.

9) Otimizando Rotas

Sim, você pode obter rotas de custo mínimo, tanto para custos não-negativos como, também, para custos negativos e positivos.

# Com o grafo montado, basta inicializar a classe, passando o grafo como parâmetro.
graph = Graph()
# ... criação do grafo.

# Inicializamos a classe responsável pelos algoritmos de caminho mínimo.
smp = ShortestMinimumPath(graph)

# Em ambos os métodos, você deve fornecer, é claro, um ponto de partida.

# Aqui você pode escolher qual algoritmo usar:
# 1) Algoritmo de Dijkstra.
smp.apply_dijkstra_algorithm("A")

# 2) Algoritmo de Bellman-Ford.
smp.apply_bellman_ford_algorithm("A")

# 3) Algoritmo de Floyd-Warshall.
smp.apply_floyd_warshall_algorithm()

# O retorno dos métodos é, basicamente, o caminho percorrido e o custo
# de cada arco percorrido.

10) Licença

Esse projeto está sob licença. Veja o arquivo LICENÇA para mais detalhes.

JLMSC/Grafos