IA - 2 atividade: Buscas Largura e profundidade com plotagem gráfica

import networkx as nx
import matplotlib.pyplot as plt
from queue import Queue

colormap = []
escolhidos = []
colormapescolhidos = []
dicionario = {}
G = nx.Graph()
varx = vary = 0

class GraphLargura:
    def __init__(self, num_of_nodes, directed=True):
        self.m_num_of_nodes = num_of_nodes
        self.m_nodes = range(self.m_num_of_nodes)
        self.m_directed = directed
        self.m_adj_list = {node: set() for node in self.m_nodes}

    def add_edge(self, node1, node2, weight=1):
        self.m_adj_list[node1].add((node2, weight))
        if not self.m_directed:
            self.m_adj_list[node2].add((node1, weight))

    def print_adj_list(self):
        for key in self.m_adj_list.keys():
            print("node", key, ": ", self.m_adj_list[key])

    def bfs(self, start_node, target_node):
        visited = set()
        queue = Queue()
        queue.put(start_node)
        visited.add(start_node)
        parent = dict()
        parent[start_node] = None
        path_found = False
        while not queue.empty():
            current_node = queue.get()
            if current_node == target_node:
                path_found = True
                break
            for (next_node, weight) in self.m_adj_list[current_node]:
                if next_node not in visited:
                    queue.put(next_node)
                    parent[next_node] = current_node
                    visited.add(next_node)
        path = []
        if path_found:
            path.append(target_node)
            while parent[target_node] is not None:
                path.append(parent[target_node])
                target_node = parent[target_node]
            path.reverse()
        return path

class GraphProfundidade:
    def __init__(self, num_of_nodes, directed=True):
        self.m_num_of_nodes = num_of_nodes
        self.m_nodes = range(self.m_num_of_nodes)
        self.m_directed = directed
        self.m_adj_list = {node: set() for node in self.m_nodes}

    def add_edge(self, node1, node2, weight=1):
        self.m_adj_list[node1].add((node2, weight))
        if not self.m_directed:
            self.m_adj_list[node2].add((node1, weight))
    def print_adj_list(self):
        for key in self.m_adj_list.keys():
            print("node", key, ": ", self.m_adj_list[key])

    def dfs(self, start, target, path=[], visited=set()):
        path.append(start)
        visited.add(start)
        if start == target:
            return path
        for (neighbour, weight) in self.m_adj_list[start]:
            if neighbour not in visited:
                result = self.dfs(neighbour, target, path, visited)
                if result is not None:
                    return result
        path.pop()
        return None

#Entrada
x = str(input("Digite o tipo de grafo:\n1- Largura; 2- Profundidade \n"))
qntNodos = int(input("Digite a quantidade de nodos: "))
for i in range(qntNodos):
    G.add_node(i)

#Seleção do tipo de busca
if x == "1":
    graph = GraphLargura(qntNodos, directed=False)
elif x == "2":
    graph = GraphProfundidade(qntNodos, directed=False)
else:
    exit()

#Entrada com nome dos nodos, escolhido pelo usuario
for nomes in range(qntNodos):
    entrada = str(input("Digite o nome da variável: "))
    dicionario[nomes] = entrada

#Ligações entre os nodos do grafo
choice = str(input("Como quer fazer as ligações: \n1- Digitando o nome atribuido a cada nodo:(Formato: FeiraNova Recife) "
                   "\n2- Via números:(Formato: 0,1) "))
while True:
    if choice == "1":
        j = str(input("Digite as ligações dos nodos(Formato: FeiraNova Recife)*Para palavras compostas, "
                      "digite a palavra toda junta sem dar espaços* \n(Digite 0 para terminar as entradas): "))
        if j == "0":
            break
        j.lower().lstrip().rstrip()
        j = j.split()
        for k in range(qntNodos):
            if j[0] == dicionario.get(k):
                varx = k
        for k in range(qntNodos):
            if j[1] == dicionario.get(k):
                vary = k
        graph.add_edge(varx, vary)
        G.add_edge(varx, vary)
    else:
        j = str(input("Digite as ligações dos nodos(Formato: 0,1) \n(Digite 0 para terminar as entradas): "))
        if j == "0":
            break
        graph.add_edge(int(j[0]), int(j[2]))
        G.add_edge(int(j[0]), int(j[2]))

