<jupyter_start><jupyter_text>Ejercicios Graphs, Paths & ComponentsEjercicios básicos de Grafos.  Ejercicio - Número de Nodos y Enlaces_ (resuelva en código propio y usando la librería NetworkX (python) o iGraph (R)) _Cuente el número de nodos y enlaces con los siguientes links (asumiendo que el grafo puede ser dirigido Y no dirigido):<jupyter_code>edges = set([(1, 2), (3, 1), (3, 2), (2, 4)])
edges = set([(1, 2), (3, 1), (3, 2), (2, 4)])
edges_list = [i[0] for i in edges] + [i[1] for i in edges]
nodes = set(edges_list)

edges_number = len(edges)
nodes_number = len(nodes)

print ("Número de nodos: " + str(nodes_number))
print ("Número de enlaces: " + str(edges_number))

"""Now using NetorkX"""
import networkx as nx

G = nx.Graph()
G.add_edges_from(edges)

print ("Número de nodos: " + str(G.number_of_nodes()))
print ("Número de aristas: " + str(G.number_of_edges()))<jupyter_output>Número de nodos: 4
Número de enlaces: 4
Número de nodos: 4
Número de aristas: 4<jupyter_text>Ejercicio - Matriz de Adyacencia_ (resuelva en código propio y usando la librería NetworkX (python) o iGraph (R)) _Cree la matriz de adyacencia del grafo del ejercicio anterior (para dirigido y no-dirigido)<jupyter_code>"""Código propio"""
import numpy as np

edges = set([(1,2), (3, 1), (3, 2), (2, 4)])

def adj_matrix_dgraph(edges):
    edges_list = [i[0] for i in edges] + [i[1] for i in edges]
    nodes = set(edges_list)
    
    """create matrix"""
    matrix = np.zeros((len(nodes),len(nodes)))
    
    for edge in edges:
        matrix[edge[0] - 1,edge[1] -1] = 1
    
    return matrix

def adj_matrix(edges):
    edges_list = [i[0] for i in edges] + [i[1] for i in edges]
    nodes = set(edges_list)
    
    """create matrix"""
    matrix = np.zeros((len(nodes),len(nodes)))
    
    for edge in edges:
        i = edge[0]-1
        j = edge[1]-1
        matrix[i,j] = 1
        matrix[j,i] = 1
    
    return matrix

print ("matriz para grafo dirigido:\n" + str(adj_matrix_dgraph(edges)))
print ("\n")
print ("matriz para grafo no dirigido:\n" + str(adj_matrix(edges)))

"""Solución con NetworkX"""

import networkx as nx
G = nx.Graph()
G.add_edges_from(edges)

matrix = nx.adjacency_matrix(G)

print (matrix)

DG = nx.DiGraph()
DG.add_edges_from(edges)

print ("\n")
print (nx.adjacency_matrix(DG))<jupyter_output>matriz para grafo dirigido:
[[ 0.  1.  0.  0.]
 [ 0.  0.  0.  1.]
 [ 1.  1.  0.  0.]
 [ 0.  0.  0.  0.]]


