# 99192 OTERO - 99373 ALVAREZ,     JORGE COLLINET
import sys
from grafo import Grafo
import heapq
import collections
import re
RANGO_WALKS = 100
CANTIDAD_WALKS = 50
RANGO_CENTRALIDAD = 700
OPCIONES = ['1','2','3','4','5','6','7','8']

def crear_grafo(ruta):
    ''' Recibe una ruta de un archivo y devuelve un grafo a partir de sus datos
        PRE: la ruta debe existir, el archivo debe ser de la siguiente manera:
            Vertices cant
            .
            .
            Arcs*
            .
    '''
    with open(ruta) as archivo:
        grafo = Grafo(True)
        for i,linea in enumerate(archivo):
            if i == 0: continue
            linea = linea.rstrip("\n")
            if linea == "*Arcs": break
            vertice = linea.split(" ", 1)
            vertice[1] = vertice[1].rstrip('"')
            vertice[1] = vertice[1].lstrip('"')
            grafo.__setitem__(vertice[0], vertice[1])
        for linea in archivo:
            linea = linea.rstrip("\n")
            arista = linea.split(" ")
            grafo.agregar_arista(arista[0],arista[1],int(arista[2]))
    return grafo


def frecuencia_random_walks(grafo, cantidad , id = None, recomendados = False,  rang_walk = RANGO_WALKS):
    ''' Ejecuta varias veces la funcion random_walks.
      Parametros:
       *grafo: el grafo sobre el cual se aplicara la funcion
       *cantidad: la cantidad de veces que se hara random_walks
       *id: es la id origen, por defecto es None
       *rang_walk: es el rango del random_walks
       *recomendados: es un booleano que indica si se esta utilizando para la funcion recomendados
      Salida:
        Devuelve una lista con los id's que mas aparecen en los recorridos randoms,
        en caso de que recomendados = True devolvera una lista con los que aparecen
        mas veces en los recorridos a partir del origen, pero no estaran sus
        adyacentes
    '''
    cantidad += 1 #Le sumo 1 por el tema de que most_common va desde 0 - cant-1
    frecuencia = []
    frecuentes = []

    if id:
        if not id in grafo:
            raise KeyError("No se encuentra el personaje")
    for i in range(rang_walk):
        id_origen = id
        lista_aux = grafo.random_walk(CANTIDAD_WALKS, id_origen, True)
        frecuencia += lista_aux

    if recomendados:
        frecuencia = [v for v in frecuencia if v not in grafo.adyacentes(id_origen)]
    apariciones = collections.Counter(frecuencia).most_common(cantidad)

    for id,aparicion in apariciones:
        if not id or id == id_origen: continue
        frecuentes.append(id)
    return frecuentes

def imprimir_personajes(grafo, ids):
    '''A partir de una lista de ids imprime en pantalla los nombres
       de cada id respectivamente'''
    for i, id in enumerate(ids):
        i += 1
        nombre = grafo.obtener_personaje(id)
        print(str(i)+") "+ nombre)

def op_recomendados(grafo, personaje, cantidad):

    id = grafo.obtener_id(personaje)
    recomendados = frecuencia_random_walks(grafo, int(cantidad), id, True)
    print("Las recomendaciones respecto de", personaje,"son:")
    imprimir_personajes(grafo, recomendados)

def op_similares(grafo, personaje, cantidad):
    id = grafo.obtener_id(personaje)
    similares = frecuencia_random_walks(grafo, int(cantidad), id)
    personaje = grafo.obtener_personaje(id)
    print("Los similares respecto de", personaje,"son:")
    imprimir_personajes(grafo, similares)

def op_centralidad(grafo, cantidad):
    centrales = frecuencia_random_walks(grafo,int(cantidad), None, False, RANGO_CENTRALIDAD)
    imprimir_personajes(grafo, centrales)

def op_camino(grafo, personaje1, personaje2):
    id1 = grafo.obtener_id(personaje1)
    id2 = grafo.obtener_id(personaje2)
    camino = grafo.dijkstra(id1, id2, False)
    print("El camino es:")
    imprimir_personajes(grafo, camino)

def op_distancia(grafo, personaje):
    id = grafo.obtener_id(personaje)
    orden, padres, vertice = grafo.bfs(id)
    distancias = {}
    for id, distancia in orden.items():
        distancias.setdefault(distancia, []).append(id)
    list_distancias = list(distancias.keys())
    list_distancias.sort()
    for distancia in list_distancias:
        if distancia == 0: continue
        cantidad = len(distancias[distancia])
        print("La cantidad de personajes a distancia "+str(distancia)+" es: "+ str(cantidad))

def desviacion_estandar(grafo, grado_grafo, cantidad_vertices):

    '''Devuelve la desviacion estandar'''

    sumatoria = 0
    for vertice in grafo.vertices:
        grado_vertice = 0
        for adyacente in grafo.adyacentes(vertice):
            grado_vertice += 1
        sumatoria += (grado_vertice - grado_grafo /cantidad_vertices)**2
    desvio_estandar = ((1/(cantidad_vertices - 1))* sumatoria)**(0.5)
    return desvio_estandar


def op_estadisticas(grafo):

    cantidad_vertices = grafo.cant_vertices
    cantidad_aristas = grafo.cant_aristas
    grado_total = grafo.grado()
    desv_std = desviacion_estandar(grafo, grado_total, cantidad_vertices)
    numero_max_aristas = cantidad_vertices * (cantidad_vertices - 1)

    print("Cantidad de vertices: {}".format(cantidad_vertices))
    print("Cantidad de aristas: {}".format(cantidad_aristas))
    print("Promedio del grado de cada vértice: %.2f" % (grado_total/cantidad_vertices))
    print("Desvio estándar del grado de cada vértice: %.2f" % (desv_std))
    print("Densidad del grafo: %.6f" % (cantidad_aristas/numero_max_aristas))


