grafo.py

    # Recibe un vertice a borrar y elimina todas las relaciones con otros vertices y luego elimina el vertice recibido.
    def borrar_vertice(self, vertice_a_borrar):
        if vertice_a_borrar not in self.vertices: return
        adyacentes = self.adyacentes(vertice_a_borrar)
        for vertice in adyacentes:
            self.vertices[vertice].pop(vertice_a_borrar)
            self.cant_aristas -= 1
        self.vertices.pop(vertice_a_borrar)
        self.cant_vertices -= 1

    # Devuelve el promedio de grado del grafo
    def promedio_grado(self):
        return (2*self.cant_aristas)/self.cant_vertices

    # Devuelve el estimador de máxima verosimilitud de la varianza del promedio del grado del grafo
    def varianza_grado(self):
        sumatoria = 0
        for vertice in self.vertices:
            sumatoria += ((len(self.adyacentes(vertice)) - self.promedio_grado()) ** 2)
        return sumatoria/self.cant_vertices

    # Devuelve el estimador de máxima verosimilitud del desvío estándar del promedio del grado del grafo
    def desvio_estandar_grado(self):
        return math.sqrt(self.varianza_grado())

    def dicc_grados(self):
        dicc_grados = {}
        i=0
        for vertice in self.vertices:
            grado_vertice = len(self.adyacentes(vertice))
            dicc_grados[grado_vertice] = dicc_grados.get(grado_vertice, 0) + 1
        return dicc_grados
************************************************************************************************
tp3.py

from grafo import *
import csv
import sys
import random
import heapq
import nodo_heap
import queue
import merge_sort
import matplotlib.pyplot as plt
import numpy as np
import pylab as pl
from time import time

def similares_recomendar_auxiliar(grafo, vertice_inicial, cantidad_usuarios_semejantes, operacion):
    try:
        if vertice_inicial not in grafo:
            print(MENSAJE_ERROR_USUARIO_INVALIDO)
            return
        puntajes = random_walks(grafo, vertice_inicial, LARGO_RECORRIDO_RW, CANTIDAD_RECORRIDOS_RW, None)
        if operacion.lower() == 's': maximos = k_maximos_diccionario(puntajes, cantidad_usuarios_semejantes, None, vertice_inicial)
        elif operacion.lower() == 'r': maximos = k_maximos_diccionario(puntajes, cantidad_usuarios_semejantes, grafo, vertice_inicial)
        else: raise ValueError
        for nodo in maximos:
            print(nodo.obtener_dato(), end=' ')
        print()
    except ValueError: print("Parámetro operación inválido ('s' o 'r')")

def similares(grafo, vertice_inicial, cantidad_usuarios_semejantes):
    similares_recomendar_auxiliar(grafo, vertice_inicial, cantidad_usuarios_semejantes, "s")

def recomendar(grafo, vertice_inicial, cantidad_usuarios_semejantes):
    similares_recomendar_auxiliar(grafo, vertice_inicial, cantidad_usuarios_semejantes, "r")

#Imprime un histograma de los grados del grafo para analizar su distribución
def histograma_grafos(grafo):
    dicc_grados = grafo.dicc_grados()
    claves_dicc_grados = sorted(dicc_grados)
    suma = 0
    alturas = []
    contador = 0
    tamanio_muestra = len(claves_dicc_grados)
    clases = round(1 + math.log2(tamanio_muestra)) #https://es.wikipedia.org/wiki/Regla_de_Sturges
    long_intervalos = round(tamanio_muestra/clases)
    print(long_intervalos)
    print("tamanio muestra: {}".format(tamanio_muestra))
    for i in range(tamanio_muestra):
        if i==long_intervalos*(contador+1):
            frecuencia = (suma/tamanio_muestra)
            altura = frecuencia/long_intervalos
            print("altura: {}".format(altura))
            alturas.append(altura)
            suma = 0
            contador += 1
        suma += dicc_grados.get(claves_dicc_grados[i])
    x = []
    y = []
    contador = 1
    altura_actual = alturas[0]
    for i in range(tamanio_muestra):
        x.append(i)
        if i==long_intervalos*contador:
            altura_actual = alturas[contador]
            contador += 1
            print(contador)
        y.append(altura_actual)
        if contador >= len(alturas): break
    pl.plot(x, y)
    pl.show()

def estadisticas(grafo):
    vertices = grafo.cantidad_vertices()
    aristas = grafo.cantidad_aristas()
    print("Cantidad de vértices: {}".format(vertices))
    print("Cantidad de aristas: {}".format(aristas))
    if vertices == 0: return
    print("Promedio de grado de cada vértice: {}".format(grafo.promedio_grado()))
    tiempo_i = time()
    print("Varianza de promedio de grado: {}".format(grafo.varianza_grado()))
    print("DEBUG: Termino el calculo de varianza en {}".format(time()-tiempo_i))
    print("Desvio estándar de promedio de grado: {}".format(grafo.desvio_estandar_grado()))
    densidad = 2 * aristas / (vertices * (vertices - 1))
    print("Densidad del grafo: {}".format(densidad))
    histograma_grafos(grafo)