View difference between Paste ID: weDyFe7Y and S5DUw5gW

-# 99373 ALVAREZ - 99192 OTERO
+import sys
-import random
+from grafo import Grafo
 import heapq
-import math
+import collections
-from time import time
+import re
-from collections import deque
+RANGO_WALKS = 100
 CANTIDAD_WALKS = 50
-visitar_nulo = lambda a,b,c,d: True
+RANGO_CENTRALIDAD = 700
-heuristica_nula = lambda actual,destino: 0
+OPCIONES = ['1','2','3','4','5','6','7','8']
 
-class Grafo(object):
+def crear_grafo(ruta):
-    '''Clase que representa un grafo. El grafo puede ser dirigido, o no, y puede
+    ''' Recibe una ruta de un archivo y devuelve un grafo a partir de sus datos
-       no indicarsele peso a las aristas (se comportara como peso = 1).
+        PRE: la ruta debe existir, el archivo debe ser de la siguiente manera:
-      Implementado como "diccionario de diccionarios"
+            Vertices cant
             .
             .
-    def __init__(self, es_dirigido = False):
+            Arcs*
-        '''Crea el grafo. El parametro 'es_dirigido' indica si sera dirigido, o no.'''
+            .
-        self.es_dirigido = es_dirigido
+
-        self.cant_vertices = 0
+    with open(ruta) as archivo:
-        self.vertices = {}
+        grafo = Grafo(True)
-        self.personajes = {}
+        for i,linea in enumerate(archivo):
-        self.nodos = {}
+            if i == 0: continue
-        self.cant_aristas = 0
+            linea = linea.rstrip("\n")
             if linea == "*Arcs": break
-    def __iter__(self):
+            vertice = linea.split(" ", 1)
-        '''Devuelve un iterador para el grafo'''
+            vertice[1] = vertice[1].rstrip('"')
-        return iter(self.vertices)
+            vertice[1] = vertice[1].lstrip('"')
             grafo.__setitem__(vertice[0], vertice[1])
-    def __len__(self):
+        for linea in archivo:
-        '''Devuelve la cantidad de vertices del grafo'''
+            linea = linea.rstrip("\n")
-        return self.cant_vertices
+            arista = linea.split(" ")
             grafo.agregar_arista(arista[0],arista[1],int(arista[2]))
-    def __setitem__(self, id, valor):
+    return grafo
-        '''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.
+def frecuencia_random_walks(grafo, cantidad , id = None, recomendados = False,  rang_walk = RANGO_WALKS):
-        '''
+    ''' Ejecuta varias veces la funcion random_walks.
       Parametros:
-        if not id in self.nodos:
+       *grafo: el grafo sobre el cual se aplicara la funcion
-            self.vertices[id] = {}
+       *cantidad: la cantidad de veces que se hara random_walks
-            self.personajes[valor] = id
+       *id: es la id origen, por defecto es None
-            self.cant_vertices += 1
+       *rang_walk: es el rango del random_walks
-            self.nodos[id] = Nodo_Grafo(id, valor)
+       *recomendados: es un booleano que indica si se esta utilizando para la funcion recomendados
-        self.nodos[id].nombre = valor
+      Salida:
         Devuelve una lista con los id's que mas aparecen en los recorridos randoms,
-    def __contains__(self, id):
+        en caso de que recomendados = True devolvera una lista con los que aparecen
-        ''' Determina si el grafo contiene un vertice con el identificador indicado.'''
+        mas veces en los recorridos a partir del origen, pero no estaran sus
-        return id in self.vertices.keys()
+        adyacentes
     '''
-    def cantidad_aristas(self):
+    cantidad += 1 #Le sumo 1 por el tema de que most_common va desde 0 - cant-1
-        return self.cant_aristas
+    frecuencia = []
     frecuentes = []
 
