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()))

"""
Explanation: Ejercicios Graphs, Paths & Components
Ejercicios 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):
End of explanation
"""


"""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))

"""
Explanation: 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)
End of explanation
"""


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))

"""
Explanation: D## Ejercicio - Sparseness
Calcule 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.
End of explanation
"""


""" 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)



"""
Explanation: En la matriz de adyacencia de cada uno de las redes elegidas, cuantos ceros hay?
End of explanation
"""


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())

"""
Explanation: Ejercicio - Redes Bipartitas
Defina una red bipartita y genere ambas proyecciones, explique qué son los nodos y links tanto de la red original como de las proyeccciones
End of explanation
"""


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))))

"""
Explanation: Explicación
Los 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 - Paths
Cree 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
End of explanation
"""


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=" ")

"""
Explanation: Ejercicio - Componentes
Baje una red real (http://snap.stanford.edu/data/index.html) y lea el archivo
End of explanation
"""


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)))

"""
Explanation: Utilizando NetworkX o iGraph descubra el número de componentes
End of explanation
"""


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 Mann, Edd. 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)))

"""
Explanation: Implemente el algorithmo Breadth First para encontrar el número de componentes (revise que el resultado es el mismo que utilizando la librería)
End of explanation
"""


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()))

"""
Explanation: 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
End of explanation
"""


""" 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)

"""
Explanation: Calcule el grado promedio
End of explanation
"""


N = 5

"""
Explanation: Ejercicio - Diámetro
End of explanation
"""


""" 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)

"""
Explanation: Cree un grafo de N nodos con el máximo diámetro posible
End of explanation
"""


""" 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)

"""
Explanation: Cree un grafo de N nodos con el mínimo diámetro posible
End of explanation
"""


""" 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)

"""
Explanation: Cree un grafo de N nodos que sea un ciclo simple
End of explanation
"""


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')]

"""
Explanation: Ejercicio - Pregunta "real"
Una aerolínea tiene las siguientes rutas desde las ciudades a las que sirve (cada par tiene servicio en ambas direcciones).
End of explanation
"""


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))

"""
Explanation: 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)
End of explanation
"""


""" 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))


"""
Explanation: 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)
End of explanation
"""


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

nx.draw(G)

"""
Explanation: Visualice la red
End of explanation
"""


