Laboratorio 12: Grafos con listas de adyacencia

posted Apr 19, 2013, 6:17 AM by Camilo Rocha   [ updated Apr 19, 2013, 6:43 AM ]
El objetivo de este laboratorio es implementar, finalmente, la estructura de datos Graph para representar grafos dirigidos. La implementción usa una lista de listas como representación interna, en donde cada lista que representa arcos está ordenada ascendentemente. Para implementar la estructura de datos Graph, cada estudiante deberá completar una plantilla con la implementación de algunas funciones que serán probadas con algunos casos de prueba.

A continuación encuentran la especificación de la clase Graph que deben completar:

NAME
    Graph

CLASSES
    builtins.object
        Graph
   
    class Graph(builtins.object)
     |  This class models a graph with a bounded number of vertexes, where
     |  each vertex is represented as a natural number indexed from 0 and
     |  where edges are represented by tuples of arbitrary length. The
     |  convention for edges is that, given a source vertex, the first
     |  component of the tuple representing such an edge corresponds to the
     |  target of the vertex. The remaining components of such a tuple can
     |  be used to store, for instance, the weight of the edge, a label, etc.
     | 
     |  Methods defined here:
     | 
     |  __eq__(self, other)
     |      Return if another object is equal to this object.
     | 
     |  __init__(self, v_count)
     |      This is the constructor of the class. Initially, a graph
     |      has no edges.
     | 
     |  __str__(self)
     |      Return the string representation of the graph.
     | 
     |  add_edge(self, s, t)
     |      Add an edge with source s and target t[0], if not such an edge exists.
     |      Otherwise a ValueError exception is thrown. The argument t must be a tuple.
     |      The values s and t are such that 0 <= s,t[0] < get_vertex_count().
     | 
     |  get_adj_count(self, s)
     |      Return the number of edges with source s, where 0 <= s < get_vertex_count().
     | 
     |  get_edge_at_index(self, s, i)
     |      Return the edge with source s at position i, if any; otherwise throw
     |      a ValueError exception. The values s and i is such that 0 <= s < get_vertex_count()
     |      and 0 <= i < get_adj_count(s).
     | 
     |  get_edge_count(self)
     |      Return the number of edges in the graph.
     | 
     |  get_vertex_count(self)
     |      Return the number of vertexes in the graph.
     | 
     |  has_edge(self, s, t)
     |      Return True if there is an edge from source s to target t; False otherwise.
     |      The values s and t are such that 0 <= s,t < get_vertex_count().
     | 
     |  remove_edge(self, s, t)
     |      Remove the edge with source s and target t if it exists, otherwise
     |      a ValueError exception is thrown.  The values s and t are such
     |      that 0 <= s,t[0] < get_vertex_count().
     | 
     |  update_edge(self, s, t)
     |      Update the edge with source s and target t[0], if such an edge exists.
     |      Otherwise a ValueError exception is thrown. The argument t must be a tuple.
     |      The values s and t are such that 0 <= s,t[0] < get_vertex_count().

Para la implementación, tengan especial cuidado al trabajar con los arcos: identifiquen cuándo un método recibe/retorna un vértice o una tupla (al referirse a un arco).

A continuación encuentran una sesión interactiva con una implementación de la clase Graph:

>>> a = Graph(5)
>>> print(a)
0 -> []
1 -> []
2 -> []
3 -> []
4 -> []
>>> a.add_edge(1,(3,4))
>>> a.add_edge(1,(2,5))
>>> a.add_edge(1,(4,2))
>>> print(a)
0 -> []
1 -> [(2, 5), (3, 4), (4, 2)]
2 -> []
3 -> []
4 -> []
>>> a.has_edge(1,2)
True
>>> a.has_edge(1,0)
False
>>> a.get_vertex_count()
5
>>> a.get_edge_count()
3
>>> a.get_adj_count(1)
3
>>> a.get_adj_count(3)
0
>>> a.get_edge_at_index(1,1)
(3, 4)
>>> a.get_edge_at_index(3,1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "pimo/Graph.py", line 170, in get_edge_at_index
    assert 0 <= i < self.get_adj_count(s)
AssertionError
>>> a.add_edge(3,(5,1))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "pimo/Graph.py", line 104, in add_edge
    assert 0 <= t[0] < self.get_vertex_count()
AssertionError
>>> a.remove_edge(1,2)
>>> a.get_edge_count()
2
>>> print(a)
0 -> []
1 -> [(3, 4), (4, 2)]
2 -> []
3 -> []
4 -> []
>>> a.update_edge(1,(4,6))
>>> print(a)
0 -> []
1 -> [(3, 4), (4, 6)]
2 -> []
3 -> []
4 -> []
>>> a.update_edge(1,(2,4))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "pimo/Graph.py", line 152, in update_edge
    raise ValueError("There is no edge from {0} to {1} to update.".format(str(s),str(t[0])))
ValueError: There is no edge from 1 to 2 to update.
>>>

El laboratorio es individual y cada estudiante debe entregar:
  • El código impreso del archivo pimo/Graph.py completo, con la implementación de todos los métodos.
  • El código impreso del archivo Graph.test.py que implementa al menos 5 pruebas para cada método público de la clase Graph. Además, se debe adjuntar el código impreso de la ejecución de las pruebas.
  • El encabezado de cada archivo debe indicar, usando comentarios de Python,
    • Su nombre en la primera línea
    • Su código de estudiante en la segunda línea
ċ
graph.tar.gz
(1k)
Camilo Rocha,
Apr 19, 2013, 6:42 AM