-    def agregar_arista(self, desde, hasta, peso = 1):
+    if id:
-        '''Agrega una arista que conecta los vertices indicados.
+        if not id in grafo:
-           Parametros:
+            raise KeyError("No se encuentra el personaje")
-            * desde y hasta: identificadores de vertices dentro del grafo. Si alguno
+    for i in range(rang_walk):
-              de estos no existe dentro del grafo, lanzara KeyError.
+        id_origen = id
-            * Peso: valor de peso que toma la conexion. Si no se indica, valdra 1.
+        lista_aux = grafo.random_walk(CANTIDAD_WALKS, id_origen, True)
-            Si el grafo es no-dirigido, tambien agregara la arista reciproca.
+        frecuencia += lista_aux
-        '''
+
-        if not desde or not hasta in self.vertices:
+    if recomendados:
-            raise KeyError("No se encontro uno de los vertices")
+        frecuencia = [v for v in frecuencia if v not in grafo.adyacentes(id_origen)]
-        self.cant_aristas += 1
+    apariciones = collections.Counter(frecuencia).most_common(cantidad)
-        self.vertices[desde][hasta] = peso
+
-        if self.es_dirigido:
+    for id,aparicion in apariciones:
-            self.vertices[hasta][desde] = peso
+        if not id or id == id_origen: continue
         frecuentes.append(id)
-    def adyacentes(self, id):
+    return frecuentes
-        '''Devuelve una lista con los vertices (identificadores) adyacentes
+
-           al indicado. Si no existe el vertice, se lanzara KeyError
+def imprimir_personajes(grafo, ids):
-        '''
+    '''A partir de una lista de ids imprime en pantalla los nombres
-        if not id in self.vertices:
+       de cada id respectivamente'''
-            raise KeyError("No se encontro el vertice")
+    for i, id in enumerate(ids):
-        return list(self.vertices[id].keys())
+        i += 1
         nombre = grafo.obtener_personaje(id)
-    def obtener_personaje(self, id):
+        print(str(i)+") "+ nombre)
-        '''Devuelve el valor de la id'''
+
-        if not id in self.nodos:
+def op_recomendados(grafo, personaje, cantidad):
-            raise KeyError("No se encontro la id")
+
-        return self.nodos[id].nombre
+    id = grafo.obtener_id(personaje)
     recomendados = frecuencia_random_walks(grafo, int(cantidad), id, True)
-    def grado(self):
+    print("Las recomendaciones respecto de", personaje,"son:")
-        '''Devuelve el grado total del grafo'''
+    imprimir_personajes(grafo, recomendados)
-        grado_total = 0
+
-        for vertice in self.vertices:
+def op_similares(grafo, personaje, cantidad):
-            for adyacente in Grafo.adyacentes(self, vertice):
+    id = grafo.obtener_id(personaje)
-                grado_total += 1
+    similares = frecuencia_random_walks(grafo, int(cantidad), id)
-        return grado_total
+    personaje = grafo.obtener_personaje(id)
     print("Los similares respecto de", personaje,"son:")
-    def obtener_id(self, valor):
+    imprimir_personajes(grafo, similares)
-        '''Devuelve la ide del valor'''
+
-        if not valor in self.personajes:
+def op_centralidad(grafo, cantidad):
-            raise KeyError("La No se encontro el nombre")
+    centrales = frecuencia_random_walks(grafo,int(cantidad), None, False, RANGO_CENTRALIDAD)
-        return self.personajes[valor]
+    imprimir_personajes(grafo, centrales)
 