def max_freq(list_adyacentes, nodos):

    mayor_freq = {}
    for adyacente in list_adyacentes: #Contador de frecuencia de cada label
        label = nodos[adyacente].label_act
        if not label in mayor_freq:
            mayor_freq[label] = 0
        mayor_freq[label] += 1

    label_mayor_freq = 0
    frecuencia = 0

    for label in mayor_freq: # Detector del que tiene mayor frecuencia
        if mayor_freq[label] > frecuencia:
            label_mayor_freq = label
            frecuencia = mayor_freq[label]

    return label_mayor_freq

def _op_comunidades(grafo, nodos):

    comunidades = {} #label : [vertices]
    for vertice in nodos:
        nodos[vertice].label = max_freq(grafo.adyacentes(vertice), nodos)
        label = nodos[vertice].label
        if not label in comunidades:
            comunidades[label] = []
        comunidades[label].append(vertice)

    eliminar = []
    for comunidad in comunidades:
        if len(comunidades[comunidad]) <= 4 or len(comunidades[comunidad]) >= 1000:
            eliminar.append(comunidad)

    for comunidad in eliminar:
        comunidades.pop(comunidad)

    return comunidades


def op_comunidades(grafo):
    nodos = grafo.nodos
    comunidades = _op_comunidades(grafo, nodos)
    desigualdad = False
    while True:
        test_comunidad = _op_comunidades(grafo,nodos)
        if comunidades == test_comunidad: break
        comunidades = test_comunidad
    for i, comunidad in enumerate(comunidades):
        print("\n\nCantidad de Integrantes: {}".format(len(comunidades[comunidad])))
        imprimir_personajes(grafo, comunidades[comunidad])


def verificar_personaje(grafo, personaje):
    if not personaje in grafo.personajes:
        intentos = 0
        while intentos < 5 and not personaje in grafo.personajes:
            personaje = input("El personaje no se encuentra en la base de datos, vuelva a ingresar: ")
            personaje = personaje.upper()
            intentos += 1
        if intentos == 5 and not personaje in grafo.personajes:
            return False
    return personaje

def verificar_numero(opcion):
    if not opcion.isdigit():
        intentos = 0
        while intentos < 5 and not opcion.isdigit():
            opcion = input("Vuelva a seleccionar la cantidad: ")
            intentos += 1
        if intentos == 5 or not opcion.isdigit(): return False
    return opcion



def menu(grafo):
    print("************** MENU - MARVEL ***************")
    print("1- Recomendados")
    print("2- Similares")
    print("3- Centralidad")
    print("4- Camino")
    print("5- Distancias")
    print("6- Estadisticas")
    print("7- Comunidades")
    print("8- Salir")
    opcion = input("Ingrese una opcion: ")
    print("")
    posibilidades = 0
    while not opcion in OPCIONES and posibilidades != 5 :
        print("Error al ingresar la opcion")
        opcion = input("Ingrese una opcion nuevamente: ")
        posibilidades += 1

    if posibilidades == 5: return

    opcion = int(opcion)

    if opcion == 1:
        print("************** Recomendados ***************")
        personaje = input("Ingrese el nombre del personaje: ")
        personaje = personaje.upper()
        personaje = verificar_personaje(grafo, personaje)
        if not personaje: return
        cantidad = input("Ingrese cantidad de recomendados: ")
        cantidad = verificar_numero(cantidad)
        if not cantidad: return
        op_recomendados(grafo, personaje, cantidad)

    elif opcion == 2:
        print("************** Similares ***************")
        personaje = input("Ingrese el nombre del personaje: ")
        personaje = personaje.upper()
        personaje = verificar_personaje(grafo, personaje)
        if not personaje: return
        cantidad = input("Ingrese cantidad de similares: ")
        cantidad = verificar_numero(cantidad)
        if not cantidad: return
        op_similares(grafo, personaje, cantidad)

    elif opcion == 3:
        print("************** Centralidad ***************")
        cantidad = input("Ingrese cantidad de personajes centrales: ")
        cantidad = verificar_numero(cantidad)
        if not cantidad: return
        op_centralidad(grafo, cantidad)

    elif opcion == 4:
        print("************** Camino ***************")
        personaje1 = input("Ingrese el nombre del personaje de origen: ")
        personaje1 = personaje1.upper()
        personaje1 = verificar_personaje(grafo, personaje1)
        if not personaje1: return
        personaje2 = input("Ingrese el nombre del personaje de destino: ")
        personaje2 = personaje2.upper()
        personaje2 = verificar_personaje(grafo, personaje2)
        if not personaje2: return
        op_camino(grafo, personaje1, personaje2)






    elif opcion == 5:
        print("************** Distancias ***************")
        personaje = input("Ingrese el nombre del personaje: ")
        personaje = personaje.upper()
        personaje = verificar_personaje(grafo, personaje)
        if not personaje: return
        op_distancia(grafo, personaje)

    elif opcion == 6:
        print("************** Estadisticas ***************")
        op_estadisticas(grafo)

    elif opcion == 7:
        print("************** Comunidades ***************")
        op_comunidades(grafo)

    elif opcion == 8: return


def main():
    ruta = sys.argv[1]
    grafo = crear_grafo(ruta)
    menu(grafo)

main()