Laboratorio 12: Grafos con listas de adyacencia

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

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

>>>