-
+def op_camino(grafo, personaje1, personaje2):
-    def random_walk(self, largo, origen = None, pesado = False):
+    id1 = grafo.obtener_id(personaje1)
-        ''' Devuelve una lista con un recorrido aleatorio de grafo.
+    id2 = grafo.obtener_id(personaje2)
-            Parametros:
+    camino = grafo.dijkstra(id1, id2, False)
-                * largo: El largo del recorrido a realizar
+    print("El camino es:")
-                * origen: Vertice (id) por el que se debe comenzar el recorrido.
+    imprimir_personajes(grafo, camino)
-                  Si origen = None, se comenzara por un vertice al azar.
+
-                * pesado: indica si se tienen en cuenta los pesos de las aristas para determinar
+def op_distancia(grafo, personaje):
-                  las probabilidades de movernos de un vertice a uno de sus vecinos (False = todo equiprobable).
+    id = grafo.obtener_id(personaje)
-            Devuelve:
+    orden, padres, vertice = grafo.bfs(id)
-                Una lista con los vertices (ids) recorridos, en el orden del recorrido.
+    distancias = {}
-        '''
+    for id, distancia in orden.items():
-        if not self.vertices:
+        distancias.setdefault(distancia, []).append(id)
-            raise ValueError("No hay vertices en el grafo")
+    list_distancias = list(distancias.keys())
-        recorrido = []
+    list_distancias.sort()
-        cont_recorrido = 0
+    for distancia in list_distancias:
-        if origen:
+        if distancia == 0: continue
-            if not origen in self.vertices:
+        cantidad = len(distancias[distancia])
-                raise KeyError("No se encontro el vertice origen")
+        print("La cantidad de personajes a distancia "+str(distancia)+" es: "+ str(cantidad))
-            recorrido.append(origen)
+
-        else:
+def desviacion_estandar(grafo, grado_grafo, cantidad_vertices):
-            lista_claves = list(self.vertices.keys())
+
-            vertice_random = random.choice(lista_claves)
+    '''Devuelve la desviacion estandar'''
-            while not vertice_random:
+
-                vertice_random = random.choice(lista_claves)
+    sumatoria = 0
-            recorrido.append(vertice_random)
+    for vertice in grafo.vertices:
         grado_vertice = 0
-        vertice_partida = recorrido[cont_recorrido]
+        for adyacente in grafo.adyacentes(vertice):
             grado_vertice += 1
-        while cont_recorrido < largo:
+        sumatoria += (grado_vertice - grado_grafo /cantidad_vertices)**2
-            if not vertice_partida: break
+    desvio_estandar = ((1/(cantidad_vertices - 1))* sumatoria)**(0.5)
-            diccionario_adyacentes = self.vertices[vertice_partida]
+    return desvio_estandar
-            if pesado:
+
-                vertice_random = vertice_random_por_peso(diccionario_adyacentes)
+
-            else:
+def op_estadisticas(grafo):
-                lista_claves = list(self.vertices[vertice_partida].keys())
+
-                vertice_random = random.choice(lista_claves)
+    cantidad_vertices = grafo.cant_vertices
-
+    cantidad_aristas = grafo.cant_aristas
-            recorrido.append(vertice_random)
+    grado_total = grafo.grado()
-            cont_recorrido+= 1
+    desv_std = desviacion_estandar(grafo, grado_total, cantidad_vertices)
-            vertice_partida = recorrido[cont_recorrido]
+    numero_max_aristas = cantidad_vertices * (cantidad_vertices - 1)
 
     print("Cantidad de vertices: {}".format(cantidad_vertices))
-        return recorrido
+    print("Cantidad de aristas: {}".format(cantidad_aristas))
-
+    print("Promedio del grado de cada vértice: %.2f" % (grado_total/cantidad_vertices))
-    def dijkstra(self, origen, destino, minimo = True):
+    print("Desvio estándar del grado de cada vértice: %.2f" % (desv_std))
     print("Densidad del grafo: %.6f" % (cantidad_aristas/numero_max_aristas))
