View difference between Paste ID: 8kFNaLvz and UrAUXniH

 import random
 import heapq
 import math
 from time import time
 from collections import deque
 
 visitar_nulo = lambda a,b,c,d: True
 heuristica_nula = lambda actual,destino: 0
 
 class Grafo(object):
     '''Clase que representa un grafo. El grafo puede ser dirigido, o no, y puede
        no indicarsele peso a las aristas (se comportara como peso = 1).
       Implementado como "diccionario de diccionarios"
     '''
 
     def __init__(self, es_dirigido = False):
         '''Crea el grafo. El parametro 'es_dirigido' indica si sera dirigido, o no.'''
         self.es_dirigido = es_dirigido
         self.cant_vertices = 0
         self.vertices = {}
         self.personajes = {}
         self.nodos = {}
         self.cant_aristas = 0
 
     def __iter__(self):
         '''Devuelve un iterador para el grafo'''
         return iter(self.vertices)
 
     def __len__(self):
         '''Devuelve la cantidad de vertices del grafo'''
         return self.cant_vertices
 
-    def keys(self):
+
-        '''Devuelve una lista de identificadores de vertices. Iterar sobre
+
-           ellos es equivalente a iterar sobre el grafo.
+
            ya se encuentre asociado a un vertice, se actualizara el valor.
-        return self.vertices.keys()
+
 
         if not id in self.nodos:
             self.vertices[id] = {}
             self.personajes[valor] = id
             self.cant_vertices += 1
             self.nodos[id] = Nodo_Grafo(id, valor)
         self.nodos[id].nombre = valor
 
     def __contains__(self, id):
         ''' Determina si el grafo contiene un vertice con el identificador indicado.'''
         return id in self.vertices.keys()
 
     def cantidad_aristas(self):
         return self.cant_aristas
 
-    def __delitem__(self, id):
+
-        '''Elimina el vertice del grafo. Si no existe el identificador en el grafo,
+
-           lanzara KeyError.
+
-           Borra tambien todas las aristas que salian y entraban al vertice en cuestion.
+
             * desde y hasta: identificadores de vertices dentro del grafo. Si alguno
               de estos no existe dentro del grafo, lanzara KeyError.
             * Peso: valor de peso que toma la conexion. Si no se indica, valdra 1.
-            raise KeyError("No se encontro la clave")
+
-        for i in self.vertices:
+
-            if id in self.vertices[i]:
+
-                self.vertices[i].pop(id)
+
-        self.vertices.pop(id)
+
-        self.nodos.pop(id)
+
         if self.es_dirigido:
             self.vertices[hasta][desde] = peso
 
     def adyacentes(self, id):
         '''Devuelve una lista con los vertices (identificadores) adyacentes
            al indicado. Si no existe el vertice, se lanzara KeyError
         '''
         if not id in self.vertices:
             raise KeyError("No se encontro el vertice")
         return list(self.vertices[id].keys())
 
     def obtener_personaje(self, id):
         '''Devuelve el valor de la id'''
         if not id in self.nodos:
             raise KeyError("No se encontro la id")
         return self.nodos[id].nombre
 
     def grado(self):
         '''Devuelve el grado total del grafo'''
         grado_total = 0
         for vertice in self.vertices:
             for adyacente in Grafo.adyacentes(self, vertice):
                 grado_total += 1
         return grado_total
 
-    def borrar_arista(self, desde, hasta):
+
-        '''Borra una arista que conecta los vertices indicados.
+
         if not valor in self.personajes:
-            * desde y hasta: identificadores de vertices dentro del grafo.
+
-              Si alguno de estos no existe dentro del grafo, lanzara KeyError.
+
-           En caso de no existir la arista, se lanzara ValueError.
+
 
     def random_walk(self, largo, origen = None, pesado = False):
         ''' Devuelve una lista con un recorrido aleatorio de grafo.
-        if not hasta in self.vertices[desde][1]:
+
-            raise ValueError("No existe la arista")
+
-        if not self.es_dirigido:
+
-            self.vertices[hasta].pop(desde)
+
-        self.vertices[desde].pop(hasta)
+
                   las probabilidades de movernos de un vertice a uno de sus vecinos (False = todo equiprobable).
-    def obtener_peso_arista(self, desde, hasta):
+
-        '''Obtiene el peso de la arista que va desde el vertice 'desde', hasta el vertice 'hasta'.
+
         '''
-            * desde y hasta: identificadores de vertices dentro del grafo.
+
-              Si alguno de estos no existe dentro del grafo, lanzara KeyError.
+
-           En caso de no existir la union consultada, se devuelve None.
+
         cont_recorrido = 0
         if origen:
             if not origen in self.vertices:
