Implementan de grafos con clase nodo y métodos de búsqueda por profundidad, amplitud y A*

grafo_dfs_bfs_a_asterisco.py

class Nodo:
    def __init__ (self, valor):
        self.info = valor
        self.arcos = []
        
    def enlace (self, ndestino, peso = 1, bdir = False):
        if (type(ndestino) == type(self)):
            arco = Arco(ndestino, peso)
            self.arcos.append(arco)
            if (bdir == True):
                arco = Arco(self, peso)
                ndestino.arcos.append(arco)
            return True
        return False
        
    def muestra_enlaces (self):
        for arco in self.arcos: 
            print arco.nodo.info,
            print arco.peso
            
    def existe_enlace(self, ndestino):
        for arco in self.arcos:
            if (arco.nodo == ndestino):
                return arco
        return False
        
    def eli_enlace (self, ndestino):
        arco = self.existe_enlace(ndestino)
        if (arco != False):
            self.arcos.remove(arco)
            return True
        return False
            
    def __del__(self):
        del self.arcos

    def __str__(self):
        return self.info
        
class Arco:
    def __init__ (self, ndestino, peso=0):
        self.nodo = ndestino
        self.peso = peso

class Grafo:
    def __init__(self, dirigido = True):
        self.__nodos = []
        self.__dirigido = dirigido
        
    def buscaNodo (self, valor):
        for nodo in self.__nodos:
            if (nodo.info == valor):
                return nodo
        return False
    
    def enlace(self, valOrigen, valDestino, peso = 1, bdir = False):
        
        norigen = self.buscaNodo(valOrigen)
        if (not(norigen)):
            return False
            
        ndestino = self.buscaNodo(valDestino)
        if (not(ndestino)):
            return False
        
        if (self.__dirigido == False):
            bdir = True
            
        norigen.enlace(ndestino, peso, bdir)
        return True
        
    def ins_nodo (self, valor):
        if (self.buscaNodo(valor) == False):
            nodo = Nodo(valor)
            self.__nodos.append(nodo)
            return nodo
        return False
        
    def eli_nodo(self, valor):
        nodoE = self.buscaNodo(valor)
        if (nodoE == False):
            return False
            
        for nodo in self.__nodos:
            nodo.eli_enlace(nodoE)
        
        self.__nodos.remove(nodoE)
        return True
    
    def existen_islas(self):
        for nodo in self.__nodos:
            if (len(nodo.arcos) == 0):
                esIsla = True
                for norigen in self.__nodos:
                    if (norigen.existe_enlace(nodo) != False):
                        esIsla = False
                        break
                        
                if (esIsla == True):
                    return True
        return False
    
    def elimina_bucles(self):
        for nodo in self.__nodos:
            if nodo.existe_enlace(nodo):
                nodo.eli_enlace(nodo)
                
    def existe_camino (self, valOrigen, valDestino, camino = []):
        
        nOrigen = self.buscaNodo(valOrigen)
        nDestino = self.buscaNodo(valDestino)
        if (nOrigen == False or nDestino == False):
            return False
        
        camino.append(valOrigen)
        if (nOrigen.existe_enlace(nDestino) != False):
            camino.append(valDestino)
            return True
        
        for arco in nOrigen.arcos:
            if (arco.nodo.info in camino):
                continue
        
            if (self.existe_camino (arco.nodo.info, valDestino, camino)):
                return True
            camino.pop()

        return False
        
    # Metodo para estimar Deep First Search o profundidad
    def dfs(self,inicio,visitados = []):

        # Se añade a los visitados el nodo inicial
        visitados.append(inicio.info)
        
        # Si se recorrieron todos los nodos se imprime la lista
        if(len(self.__nodos)==len(visitados)):
            print visitados
        
        # Se recorren los arcos del inicio
        for arco in inicio.arcos:
            # Si el nodo no ha sido visitado
            if(arco.nodo.info not in visitados):
                #Se llama recursivamente a la funcion con valor de 
                #inicio el nodo en cuestion
                self.dfs(arco.nodo,visitados)
                
    # Metodo para estimar Breadth First Search o ancho
    def bfs(self,inicio,visitados = [],cercanos = []):

        # Se añade a los visitados el nodo inicial
        visitados.append(inicio.info)

        # Si se recorrieron todos los nodos se imprime la lista
        if(len(self.__nodos)==len(visitados)):
            print visitados
        
        # Se recorren los arcos del inicio
        for arco in inicio.arcos:
            # Si el elemento no esta en cercanos, ni ha sido visitado
            if(arco.nodo not in cercanos and arco.nodo.info not in visitados):
                #se agrega a los cercanos
                cercanos.append(arco.nodo)
                
        # Si hay elementos en cercanos
        if(len(cercanos)>0):
            # Se asigna el nodo a una variable
            item = cercanos[0]
            # Se elimina el elemento de cercanos
            cercanos.pop(0)
            #Se llama recursivamente la funcion con el item como nodo inicio
            #y las respectivas listas actualizadas
            self.bfs(item,visitados,cercanos)

    # Se establecio un nuevo metodo para comprobar si existe un camino
    # que logra recorrer un camino desde un origen a un destino a maxima
    # profundidad
    def camino(self,origen,destino,valor = []):
        nOrigen = self.buscaNodo(origen)
        nDestino = self.buscaNodo(destino)
        if (nOrigen.existe_enlace(nDestino) != False):
            valor.append(True)
            return True

        
        for arco in nOrigen.arcos:
            self.camino(arco.nodo.info,destino)
        if True not in valor:
            return False
        else:
            return True

    # Implementacion de metodo A*
    # Es importante que no se aplico la formula de funcion heuristica, debido a que
    # se utilizo el peso de los arcos
    # Nota: La Funcion no es recursiva
    # abiertos -> Define los nodos hijos en lo que se buscara el camino
    # cerrados -> Define cual es el nodo con menor peso por cada elemento en una iteracion de abiertos
    def a_asterisco(self,valOrigen,valDestino,abiertos = {},cerrados = {}):
        nOrigen = self.buscaNodo(valOrigen)
        nDestino = self.buscaNodo(valDestino)
        # En la variable rutas se almacena la ruta "optima"
        rutas = {}
        rutas[valOrigen] = []
        #Se comprueba que exista el camino
        if(self.camino(valOrigen,valDestino)):
            # Se agrega el nodo inicial en la lista abiertos
            abiertos[valOrigen] = 0
            # Se repite mientras existan elementos en la lista abiertos
            while abiertos:
                # Se establece un peso por cada iteracion, con el fin de obtener el peso
                # menor en los arcos
                peso = 999
                for item in abiertos:
                    nodos = self.buscaNodo(item)
                    # Se recorren los arcos de los nodos
                    for arco in nodos.arcos:
                        #Si existe un camino
                        if(self.camino(arco.nodo.info,valDestino)):
                            # Se comprueba que el peso de ese camino sea menor que el de la variable arbitraria peso
                            if arco.peso < peso:
                                # En caso de que se cumpla, se actualiza el peso, con el fin de obtener el nodo con menor peso
                                peso =  arco.peso
                                #Si existen elementos en el diccionario cerrados 
                                if(len(cerrados)!=0):
                                    for key in cerrados.keys():
                                        # Si el peso de la variable almacenada en cerrados es mayor que el peso actual
                                        if(cerrados[key]>peso):
                                            # Se limpia el diccionario
                                            cerrados.clear()
                                            break
                                # Se asigna a cerrados el nodo/peso con menor peso
                                cerrados[arco.nodo.info] = peso
                            #Si se llego al destino
                            if(arco.nodo.info == valDestino):
                                #Se almacena el ultimo valor en la ruta
                                rutas[valOrigen].append({arco.nodo.info:arco.peso})
                                #Se imprime la ruta "optima"
                                print rutas
                                #Retorna verdadero
                                return True
                            # Se establece un nuevo valor para el nodo en el que se itera
                            nodos = arco.nodo
                # Se va asignando en la ruta una copia de los elementos
                rutas[valOrigen].append(cerrados.copy())
                # Se limpian los abiertos
                abiertos.clear()
                # Se copian los cerrados en abiertos
                abiertos = cerrados.copy()
                # Se limpian los cerrados para una nueva iteracion
                cerrados.clear()
        # Si no existe un camino, retorna falso
        return False

        
    def __str__(self):
        grafo  = ""
        for nodo in self.__nodos:
            grafo = grafo + nodo.info
            arcos = ""
            for arco in nodo.arcos:
                if (arcos != ""):
                    arcos = arcos + ", "
                arcos = arcos + arco.nodo.info + ":" + str(arco.peso)
            grafo = grafo + "(" + arcos + ") "
        return grafo    

(y)