-        '''Devuelve el recorrido dependiendo si es maximo o minimo desde el
+
-            origen hasta el destino, aplicando el algoritmo de Dijkstra.
+
-           Parametros:
+def max_freq(list_adyacentes, nodos):
-            * minimo: indica si el camino devuelto sera el minimo si minimo es True
+
-              devolvera el maximo si es False
+    mayor_freq = {}
-            * origen y destino: identificadores de vertices dentro del grafo.
+    for adyacente in list_adyacentes: #Contador de frecuencia de cada label
-              Si alguno de estos no existe dentro del grafo, lanzara KeyError.
+        label = nodos[adyacente].label_act
-           Devuelve:
+        if not label in mayor_freq:
-            * Listado de vertices (identificadores) ordenado con el recorrido, incluyendo
+            mayor_freq[label] = 0
-              a los vertices de origen y destino. En caso que no exista camino entre
+        mayor_freq[label] += 1
-              el origen y el destino, se devuelve None.
+
-        '''
+    label_mayor_freq = 0
-        heap = []
+    frecuencia = 0
-        camino = []
+
-        for vertice in self.vertices:
+    for label in mayor_freq: # Detector del que tiene mayor frecuencia
-            nodo = self.nodos[vertice]
+        if mayor_freq[label] > frecuencia:
-            nodo.visitado = False
+            label_mayor_freq = label
-            nodo.distancia = math.inf
+            frecuencia = mayor_freq[label]
-            if vertice == origen:
+
-                heapq.heappush(heap,nodo)
+    return label_mayor_freq
-                nodo.distancia = 0
+
-        while heap:
+def _op_comunidades(grafo, nodos):
-            nodo = heapq.heappop(heap)
+
-            nodo.visitado = True
+    comunidades = {} #label : [vertices]
-            vertice = nodo.vertice
+    for vertice in nodos:
-            dist = nodo.distancia
+        nodos[vertice].label = max_freq(grafo.adyacentes(vertice), nodos)
-            for adyacente in self.vertices[vertice]:
+        label = nodos[vertice].label
-                if not adyacente: continue
+        if not label in comunidades:
-                peso = self.vertices[vertice][adyacente]
+            comunidades[label] = []
-                nodo_ad = self.nodos[adyacente]
+        comunidades[label].append(vertice)
-                if not nodo_ad.visitado and nodo_ad.distancia > (dist + peso):
+
-
+    eliminar = []
-                    if minimo:
+    for comunidad in comunidades:
-                        nodo_ad.cambiar_dist(dist + peso)
+        if len(comunidades[comunidad]) <= 4 or len(comunidades[comunidad]) >= 1000:
-                    else:
+            eliminar.append(comunidad)
-                        nodo_ad.cambiar_dist(dist + 1/peso)
+
-                    nodo_ad.cambiar_padre(vertice)
+    for comunidad in eliminar:
-                    heapq.heappush(heap,nodo_ad)
+        comunidades.pop(comunidad)
 
-        vertice = destino
+    return comunidades
-        camino.append(vertice)
+
-        while vertice != origen:
+
-            padre = self.nodos[vertice].padre
+def op_comunidades(grafo):
-            camino.append(padre)
+    nodos = grafo.nodos
-            vertice = padre
+    comunidades = _op_comunidades(grafo, nodos)
-        return camino
+    desigualdad = False
     while True:
         test_comunidad = _op_comunidades(grafo,nodos)
         if comunidades == test_comunidad: break
-    def bfs(self, inicio = None, visitar = None, extra = None):
+        comunidades = test_comunidad
     for i, comunidad in enumerate(comunidades):
-        '''Realiza un recorrido BFS dentro del grafo
+        print("\n\nCantidad de Integrantes: {}".format(len(comunidades[comunidad])))
-        Parametros:
+        imprimir_personajes(grafo, comunidades[comunidad])
-            - 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:
+def verificar_personaje(grafo, personaje):
-            Tupla (padres, orden), donde :
+    if not personaje in grafo.personajes:
-                - '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)
+        intentos = 0
-                - 'orden' es un diccionario que indica para un identificador, cual es su orden en el recorrido BFS
+        while intentos < 5 and not personaje in grafo.personajes:
-        '''
+            personaje = input("El personaje no se encuentra en la base de datos, vuelva a ingresar: ")
-        padres = {}
+            personaje = personaje.upper()
-        orden = {}
+            intentos += 1
         if intentos == 5 and not personaje in grafo.personajes:
-        for nodo in self.nodos:
+            return False
-            nodo = self.nodos[nodo]
+    return personaje
-            nodo.visitado = False
+
-            padres[nodo.vertice] = None
+def verificar_numero(opcion):
-            orden[nodo.vertice] = math.inf
+    if not opcion.isdigit():
         intentos = 0