-        if not hasta in self.vertices[desde]: return None
+
-        return self.vertices[desde][hasta]
+
         else:
             lista_claves = list(self.vertices.keys())
             vertice_random = random.choice(lista_claves)
             while not vertice_random:
                 vertice_random = random.choice(lista_claves)
             recorrido.append(vertice_random)
 
         vertice_partida = recorrido[cont_recorrido]
 
         while cont_recorrido < largo:
             if not vertice_partida: break
             diccionario_adyacentes = self.vertices[vertice_partida]
             if pesado:
                 vertice_random = vertice_random_por_peso(diccionario_adyacentes)
             else:
                 lista_claves = list(self.vertices[vertice_partida].keys())
                 vertice_random = random.choice(lista_claves)
 
             recorrido.append(vertice_random)
             cont_recorrido+= 1
             vertice_partida = recorrido[cont_recorrido]
 
 
         return recorrido
 
     def dijkstra(self, origen, destino, minimo = True):
 
         '''Devuelve el recorrido dependiendo si es maximo o minimo desde el
             origen hasta el destino, aplicando el algoritmo de Dijkstra.
            Parametros:
             * minimo: indica si el camino devuelto sera el minimo si minimo es True
               devolvera el maximo si es False
             * origen y destino: identificadores de vertices dentro del grafo.
               Si alguno de estos no existe dentro del grafo, lanzara KeyError.
            Devuelve:
             * Listado de vertices (identificadores) ordenado con el recorrido, incluyendo
               a los vertices de origen y destino. En caso que no exista camino entre
               el origen y el destino, se devuelve None.
         '''
         heap = []
         camino = []
         for vertice in self.vertices:
             nodo = self.nodos[vertice]
             nodo.visitado = False
             nodo.distancia = math.inf
             if vertice == origen:
                 heapq.heappush(heap,nodo)
                 nodo.distancia = 0
         while heap:
             nodo = heapq.heappop(heap)
             nodo.visitado = True
             vertice = nodo.vertice
             dist = nodo.distancia
             for adyacente in self.vertices[vertice]:
                 if not adyacente: continue
                 peso = self.vertices[vertice][adyacente]
                 nodo_ad = self.nodos[adyacente]
                 if not nodo_ad.visitado and nodo_ad.distancia > (dist + peso):
 
                     if minimo:
                         nodo_ad.cambiar_dist(dist + peso)
                     else:
                         nodo_ad.cambiar_dist(dist + 1/peso)
                     nodo_ad.cambiar_padre(vertice)
                     heapq.heappush(heap,nodo_ad)
 
         vertice = destino
         camino.append(vertice)
         while vertice != origen:
             padre = self.nodos[vertice].padre
             camino.append(padre)
             vertice = padre
         return camino
 
 
 
     def bfs(self, inicio = None, visitar = None, extra = None):
 
         '''Realiza un recorrido BFS dentro del grafo
         Parametros:
             - inicio: identificador del vertice que se usa como inicio. Si se indica un vertice, el recorrido se comenzara en dicho vertice,
             y solo se seguira hasta donde se pueda (no se seguira con los vertices que falten visitar)
         Salida:
             Tupla (padres, orden), donde :
                 - 'padres' es un diccionario que indica para un identificador, cual es el identificador del vertice padre en el recorrido BFS (None si es el inicio)
                 - 'orden' es un diccionario que indica para un identificador, cual es su orden en el recorrido BFS
         '''
         padres = {}
         orden = {}
 
         for nodo in self.nodos:
             nodo = self.nodos[nodo]
             nodo.visitado = False
             padres[nodo.vertice] = None
             orden[nodo.vertice] = math.inf
 
         if inicio:
             nodo = self.nodos[inicio]
             vertice = inicio
         else:
             nodos = list(self.nodos.keys())
             vertice = random.choice(nodos)
             nodo = self.nodos[vertice]
         vertice_origen = vertice
         padres[vertice] = None
         nodo.visitado = True
         orden[vertice] = 0
         cola = deque([])
         cola.append(nodo)
         while cola:
             nodo = cola.popleft()
             vertice = nodo.vertice
             if visitar and not visitar(nodo,extra): break
             for adyacente in self.vertices[vertice]:
                 nodo_ad = self.nodos[adyacente]
                 if nodo_ad.visitado == False:
                     nodo_ad.visitado = True
                     cola.append(nodo_ad)
                     orden[adyacente] = orden[vertice] + 1
                     padres[adyacente] = vertice
 
         return (orden, padres, vertice_origen)
 
 
 
 class Nodo_Grafo():
 
     def __init__(self, vertice, nombre, distancia = 0, visitado = False, padre = None):
         self.vertice = vertice
         self.distancia = distancia
         self.visitado = visitado
         self.padre = padre
         self.nombre = nombre
         self.label_act = int(vertice)
 
 
     def visitado(self):
         return self.visitado
 
     def cambiar_dist(self, distancia_nueva):
         self.distancia = distancia_nueva
 
     def cambiar_padre(self, padre_nuevo):
         self.padre = padre_nuevo
 
     def __lt__(self,otro):
         return self.distancia < otro.distancia
 
     def __gt__(self,otro):
         return self.distancia > otro.distancia
 
     def __eq__(self,otro):
         return self.distancia == otro.distancia
 
     def __str__(self):
         return str(self.vertice)+"; "+str(self.distancia)
 
 
 
 def vertice_random_por_peso(diccionario_adyacentes):
     '''Devuelve un vertice adyacente random, con altas prioridades de que su peso sea mayor al de los demas'''
 
     total = sum(diccionario_adyacentes.values())
     rand = random.uniform(0, total)
     acum = 0
     for vertice, peso_arista in diccionario_adyacentes.items():
         if acum + peso_arista >= rand:
             return vertice
         acum += peso_arista