LAB 08 Grafos
Contents
!wget --no-cache -O init.py -q https://raw.githubusercontent.com/rramosp/20192.L3/master/init.py
import init; init.init(force_download=False); init.get_weblink()
import init
from local.lib.rlxmoocapi import submit, session
import inspect
student = session.Session(init.endpoint).login( course_id=init.course_id,
session_id="UDEA",
lab_id="lab_08" )
LAB 08 Grafos¶
Ejercicio 1¶
crea el constructor de un grafo que se representa como una lista de nodos conectados para cada nodo. Por ejemplo:
g1 = Graph(num_nodes=4, edge_list=[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (2,1)])
print g1.nodes
> {0: [1, 2, 3], 1: [0, 2, 3], 2: [0, 1, 3], 3: [0, 1, 2]}
o también en el caso de un grafo dirigido:
g1 = Graph(num_nodes=4, edge_list=[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (2,1)], is_directed=True)
print g1.nodes
> {0: [1, 2, 3], 1: [2, 3], 2: [1, 3], 3: [], 4: []}
observa que,
si tenemos un grafo dirigido y el lado \((V_i, V_j)\), entonces \(i\) ha de estar en la lista de nodos de \(j\) y viceversa.
en cambio, con un grafo no dirigido, sólo \(i\) ha de estar en la lista de nodos de \(j\).
la lista de nodos conectados con cada nodo ha de quedar compacta, no puede haber nodos repetidos. P.ej. si en la lista de lados se encuentran ambos (5,1) y (1,5), o hay lados repetidos.
si algún nodo no tiene lados salientes en un grafo dirigido, la lista correspondiente a ese nodo quedara vacía.
def Graph1(num_nodes, edge_list, is_directed=False, **kwargs):
import numpy as np
class Graph1_class:
def __init__(self, num_nodes=num_nodes, edge_list=edge_list, is_directed=is_directed, **kwargs):
assert type(edge_list)==list, "edge_list must be a list of tuples"
assert type(num_nodes)==int, "num_nodes must be an int"
for t in edge_list:
assert len(t)==2, "edge_list must be a list of tuples"
assert t[0]<num_nodes and t[0]>=0 and t[1]<num_nodes and t[1]>=0, "edge number not allowed " + str(t)
<-- INGRESA TU CODIGO AQUÍ-->
return Graph1_class(**kwargs)
prueba tu código
g1 = Graph1(4, [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (2,1)])
print(g1.nodes)
g1 = Graph1(5, [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (2,1)], is_directed=True)
print(g1.nodes)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_01");
Ejercicio 2¶
completa el método as_nx para crear el grafo de networkx correspondiente. Revisa la documentación de networkx.Graph y de networkx.DiGraph. Ten en cuenta que:
la clase para grafos no dirigidos es
networkx.Graphla clase para grados dirigidos es
networkx.DiGraphen cualquiera de los dos casos el método para añadir nodos es
add_nodes_fromen cualquiera de los dos casos el método para añadir lados es
add_edge
Una vez hayas implementado tu método, puedes usar draw para visualizar el grafo.
def Graph2(num_nodes, edge_list, is_directed=False, **kwargs):
import numpy as np
import networkx as nx
class Graph2_class:
def __init__(self, num_nodes=num_nodes, edge_list=edge_list, is_directed=is_directed, **kwargs):
assert type(edge_list)==list, "edge_list must be a list of tuples"
assert type(num_nodes)==int, "num_nodes must be an int"
for t in edge_list:
assert len(t)==2, "edge_list must be a list of tuples"
assert t[0]<num_nodes and t[0]>=0 and t[1]<num_nodes and t[1]>=0, "edge number not allowed " + str(t)
< ---- SU CODIGO AQUÍ --->
def as_nx(self):
g = < ---- SU CODIGO AQUÍ --->
return g
def draw(self):
ng = self.as_nx()
nx.drawing.draw(ng, arrows=self.is_directed, with_labels=True,
node_alpha=.2, node_color="blue",
node_size=900, font_color="white")
return Graph2_class(**kwargs)
prueba tu código
import matplotlib.pyplot as plt
%matplotlib inline
g1 = Graph2(5, [(0, 1), (0, 2), (0, 3), (1, 2), (2, 3), (2,4), (3,4)])
g1.draw()
g2 = Graph2(5, [(0,1), (0,2), (1,3), (2,4), (3,4), (3,2)], is_directed=True)
g2.draw()
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_02");
Ejercicio 3¶
implementa los métodos indicados para tu clase con la implementación del grafo como un diccionario de listas de nodos conectados.
def Graph3(num_nodes, edge_list, is_directed=False, **kwargs):
import numpy as np
import networkx as nx
class Graph3_class(object):
def __init__(self, num_nodes=num_nodes, edge_list=edge_list, is_directed=is_directed, **kwargs):
assert type(edge_list)==list, "edge_list must be a list of tuples"
assert type(num_nodes)==int, "num_nodes must be an int"
for t in edge_list:
assert len(t)==2, "edge_list must be a list of tuples"
assert t[0]<num_nodes and t[0]>=0 and t[1]<num_nodes and t[1]>=0, "edge number not allowed " + str(t)
< ---- SU CODIGO AQUÍ --->
def assert_valid_node_number(self, n):
assert n>=0 and n<self.num_nodes, "invalid node number: %d"%n
def grade(self, node_number):
self.assert_valid_node_number(node_number)
return < ---- SU CODIGO AQUÍ --->
def grade_out(self, node_number):
assert self.is_directed, "only directed graphs have in/out grades"
self.assert_valid_node_number(node_number)
return < ---- SU CODIGO AQUÍ --->
def grade_in(self, node_number):
assert self.is_directed, "only directed graphs have in/out grades"
self.assert_valid_node_number(node_number)
return < ---- SU CODIGO AQUÍ --->
def are_adyacent(self, node_number_1, node_number_2):
self.assert_valid_node_number(node_number_1)
self.assert_valid_node_number(node_number_2)
return < ---- SU CODIGO AQUÍ --->
def is_valid_trayectory(self, trayectory):
assert type(trayectory)==list, "trayectory must be a list"
return < ---- SU CODIGO AQUÍ --->
return Graph3_class(**kwargs)
g1 = Graph3(4, [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
for i in range(g1.num_nodes):
print("node",i, ", grade =", g1.grade(i))
g3 = Graph3(4, [(0,1), (1,0), (1,2), (2,0), (2,3)], is_directed=True)
for i in range(g3.num_nodes):
print("node",i, ", grade_in =", g3.grade_in(i),", grade_out =", g3.grade_out(i), ", total grade =", g3.grade(i))
print(g3.are_adyacent(0,1))
print(g3.are_adyacent(3,2))
print(g3.are_adyacent(0,3))
t1 = [ 0, 1, 2, 3]
t2 = [ 0, 2, 1]
t3 = [ 2,0,1,0]
print(" trayectory is_valid ")
for t in [t1, t2, t3]:
print("%20s"%str(t), "%10s"%g3.is_valid_trayectory(t))
g3 = Graph3(6, [(4,2), (0,2), (1,3), (2,1), (5,0), (3,4), (5,1), (0,2), (3,4), (4,5),
(1,4), (1,2), (4,3), (4,1), (4,5), (0,1), (1,4), (2,0), (1,5)], is_directed=True)
for i in range(g3.num_nodes):
print("node",i, ", grade_in =", g3.grade_in(i),", grade_out =", g3.grade_out(i), ", total grade =", g3.grade(i))
t = [2,0,5,1,4,3]
g3.is_valid_trayectory(t)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_03");
Ejercicio 4¶
Realiza el constructor para que inicialice una representación como una matriz de incidencia. Asumamos que tenemos solamente grafos NO dirigidos, no tengas el cuenta el caso de grafos dirigidos.
Una matric de incidencia es una matriz de m filas y n columnas siendo:
m = número vértices del grafo.
n = número lados del grafo.
Lo anterior implica que debemos numerar los lados del grafo. Dicha numeración se hace aleatoriamente, o se puede hacer en secuencia con la lista de lados (edges).
Fíjate en el siguiente grafo de ejemplo y la matriz de incidencia asociada cualquier columna tiene exactamente dos elementos a 1:
g2 = Graph(7, [(1,4),(0,2), (2,5),(0,1), (1,3), (2,6)])
g2.inc_matrix
> [[0 1 0 1 0 0]
> [1 0 0 1 1 0]
> [0 1 1 0 0 1]
> [0 0 0 0 1 0]
> [1 0 0 0 0 0]
> [0 0 1 0 0 0]
> [0 0 0 0 0 1]]
import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline
def Graph4(num_nodes, edge_list, is_directed=False, **kwargs):
import numpy as np
class Graph4_class:
def __init__(self, num_nodes=num_nodes, edge_list=edge_list, is_directed=is_directed, **kwargs):
assert type(edge_list)==list, "edge_list must be a list of tuples"
assert type(num_nodes)==int, "num_nodes must be an int"
for t in edge_list:
assert len(t)==2, "edge_list must be a list of tuples"
assert t[0]<num_nodes and t[0]>=0 and t[1]<num_nodes and t[1]>=0, "edge number not allowed " + str(t)
self.num_nodes = num_nodes
< ---- SU CODIGO AQUÍ --->
return Graph4_class(**kwargs)
g2 = Graph4(7, [(1,4),(0,2), (2,5),(0,1), (1,3), (2,6)])
print(g2.inc_matrix)
k = g2.inc_matrix
k.sum(axis=0)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_04");
Ejercicio 5¶
implementa los métodos siguientes para la clase anterior con matrices de incidencia:
gradeare_adyacentis_valid_trayectory
def Graph5(num_nodes, edge_list, is_directed=False, **kwargs):
import numpy as np
class Graph5_class:
def __init__(self, num_nodes=num_nodes, edge_list=edge_list, is_directed=is_directed, **kwargs):
assert type(edge_list)==list, "edge_list must be a list of tuples"
assert type(num_nodes)==int, "num_nodes must be an int"
for t in edge_list:
assert len(t)==2, "edge_list must be a list of tuples"
assert t[0]<num_nodes and t[0]>=0 and t[1]<num_nodes and t[1]>=0, "edge number not allowed " + str(t)
self.num_nodes = num_nodes
< ---- SU CODIGO AQUÍ --->
def assert_valid_node_number(self, n):
assert n>=0 and n<self.num_nodes, "invalid node number: %d"%n
def grade(self, node_number):
self.assert_valid_node_number(node_number)
return < ---- SU CODIGO AQUÍ --->
def are_adyacent(self, node_number_1, node_number_2):
self.assert_valid_node_number(node_number_1)
self.assert_valid_node_number(node_number_2)
return < ---- SU CODIGO AQUÍ --->
def is_valid_trayectory(self, trayectory):
assert type(trayectory)==list, "trayectory must be a list"
return < ---- SU CODIGO AQUÍ --->
return Graph5_class(**kwargs)
g1 = Graph5(4, [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
for i in range(g1.num_nodes):
print("node",i, ", grade =", g1.grade(i))
print(g1.are_adyacent(0,1))
print(g1.are_adyacent(3,2))
print(g1.are_adyacent(0,3))
g3 = Graph5(4, [(0,1), (1,0), (1,2), (2,0), (2,3)])
t1 = [ 0, 1, 2, 3]
t2 = [ 0, 2, 3,1]
t3 = [ 2,0,1,0]
print(" trayectory is_valid ")
for t in [t1, t2, t3]:
print("%20s"%str(t), "%10s"%g3.is_valid_trayectory(t))
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_05");