matriz para grafo no dirigido:
[[ 0.  1.  1.  0.]
 [ 1.  0.  1.  1.]
 [ 1.  1.  0.  0.]
 [ 0.  1.  0.  0.]]
  (0, 1)	1
  (0, 2)	1
  (1, 0)	1
  (1, 2)	1
  (1, 3)	1
  (2, 0)	1
  (2, 1)	1
  (3, 1)	1


  (0, 1)	1
  (1, 3)	1
  (2, 0)	1
  (2, 1)	1<jupyter_text>D Ejercicio - SparsenessCalcule la proporción entre número de links existentes en 3 redes reales (http://snap.stanford.edu/data/index.html) contra el número de links posibles.<jupyter_code>import numpy as np

""" The entered datasets correspond to non-directed graphs"""
""" information about the dataset can be found in the following link:
    http://snap.stanford.edu/data/egonets-Facebook.html """

edges1 = np.genfromtxt('0.edges', dtype="int", delimiter=" ")

edges2 = np.genfromtxt('348.edges', dtype="int", delimiter=" ")

edges3 = np.genfromtxt('414.edges', dtype="int", delimiter=" ")

def edges_to_nodes(edges):
    edges_list = [i[0] for i in edges] + [i[1] for i in edges]
    nodes = set(edges_list)
    
    return nodes


def edge_rate(edges):
    nodes = edges_to_nodes(edges)
    n = len(nodes)
    
    print ("len(n) = %d" %(n))
    
    """ For a non-directed graph and excluding reflexive relations"""
    possible_edges = (n*(n-1))/2
    
    print ("possible_edges=%d" % (possible_edges))
    result = float(len(edges))/possible_edges
    return result

def edge_rate_dgraph(edges):
    nodes = edges_to_nodes(edges)
    n = len(nodes)
    
    """ For a directed graph including reflexive relations"""
    possible_edges = n**2
    result = float(len(edges))/possible_edges
    return result

print (edge_rate(edges1))
print (edge_rate(edges2))
print (edge_rate(edges3))

""" With networkx """

import networkx as nx

G1 = nx.read_edgelist('0.edges', delimiter=" ")
G2 = nx.read_edgelist('348.edges', delimiter=" ")
G3 = nx.read_edgelist('414.edges', delimiter=" ")


def possible_edges(graph):
    nodes = graph.number_of_nodes()
    return (nodes*(nodes-1))/2

print ("possible_edges(G1)=%d" % (possible_edges(G1)))

def edge_rate_nx(graph):
    return float(graph.number_of_edges())/float(possible_edges(graph))

print ("\n")
print (edge_rate_nx(G1))
print (edge_rate_nx(G2))
print (edge_rate_nx(G3))<jupyter_output>len(n) = 333
possible_edges=55278
0.09113933210318753
len(n) = 224
possible_edges=24976
0.2556053811659193
len(n) = 150
possible_edges=11175
0.3029977628635347
possible_edges(G1)=55278


0.045569666051593766
0.12780269058295965
0.15149888143176735<jupyter_text>En la matriz de adyacencia de cada uno de las redes elegidas, cuantos ceros hay?<jupyter_code>""" Without NetworkX """
import numpy as np

def edges_to_nodes(edges):
    edges_list = [i[0] for i in edges] + [i[1] for i in edges]
    nodes = set(edges_list)
    print ("len(nodes)=%d" %(len(nodes)))
    return nodes

""" The entered datasets correspond to non-directed graphs"""
""" information about the dataset can be found in the following link:
    http://snap.stanford.edu/data/egonets-Facebook.html """

edges1 = np.genfromtxt('0.edges', dtype="int", delimiter=" ")
print (len(edges1))

edges2 = np.genfromtxt('348.edges', dtype="int", delimiter=" ")
print (len(edges2))

edges3 = np.genfromtxt('414.edges', dtype="int", delimiter=" ")
print (len(edges3))

""" Asuming there aren't repeated elements in the dataset """

def number_of_zeroes(edges):
    n = len(edges_to_nodes(edges))
    zeroes = n**2 - len(edges)
    return zeroes

def number_of_zeroes_dgraph(edges):
    n = len(edges_to_nodes(edges))
    zeroes = n**2 - len(edges)
    return zeroes


print ("number_of_zeroes(edges1)=%d" %(number_of_zeroes(edges1)))
print ("number_of_zeroes(edges2)=%d" %(number_of_zeroes(edges2)))
print ("number_of_zeroes(edges3)=%d" %(number_of_zeroes(edges3)))

""" With NetworkX """
import networkx as nx

""" The selected datasets are non-directed graphs. Therefore their adjacency matrix is simetrical """

""" For undirected graphs NetworkX stores only the edges of one of the matrix's triangles (upper or lower)"""

G1 = nx.read_edgelist('0.edges', delimiter=" ")
print (len(G1.edges()))

G2 = nx.read_edgelist('348.edges', delimiter=" ")
print (len(G2.edges()))

G3 = nx.read_edgelist('414.edges', delimiter=" ")
print (len(G3.edges()))

N1 = len(G1.nodes())
N2 = len(G2.nodes())
N3 = len(G3.nodes())

def zeroes(graph):
    N = len(graph.nodes())
    result = N**2 - 2*len(graph.edges())
    print ("zeroes=%d" %(result))
    return result

zeroes(G1)
zeroes(G2)
zeroes(G3)<jupyter_output>2519
3192
1693
zeroes=105851
zeroes=43792
zeroes=19114<jupyter_text>Ejercicio - Redes BipartitasDefina una red bipartita y genere ambas proyecciones, explique qué son los nodos y links tanto de la red original como de las proyeccciones<jupyter_code>import numpy as np

network1 = set([(1,'a'),(3,'b'), (4,'d'),(5,'b'),(1,'b'), (2,'d'), (1,'d'), (3,'c')])

def projection_u(edges):
    edges_list = list(edges)
    result = []
    for i in range(0,len(edges_list)):
        for j in range(i+1, len(edges_list)):
            if edges_list[i][1] == edges_list[j][1]:
                tup = (edges_list[i][0], edges_list[j][0])
                result.append(tup)
    
    return set(result)

print (projection_u(network1))

def projection_v(edges):
    edges_list = list(edges)
    result = []
    for i in range(0,len(edges_list)):
        for j in range(i+1, len(edges_list)):
            if edges_list[i][0] == edges_list[j][0]:
                tup = (edges_list[i][1], edges_list[j][1])
                result.append(tup)
    
    return set(result)

print (projection_v(network1))
""" With NetworkX """
import numpy as np
import networkx as nx
from networkx.algorithms import bipartite

edges = set([(1,'a'),(3,'b'), (4,'d'),(5,'b'),(1,'b'), (2,'d'), (1,'d'), (3,'c')])
B = nx.Graph()
B.add_nodes_from([1,2,3,4,5], bipartite=0)
B.add_nodes_from(['a','b','c','d'], bipartite=1)
B.add_edges_from(edges)

projection_u = bipartite.projected_graph(B, [1,2,3,4,5])
print (projection_u.edges())

projection_v = bipartite.projected_graph(B, ['a','b','c','d'])
print (projection_v.edges())<jupyter_output>[(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5)]
[('a', 'b'), ('a', 'd'), ('b', 'c'), ('b', 'd')]<jupyter_text>ExplicaciónLos nodos de la red original corresponden a elementos pertenecientes a dos conjuntos U y V. Para este caso particular los conjuntos son disjuntos y tienen tipos diferentes de datos. los links de la red original representan relaciones entre ambos conjuntos.En la red de proyecciones de U, los nodos representan elementos de un mismo conjunto y los enlaces representan relaciones entre elementos del mismo conjunto definidas a partir de elementos comunes del conjunto V con el cual un par de elementos x,y del conjunto U se relacionan. i.e. si 'x' y 'y', pertenecientes al conjunto, U se relacionan con un elemento 'w', perteneciente al conjunto V, entonces 'x' se relaciona con 'y', i.e. hay un link entre 'x' y 'y'.Para el caso de las proyecciones de V, la definición varía en que si un par de elementos 'x','y' pertenecientes al conjunto V se relacionan, i.e. hay un link entre ellos, entonces 'x' y 'y' se relacionan en la proyección de V.  Ejercicio - PathsCree un grafo de 5 nodos con 5 enlaces. Elija dos nodos cualquiera e imprima:+ 5 Paths diferentes entre los nodos+ El camino mas corto entre los nodos+ El diámetro de la red+ Un self-avoiding path<jupyter_code>import numpy as np

edges = set([(1,4),(2,3),(2,4),(2,5),(3,4),(4,1),(3,2),(4,2),(5,2),(4,3)])

graph = {1:[4],
         2:[3,4,5],
         3:[2,4],
         4:[3,2],
         5:[2]}

print (edges)
""" From 1 to 5 """
path1 = [1,4,3,2,5]
path2 = [1,4,2,5]
path3 = [1,4,2,3,2,5]
path4 = [1,4,3,4,2,5]
path5 = [1,4,2,4,2,5]

print(path1)
print(path2)
print(path3)
print(path4)
print(path5)

""" Shortest path"""
def find_shortest_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not start in graph:
        return None
    shortest = None
    for node in graph[start]:
        if node not in path:
            newpath = find_shortest_path(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest
print ("Shortest path is: %s" %(str(find_shortest_path(graph,1,5))))
import numpy as np
import networkx as nx

edges = set([(1,4),(2,3),(2,4),(2,5),(3,4),(4,1),(3,2),(4,2),(5,2),(4,3)])

G = nx.Graph()
G.add_edges_from(edges)

for path in nx.all_simple_paths(G, source=1,target=5):
    print (path)
    
print ("Shortest path is: %s" %(str(nx.shortest_path(G,source=1,target=5))))<jupyter_output>[1, 4, 3, 2, 5]
[1, 4, 2, 5]
Shortest path is: [1, 4, 2, 5]<jupyter_text>Ejercicio - ComponentesBaje una red real (http://snap.stanford.edu/data/index.html) y lea el archivo<jupyter_code>import numpy as np

""" The entered datasets correspond to non-directed graphs"""
""" information about the dataset can be found in the following link:
    http://snap.stanford.edu/data/egonets-Facebook.html """

edges1 = np.genfromtxt('0.edges', dtype="int", delimiter=" ")
""" With NetworkX """
import numpy as np
import networkx as nx

G1 = nx.read_edgelist('0.edges', delimiter=" ")<jupyter_output><empty_output><jupyter_text>Utilizando NetworkX o iGraph descubra el número de componentes<jupyter_code>import numpy as np
import networkx as nx

G = nx.read_edgelist('0.edges', delimiter=" ")

print ("number_connected_components=%d" %(nx.number_connected_components(G)))<jupyter_output>number_connected_components=5<jupyter_text>Implemente el algorithmo Breadth First para encontrar el número de componentes (revise que el resultado es el mismo que utilizando la librería)<jupyter_code>import numpy as np
import collections
from IPython.core.debugger import Tracer

""" The entered datasets correspond to non-directed graphs"""
""" information about the dataset can be found in the following link:
    http://snap.stanford.edu/data/egonets-Facebook.html """

edges1 = np.genfromtxt('0.edges', dtype="int", delimiter= " ")

edges2 = set([(1,2),(2,3),(2,4),(3,4),(4,5),(4,6),(7,)])


e = list(edges2)

print ("Tuple 5 is:" + str(e[4][0]))
print ("Tuple 5 is:" + str(e[4][0]))

""" This method is for undirected graphs """

def edges_to_graph(edges):
    edges = list(edges)
    graph = {}
    
    for i in range(0,len(edges)):
        
        if graph.get(edges[i][0], None):
            graph[edges[i][0]].add(edges[i][1])
        else:
            if len(edges[i]) == 2:
                graph[edges[i][0]] = set([edges[i][1]])
            else:
                graph[edges[i][0]] = set([])
        
        if len(edges[i]) == 2:
            if graph.get(edges[i][1], None):
                graph[edges[i][1]].add(edges[i][0])
            else:
                graph[edges[i][1]] = set([edges[i][0]])

    return graph

graph1 = edges_to_graph(edges1)
graph2 = edges_to_graph(edges2)
print (str(edges_to_graph(edges2)))

""" The following code snippet was taken from <NAME>. Depth-First Search and Breadth-First Search in Python.
    http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/ """

def bfs(graph, start):
    visited, queue = set(), collections.deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

def number_connected_components(graph):
    nodes = set(graph.keys())
    num = 0
    while len(nodes):
        root = next(iter(nodes))
        visited = bfs(graph, root)
        nodes = nodes - visited
        num += 1
        
    return num

print (str(number_connected_components(graph2)))

print (str(number_connected_components(graph1)))<jupyter_output>Tuple 5 is:7
Tuple 5 is:7
{1: {2}, 2: {1, 3, 4}, 4: {2, 3, 5, 6}, 6: {4}, 5: {4}, 3: {2, 4}, 7: set()}
2
5<jupyter_text>Ejercicio - Degree distribution_ (resuelva en código propio y usando la librería NetworkX (python) o iGraph (R)) _Haga un plot con la distribución de grados de la red real<jupyter_code>import numpy as np
import networkx as nx
import seaborn as sns

%matplotlib inline

edges1 = np.genfromtxt('0.edges', dtype="int", delimiter=" ")

graph1 = edges_to_graph(edges1)

def degrees(graph):
    degrees = {}
    for node, links in graph.items():
        degrees[node] = len(links)
    return degrees

d = degrees(graph1)

ax = sns.distplot(list(d.values()))

""" With NetworkX """
G = nx.read_edgelist('0.edges', delimiter=" ")

print (G.degree())

bx = sns.distplot(list(G.degree().values()))<jupyter_output>{'236': 36, '186': 43, '122': 62, '285': 46, '24': 15, '346': 26, '271': 72, '304': 54, '176': 13, '9': 56, '130': 15, '329': 29, '204': 21, '213': 38, '252': 64, '332': 42, '82': 33, '65': 11, '276': 17, '26': 67, '280': 42, '272': 44, '211': 29, '199': 46, '84': 12, '133': 17, '62': 25, '239': 58, '172': 40, '322': 71, '53': 30, '3': 16, '170': 45, '175': 16, '46': 4, '56': 77, '254': 16, '194': 18, '231': 20, '117': 5, '127': 15, '135': 9, '103': 15, '188': 47, '23': 16, '116': 16, '73': 9, '299': 19, '288': 3, '315': 55, '119': 61, '323': 38, '48': 21, '57': 14, '200': 56, '98': 48, '313': 36, '63': 5, '344': 8, '67': 75, '118': 35, '325': 38, '277': 64, '134': 18, '270': 3, '76': 2, '36': 10, '223': 26, '274': 13, '88': 19, '21': 64, '339': 26, '108': 12, '197': 15, '169': 37, '275': 9, '273': 8, '83': 6, '28': 12, '312': 25, '242': 23, '214': 16, '20': 14, '307': 3, '71': 2, '333': 7, '207': 2, '168': 10, '308': 23, '341': 11, '128': 27, '334': 27, '238': 22, '265': 26, '141': 27[...]<jupyter_text>Calcule el grado promedio<jupyter_code>""" Without NetworkX """

def k_mean(graph):
    d = degrees(graph)
    
    return (float(sum(d.values()))/len(d))

print (k_mean(graph1))

""" With NetworkX """
d_nx = G.degree()
k_mean_nx = sum(d_nx.values())/len(d_nx)
print (k_mean_nx)<jupyter_output>15.12912912912913
15.12912912912913<jupyter_text>Ejercicio - Diámetro<jupyter_code>N = 5<jupyter_output><empty_output><jupyter_text>Cree un grafo de N nodos con el máximo diámetro posible<jupyter_code>""" This is a method for undirected graphs """
def max_k(number_of_nodes):
    edges = []
    for i in range(1, number_of_nodes):
        edges.append((i, i+1))
    
    graph = edges_to_graph(edges)
    return graph

G = max_k(100)
print(G)<jupyter_output>{1: {2}, 2: {1, 3}, 3: {2, 4}, 4: {3, 5}, 5: {4, 6}, 6: {5, 7}, 7: {8, 6}, 8: {9, 7}, 9: {8, 10}, 10: {9, 11}, 11: {10, 12}, 12: {11, 13}, 13: {12, 14}, 14: {13, 15}, 15: {16, 14}, 16: {17, 15}, 17: {16, 18}, 18: {17, 19}, 19: {18, 20}, 20: {19, 21}, 21: {20, 22}, 22: {21, 23}, 23: {24, 22}, 24: {25, 23}, 25: {24, 26}, 26: {25, 27}, 27: {26, 28}, 28: {27, 29}, 29: {28, 30}, 30: {29, 31}, 31: {32, 30}, 32: {33, 31}, 33: {32, 34}, 34: {33, 35}, 35: {34, 36}, 36: {35, 37}, 37: {36, 38}, 38: {37, 39}, 39: {40, 38}, 40: {41, 39}, 41: {40, 42}, 42: {41, 43}, 43: {42, 44}, 44: {43, 45}, 45: {44, 46}, 46: {45, 47}, 47: {48, 46}, 48: {49, 47}, 49: {48, 50}, 50: {49, 51}, 51: {50, 52}, 52: {51, 53}, 53: {52, 54}, 54: {53, 55}, 55: {56, 54}, 56: {57, 55}, 57: {56, 58}, 58: {57, 59}, 59: {58, 60}, 60: {59, 61}, 61: {60, 62}, 62: {61, 63}, 63: {64, 62}, 64: {65, 63}, 65: {64, 66}, 66: {65, 67}, 67: {66, 68}, 68: {67, 69}, 69: {68, 70}, 70: {69, 71}, 71: {72, 70}, 72: {73, 71}, 73: {72, 74}, 74: {73[...]<jupyter_text>Cree un grafo de N nodos con el mínimo diámetro posible<jupyter_code>""" This is a method for undirected graphs """
def clique(number_of_nodes):
    edges = []
    for i in range(1, number_of_nodes+1):
        for j in range (1, number_of_nodes+1):
            if (i != j):
                edges.append((i, j))
    
    graph = edges_to_graph(edges)
    return graph

G = clique(10)
print(G)<jupyter_output>{1: {2, 3, 4, 5, 6, 7, 8, 9, 10}, 2: {1, 3, 4, 5, 6, 7, 8, 9, 10}, 3: {1, 2, 4, 5, 6, 7, 8, 9, 10}, 4: {1, 2, 3, 5, 6, 7, 8, 9, 10}, 5: {1, 2, 3, 4, 6, 7, 8, 9, 10}, 6: {1, 2, 3, 4, 5, 7, 8, 9, 10}, 7: {1, 2, 3, 4, 5, 6, 8, 9, 10}, 8: {1, 2, 3, 4, 5, 6, 7, 9, 10}, 9: {1, 2, 3, 4, 5, 6, 7, 8, 10}, 10: {1, 2, 3, 4, 5, 6, 7, 8, 9}}<jupyter_text>Cree un grafo de N nodos que sea un ciclo simple<jupyter_code>""" This is a method for undierected graphs """
def simple_loop(number_of_nodes):
    edges = []
    for i in range(1, number_of_nodes):
        edges.append((i,i+1))
    
    edges.append((number_of_nodes,1))
    graph = edges_to_graph(edges)
    
    return graph

G = simple_loop(5)
print(G)<jupyter_output>{1: {2, 5}, 2: {1, 3}, 3: {2, 4}, 4: {3, 5}, 5: {1, 4}}<jupyter_text>Ejercicio - Pregunta "real"Una aerolínea tiene las siguientes rutas desde las ciudades a las que sirve (cada par tiene servicio en ambas direcciones).<jupyter_code>routemap =  [('St. Louis', 'Miami'), 
             ('St. Louis', 'San Diego'), 
             ('St. Louis', 'Chicago'), 
             ('San Diego', 'Chicago'), 
             ('San Diego', 'San Francisco'), 
             ('San Diego', 'Minneapolis'), 
             ('San Diego', 'Boston'), 
             ('San Diego', 'Portland'), 
             ('San Diego', 'Seattle'), 
             ('Tulsa', 'New York'), 
             ('Tulsa', 'Dallas'), 
             ('Phoenix', 'Cleveland'), 
             ('Phoenix', 'Denver'), 
             ('Phoenix', 'Dallas'), 
             ('Chicago', 'New York'), 
             ('Chicago', 'Los Angeles'), 
             ('Miami', 'New York'), 
             ('Miami', 'Philadelphia'), 
             ('Miami', 'Denver'), 
             ('Boston', 'Atlanta'), 
             ('Dallas', 'Cleveland'), 
             ('Dallas', 'Albuquerque'), 
             ('Philadelphia', 'Atlanta'), 
             ('Denver', 'Minneapolis'), 
             ('Denver', 'Cleveland'), 
             ('Albuquerque', 'Atlanta'), 
             ('Minneapolis', 'Portland'), 
             ('Los Angeles', 'Seattle'), 
             ('San Francisco', 'Portland'), 
             ('San Francisco', 'Seattle'), 
             ('San Francisco', 'Cleveland'), 
             ('Seattle', 'Portland')]<jupyter_output><empty_output><jupyter_text>Cuál es el máximo número de intercambios que tendría que hacer un pasajero en un solo viaje entre dos ciudades servidas? (suponiendo rutas óptimas)<jupyter_code>def edges_to_graph(edges):
    edges = list(edges)
    graph = {}
    
    for i in range(0,len(edges)):
        
        if graph.get(edges[i][0], None):
            graph[edges[i][0]].add(edges[i][1])
        else:
            if len(edges[i]) == 2:
                graph[edges[i][0]] = set([edges[i][1]])
            else:
                graph[edges[i][0]] = set([])
        
        if len(edges[i]) == 2:
            if graph.get(edges[i][1], None):
                graph[edges[i][1]].add(edges[i][0])
            else:
                graph[edges[i][1]] = set([edges[i][0]])

    return graph


""" This function was taken from Python Software Foundation.
    Python Patterns - Implementing Graphs. https://www.python.org/doc/essays/graphs/ 
    (Visited in march 2017) """
def find_shortest_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not start in graph:
        return None
    shortest = None
    for next in graph[start]:
        if next not in path:
            newpath = find_shortest_path(graph, next, end, path)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest

graph1 = edges_to_graph(routemap)

def adjacency_matrix(graph):
    keys = list(graph.keys())
    keys.sort()
    
    adj_matrix = np.zeros((len(keys),len(keys)))
    
    for node, edges in graph.items():
        for edge in edges:
            adj_matrix[keys.index(node)][keys.index(edge)] = 1
    
    return (adj_matrix, keys)
            

adj_matrix = adjacency_matrix(graph1)

def distance_matrix(graph):
    keys = list(graph.keys())
    keys.sort()
    
    d_matrix = np.zeros((len(keys),len(keys)))
    
    for i in range(0, len(keys)):
        for j in range(0, len(keys)):
            start = keys[i]
            end = keys[j]
            path = find_shortest_path(graph, start, end)
            d_matrix[i][j] = len(path)-1
    
    return (d_matrix, keys)


def max_distance(graph):
    result = distance_matrix(graph)
    keys = result[1]
    d_matrix = result[0]
    
    result = 0
    result_i = -1
    result_j = -1
    for i in range(0, len(keys)):
        for j in range(0, len(keys)):
            if d_matrix[i][j] >= result:
                result = d_matrix[i][j]
                result_i = i
                result_j = j
    
    start = keys[result_i]
    end = keys[result_j]
    
    return (start, end, result)

print (distance_matrix(graph1)[0])
print (max_distance(graph1))<jupyter_output>[[ 0.  1.  2.  4.  2.  1.  3.  5.  3.  4.  3.  2.  2.  4.  3.  3.  4.  4.
   2.]
 [ 1.  0.  1.  3.  3.  2.  3.  4.  2.  3.  3.  1.  3.  3.  2.  3.  3.  3.
   3.]
 [ 2.  1.  0.  2.  3.  3.  3.  3.  3.  2.  3.  2.  4.  2.  1.  2.  2.  2.
   4.]
 [ 4.  3.  2.  0.  3.  3.  3.  1.  2.  2.  1.  3.  4.  2.  1.  2.  2.  1.
   2.]
 [ 2.  3.  3.  3.  0.  1.  1.  3.  2.  2.  3.  3.  1.  2.  2.  1.  2.  3.
   2.]
 [ 1.  2.  3.  3.  1.  0.  2.  4.  3.  3.  2.  3.  1.  3.  3.  2.  3.  4.
   1.]
 [ 3.  3.  3.  3.  1.  2.  0.  4.  1.  1.  2.  2.  1.  2.  2.  2.  3.  2.
   3.]
 [ 5.  4.  3.  1.  3.  4.  4.  0.  3.  3.  2.  4.  4.  2.  2.  2.  1.  2.
   3.]
 [ 3.  2.  3.  2.  2.  3.  1.  3.  0.  2.  1.  1.  2.  3.  2.  3.  3.  1.
   2.]
 [ 4.  3.  2.  2.  2.  3.  1.  3.  2.  0.  3.  3.  2.  1.  1.  2.  2.  2.
   4.]
 [ 3.  3.  3.  1.  3.  2.  2.  2.  1.  3.  0.  2.  3.  3.  2.  3.  3.  2.
   1.]
 [ 2.  1.  2.  3.  3.  3.  2.  4.  1.  3.  2.  0.  3.  4.  3.  4.  4.  2.
   3.]
 [ 2.  3.  4.  4.  1.  1.  1[...]<jupyter_text>Si usted necesitara viajar mucho en esta aerolínea, cual sería el lugar óptimo para vivir? (i.e. minimizar el número de intercambios para llegar a cualquier ciudad)<jupyter_code>""" The for optimal place to live I understand the city with the least number of leaps """

def optimal_place(graph):
    result = distance_matrix(graph)
    keys = result[1]
    d_matrix = result[0]
    
    total_leaps = 3000000000
    result_i = -1
    
    for i in range(0, len(keys)):
        current_sum = sum(d_matrix[i])
        if current_sum < total_leaps:
            total_leaps = current_sum
            result_i = i
            
    city = keys[result_i]
    vector = d_matrix[result_i]
    
    return (city, total_leaps, vector)

print (optimal_place(graph1))<jupyter_output>('San Diego', 34.0, array([ 3.,  2.,  1.,  1.,  2.,  3.,  2.,  2.,  2.,  1.,  2.,  3.,  3.,
        1.,  0.,  1.,  1.,  1.,  3.]))<jupyter_text>Visualice la red<jupyter_code>G = nx.Graph()
G.add_edges_from(routemap)

nx.draw(G)<jupyter_output>/home/sangeea/anaconda3/lib/python3.6/site-packages/networkx/drawing/nx_pylab.py:126: MatplotlibDeprecationWarning: pyplot.hold is deprecated.
    Future behavior will be consistent with the long-time default:
    plot commands add elements without first clearing the
    Axes and/or Figure.
  b = plt.ishold()
/home/sangeea/anaconda3/lib/python3.6/site-packages/networkx/drawing/nx_pylab.py:138: MatplotlibDeprecationWarning: pyplot.hold is deprecated.
    Future behavior will be consistent with the long-time default:
    plot commands add elements without first clearing the
    Axes and/or Figure.
  plt.hold(b)
/home/sangeea/anaconda3/lib/python3.6/site-packages/matplotlib/__init__.py:917: UserWarning: axes.hold is deprecated. Please remove it from your matplotlibrc and/or style files.
  warnings.warn(self.msg_depr_set % key)
/home/sangeea/anaconda3/lib/python3.6/site-packages/matplotlib/rcsetup.py:152: UserWarning: axes.hold is deprecated, will be removed in 3.0
  warnings.warn("axes.ho[...]
{'fraction_non_alphanumeric': 0.17306592442902352, 'fraction_numerical': 0.07492278949174515, 'mean_word_length': 3.0202329858982218, 'pattern_counts': {'":': 0, '<': 65, '<?xml version=': 0, '>': 63, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '19', 'dir': 'jupyter-structured-clean-dedup', 'id': '363267', 'license': 'MIT', 'n_tokens_mistral': 11398, 'n_tokens_neox': 10208, 'n_words': 2912, 'path': 'santiagoangee/Ejercicio1.1.ipynb', 'repo_name': 'spulido99/NetworksAnalysis', 'size': '26230'}