-        if inicio:
+        while intentos < 5 and not opcion.isdigit():
-            nodo = self.nodos[inicio]
+            opcion = input("Vuelva a seleccionar la cantidad: ")
-            vertice = inicio
+            intentos += 1
-        else:
+        if intentos == 5 or not opcion.isdigit(): return False
-            nodos = list(self.nodos.keys())
+    return opcion
-            vertice = random.choice(nodos)
+
-            nodo = self.nodos[vertice]
+
-        vertice_origen = vertice
+
-        padres[vertice] = None
+def menu(grafo):
-        nodo.visitado = True
+    print("************** MENU - MARVEL ***************")
-        orden[vertice] = 0
+    print("1- Recomendados")
-        cola = deque([])
+    print("2- Similares")
-        cola.append(nodo)
+    print("3- Centralidad")
-        while cola:
+    print("4- Camino")
-            nodo = cola.popleft()
+    print("5- Distancias")
-            vertice = nodo.vertice
+    print("6- Estadisticas")
-            if visitar and not visitar(nodo,extra): break
+    print("7- Comunidades")
-            for adyacente in self.vertices[vertice]:
+    print("8- Salir")
-                nodo_ad = self.nodos[adyacente]
+    opcion = input("Ingrese una opcion: ")
-                if nodo_ad.visitado == False:
+    print("")
-                    nodo_ad.visitado = True
+    posibilidades = 0
-                    cola.append(nodo_ad)
+    while not opcion in OPCIONES and posibilidades != 5 :
-                    orden[adyacente] = orden[vertice] + 1
+        print("Error al ingresar la opcion")
-                    padres[adyacente] = vertice
+        opcion = input("Ingrese una opcion nuevamente: ")
         posibilidades += 1
-        return (orden, padres, vertice_origen)
+
     if posibilidades == 5: return
 
-class Nodo_Grafo():
+    opcion = int(opcion)
 
-    def __init__(self, vertice, nombre, distancia = 0, visitado = False, padre = None):
+    if opcion == 1:
-        self.vertice = vertice
+        print("************** Recomendados ***************")
-        self.distancia = distancia
+        personaje = input("Ingrese el nombre del personaje: ")
-        self.visitado = visitado
+        personaje = personaje.upper()
-        self.padre = padre
+        personaje = verificar_personaje(grafo, personaje)
-        self.nombre = nombre
+        if not personaje: return
-        self.label_act = int(vertice)
+        cantidad = input("Ingrese cantidad de recomendados: ")
         cantidad = verificar_numero(cantidad)
-    def visitado(self):
+        if not cantidad: return
-        return self.visitado
+        op_recomendados(grafo, personaje, cantidad)
 
-    def cambiar_dist(self, distancia_nueva):
+    elif opcion == 2:
-        self.distancia = distancia_nueva
+        print("************** Similares ***************")
         personaje = input("Ingrese el nombre del personaje: ")
-    def cambiar_padre(self, padre_nuevo):
+        personaje = personaje.upper()
-        self.padre = padre_nuevo
+        personaje = verificar_personaje(grafo, personaje)
         if not personaje: return
-    def __lt__(self,otro):
+        cantidad = input("Ingrese cantidad de similares: ")
-        return self.distancia < otro.distancia
+        cantidad = verificar_numero(cantidad)
         if not cantidad: return
-    def __gt__(self,otro):
+        op_similares(grafo, personaje, cantidad)
-        return self.distancia > otro.distancia
+
     elif opcion == 3:
-    def __eq__(self,otro):
+        print("************** Centralidad ***************")
-        return self.distancia == otro.distancia
+        cantidad = input("Ingrese cantidad de personajes centrales: ")
         cantidad = verificar_numero(cantidad)
-    def __str__(self):
+        if not cantidad: return
-        return str(self.vertice)+"; "+str(self.distancia)
+        op_centralidad(grafo, cantidad)
 
     elif opcion == 4:
-def vertice_random_por_peso(diccionario_adyacentes):
+        print("************** Camino ***************")
-    '''Devuelve un vertice adyacente random, con altas prioridades de que su peso sea mayor al de los demas'''
+        personaje1 = input("Ingrese el nombre del personaje de origen: ")
         personaje1 = personaje1.upper()
-    total = sum(diccionario_adyacentes.values())
+        personaje1 = verificar_personaje(grafo, personaje1)
-    rand = random.uniform(0, total)
+        if not personaje1: return
-    acum = 0
+        personaje2 = input("Ingrese el nombre del personaje de destino: ")
-    for vertice, peso_arista in diccionario_adyacentes.items():
+        personaje2 = personaje2.upper()
-        if acum + peso_arista >= rand:
+        personaje2 = verificar_personaje(grafo, personaje2)
-            return vertice
+        if not personaje2: return
-        acum += peso_arista
+        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()