#Ponto de inicio e alvo de busca
print("Nó criados: ")
print(dicionario)
inicial = str(input("Digite o nodo inicial(Start da busca) e o nodo final(Alvo da busca): \n(Formato: FeiraNova Recife): "))
path = []
inicial.lower().lstrip().rstrip()
inicial = inicial.split()
for k in range(qntNodos):
    if inicial[0] == dicionario.get(k):
        varx = k
for k in range(qntNodos):
    print(k)
    if inicial[1] == dicionario.get(k):
        vary = k
if x == "1":
    path = graph.bfs(varx, vary)
else:
    path = graph.dfs(varx, vary)
escolhidos.append(varx)
escolhidos.append(vary)

#Alterar a cor do nodo após a busca ser realidada
for node in G:
    if node not in path:
        colormap.append('blue')
    else:
        colormap.append('red')

#Alterar a cor do nodo só com os alvos da busca
for node in G:
    if node not in escolhidos:
        colormapescolhidos.append('blue')
    else:
        colormapescolhidos.append('yellow')

#Renomear cada nodo com nome inserido pelo usuario
G = nx.relabel_nodes(G, dicionario)

#Saidas para PNG
pos = nx.spring_layout(G,seed=123456789,k=0.3)
nx.draw_networkx(G, with_labels=True, node_size=1200, node_color='blue', pos=pos)
plt.savefig("GrafoCompleto.png")
plt.close()
nx.draw_networkx(G, node_color=colormap, with_labels=True, node_size=1200, pos=pos)
plt.savefig("GrafoComCaminhoDefinido.png")
plt.close()
nx.draw_networkx(G, node_color=colormapescolhidos, with_labels=True, node_size=1200, pos=pos)
plt.savefig("GrafoEscolhido.png")

#Saida Para HTML
rota = []
g1 = "GrafoCompleto.png"
g2 = "GrafoComCaminhoDefinido.png"
g3 = "GrafoEscolhido.png"
gif = "https://upload.wikimedia.org/wikipedia/commons/5/5d/Breadth-First-Search-Algorithm.gif"
fonte = 5
for k in range(len(path)):
    rota.append(str(dicionario.get(path[k])) + " > ")
if x == "1":
    escolha = "Busca em Largura"
else:
    escolha = "Busca em profundidade"
style = "float:right;width:200px"
saidaHtml = open("GrafoSaidaHTML.html", "w+", encoding="utf-8")
saidaHtml.writelines(f"<html>"
                     f"     <head>"
                     f"         <tittle>"
                     f"             Segunda Entrega IA"
                     f"         </tittle>"
                     f"     </head>"
                     f"     <body>"
                     f"          <img src={gif} style={style}>"
                     f"          <font size={fonte}><br>Saída do grafo de entrada: <br>Tipo de busca: {escolha}</font> <br />"
                     f"          <p> PS.: As imagens podem divergir na posição dos nodos"
                     f" se comparado com a outra imagem. Entretanto, ambas correspondem ao mesmo grafo, apenas desenhado"
                     f" de uma forma diferente. </p>"
                     f"          <p> Grafo completo: </p>"
                     f"          <img src={g1}>"
                     f"          <p> Grafo com o inicio e o alvo de busca selecionados: Inicio:{dicionario.get(path[0])}"
                     f" final: {dicionario.get(path[len(path) - 1])}</p>"
                     f"          <img src={g3}>"
                     f"          <p> Grafo com Caminho definido -> Rota do caminho> {rota}: </p>"
                     f"          <img src={g2}>"
                     f"     </body>"
                     f"</html>")
saidaHtml.close()