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 __setitem__(self, id, valor):
        '''Agrega un nuevo vertice con el par <id, valor> indicado. ID debe
           ser de identificador unico del vertice. En caso que el identificador
           ya se encuentre asociado a un vertice, se actualizara el valor.
        '''

        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 agregar_arista(self, desde, hasta, peso = 1):
        '''Agrega una arista que conecta los vertices indicados.
           Parametros:
            * 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.
            Si el grafo es no-dirigido, tambien agregara la arista reciproca.
        '''
        if not desde or not hasta in self.vertices:
            raise KeyError("No se encontro uno de los vertices")
        self.cant_aristas += 1
        self.vertices[desde][hasta] = peso
        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 obtener_id(self, valor):
        '''Devuelve la ide del valor'''
        if not valor in self.personajes:
            raise KeyError("La No se encontro el nombre")
        return self.personajes[valor]


    def random_walk(self, largo, origen = None, pesado = False):
        ''' Devuelve una lista con un recorrido aleatorio de grafo.
            Parametros:
                * largo: El largo del recorrido a realizar
                * origen: Vertice (id) por el que se debe comenzar el recorrido.
                  Si origen = None, se comenzara por un vertice al azar.
                * pesado: indica si se tienen en cuenta los pesos de las aristas para determinar
                  las probabilidades de movernos de un vertice a uno de sus vecinos (False = todo equiprobable).
            Devuelve:
                Una lista con los vertices (ids) recorridos, en el orden del recorrido.
        '''
        if not self.vertices:
            raise ValueError("No hay vertices en el grafo")
        recorrido = []
        cont_recorrido = 0
        if origen:
            if not origen in self.vertices:
                raise KeyError("No se encontro el vertice origen")
            recorrido.append(origen)
        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