I need to fix my Python Graph class to simulate a dictionary

Asked

Viewed 144 times

2

Hello, I am trying to fix my graph class to use as a dictionary further forward, but from what I understand it is only accessing the memory location instead of the data, in the example below I will leave my graph class and the method I need to usela, I would like to change the class instead of the method, because I will need to use several other methods with that same structure.

Class below:

class node:
    def __init__(self, label):
        self.label = label


class grafo:
    def __init__(self):
        self.ligacoes = {}

    def imprimir(self):
        for a in self.ligacoes:
            print("(",a.label, end="")
            print(" -> ",end="")
            for b, c in self.ligacoes[a].items():
                print("[",b.label,":",c,"]",end=",")
            print(")")


    def inNode(self, label):
        novo = node(label)
        self.ligacoes[novo] = {}
        #self.imprimir()

    def removNode(self, label):
        removido = None
        for no in self.ligacoes.keys():
            if no.label == label:
                self.ligacoes.pop(no)
                removido = no
                break
        #self.imprimir()
        return removido

    def limparGrafo(self):
        self.ligacoes.clear()

    def inAdj(self, origem, destino, peso):
        if type(peso) != int:
            print("o peso deve ser int")
        else:
            existeOrigem = False
            existeDestino = False
            for no in self.ligacoes:
                if no.label == destino:
                    existeDestino = True
                    break
            for no in self.ligacoes:
                if no.label == origem:
                    existeOrigem = True
                    break

            if existeOrigem and existeDestino:
                novo = node(destino)
                for no in self.ligacoes:
                    if no.label == origem:
                        self.ligacoes[no].update({novo : peso})
                        break
                #self.imprimir()
            else:
                print("destino ou origem inexistentes")

Example of the method I am using below:

def caminhoMinimo(grafo,comeco,fim): # comeco = vértice inicial --  fim = vértice final
    menorD = {} # menor distancia
    predecessor = {} # para saber da onde o caminho veio
    nodeNaoVis = grafo.ligacoes # node nao visto
    infinito = 999999 #numero para simular o infinito
    caminho = [] #isso que vai ser o print final

    for node in nodeNaoVis: #entenda node como um vértice por exemplo
        menorD[node] = infinito #preenche o menorD para todos os vertices que não seja o comeco de 999999
    menorD[comeco] = 0
#comeco do algoritmo em si abaixo
    while nodeNaoVis: #vai continuar dentro do while até que não tenha nenhum node não visitado
        nodeMin = None # Node minimo/distancia minima começa nulo, vazio
        for node in nodeNaoVis:
            if nodeMin is None: # caso base
                nodeMin = node # se o nodeMin estiver nulo então nodeMin recebe os nodes Nao vistos, na 1 vez recebe o grafo inteiro
            elif menorD[node] < menorD[nodeMin]:
                nodeMin = node #caso o node seja menor que o node Min, simplesmente deixamos os 2 iguais
        #abaixo esta a parte mais importante do algoritmo
        for nodeFilho, peso in grafo.ligacoes[nodeMin].items(): #vai pegar o node filho de cada Vertice no dicionario(grafo) e seu respectivo peso
            if peso + menorD[nodeMin] < menorD[nodeFilho]: #simplesmente vai somar o peso total ate chegar em tal vertice(node) e também tira os espaços com infinitos previamente ocupados
                menorD[nodeFilho] = peso + menorD[nodeMin]
                predecessor[nodeFilho] = nodeMin #estabelecendo como chegamos nesse vertice, por quais outros vertices passamos
        nodeNaoVis.pop(nodeMin) # esse pop serve para remover o nodeMin de dentro do nodeNaoVisto
    # print(menorD) aqui ja pode ter uns prints pq ja esta tudo pronto praticamente, abaixo so ajustaremos o print do caminho
    nodeAtual = fim
    while nodeAtual != comeco: #enquanto nodeAtual for diferente de comeco(vertice inicial)
        try:
            caminho.insert(0,nodeAtual)
            nodeAtual = predecessor[nodeAtual] #faz o atual virar o predecessor, tipo um for com numero maior para o menor
        except KeyError:
            print('Caminho não alcançavel')
            break
    caminho.insert(0,comeco) #para indicar qual o começo de cada caminho
    if menorD[fim] != infinito: # significa que foi alcançado
        print("A Menor distância entre {", comeco, "e", fim, "} é", str(menorD[fim]))
        print("O seu caminho é " + str(caminho))
       #{'a':{'b':3,'c':6} <-- EXEMPLO de grafo

Example of class integration and comparison with the dictionary below:

grafo = grafo()
grafo.inNode("0")
grafo.inNode("1")
grafo.inNode("2")
grafo.inNode("3")
grafo.inNode("4")
grafo.inNode("5")
grafo.inNode("6")
grafo.inNode("7")
grafo.inNode("8")

grafo.inAdj("0","4",50)
grafo.inAdj("0","6",30)
grafo.inAdj("0","3",20)
grafo.inAdj("1","8",20)
grafo.inAdj("2","8",10)
grafo.inAdj("3","5",20)
grafo.inAdj("3","8",20)
grafo.inAdj("4","7",10)
grafo.inAdj("4","8",20)
grafo.inAdj("5","2",50)
grafo.inAdj("6","3",40)
grafo.inAdj("6","4",20)
grafo.inAdj("7","1",30)
grafo.inAdj("8","6",10)
#grafo.imprimir()
caminhoMinimo(grafo,0,8)

#dicionario que eu usava antes
#grafod = {0:{4:50,6:30,3:20},1:{8:20},2:{8:10},3:{5:20,8:20},4:{7:10,8:20},5:{2:50},6:{3:40,4:20},7:{1:30},8:{6:10}}
No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.