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.
        '''
        return self.vertices.keys()

    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 __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.
        '''

        if not id in self.vertices:
            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)

    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 borrar_arista(self, desde, hasta):
        '''Borra 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.
           En caso de no existir la arista, se lanzara ValueError.
        '''
        if not desde or not hasta in self.vertices:
            raise KeyError("No se encontro uno de los vertices")
        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)

    def obtener_peso_arista(self, desde, hasta):
        '''Obtiene el peso de la arista que va desde el vertice 'desde', hasta el vertice 'hasta'.
           Parametros:
            * 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.
        '''
        if not desde or not hasta in self.vertices:
            raise KeyError("No se encontro uno de los vertices")
        if not hasta in self.vertices[desde]: return None
        return self.vertices[desde][hasta]

    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