bgneal@0: """ Code example from Complexity and Computation, a book about
bgneal@0: exploring complexity science with Python.  Available free from
bgneal@0: 
bgneal@0: http://greenteapress.com/complexity
bgneal@0: 
bgneal@0: Copyright 2011 Allen B. Downey.
bgneal@0: Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
bgneal@0: """
bgneal@0: 
bgneal@0: class Vertex(object):
bgneal@0:     """A Vertex is a node in a graph."""
bgneal@0: 
bgneal@0:     def __init__(self, label=''):
bgneal@0:         self.label = label
bgneal@0: 
bgneal@0:     def __repr__(self):
bgneal@0:         """Returns a string representation of this object that can
bgneal@0:         be evaluated as a Python expression."""
bgneal@0:         return 'Vertex(%s)' % repr(self.label)
bgneal@0: 
bgneal@0:     __str__ = __repr__
bgneal@0:     """The str and repr forms of this object are the same."""
bgneal@0: 
bgneal@0: 
bgneal@0: class Edge(tuple):
bgneal@0:     """An Edge is a list of two vertices."""
bgneal@0: 
bgneal@0:     def __new__(cls, *vs):
bgneal@0:         """The Edge constructor takes two vertices."""
bgneal@0:         if len(vs) != 2:
bgneal@0:             raise ValueError, 'Edges must connect exactly two vertices.'
bgneal@0:         return tuple.__new__(cls, vs)
bgneal@0: 
bgneal@0:     def __repr__(self):
bgneal@0:         """Return a string representation of this object that can
bgneal@0:         be evaluated as a Python expression."""
bgneal@0:         return 'Edge(%s, %s)' % (repr(self[0]), repr(self[1]))
bgneal@0: 
bgneal@0:     __str__ = __repr__
bgneal@0:     """The str and repr forms of this object are the same."""
bgneal@0: 
bgneal@0: 
bgneal@0: class Graph(dict):
bgneal@0:     """A Graph is a dictionary of dictionaries.  The outer
bgneal@0:     dictionary maps from a vertex to an inner dictionary.
bgneal@0:     The inner dictionary maps from other vertices to edges.
bgneal@0:     
bgneal@0:     For vertices a and b, graph[a][b] maps
bgneal@0:     to the edge that connects a->b, if it exists."""
bgneal@0: 
bgneal@0:     def __init__(self, vs=[], es=[]):
bgneal@0:         """Creates a new graph.  
bgneal@0:         vs: list of vertices;
bgneal@0:         es: list of edges.
bgneal@0:         """
bgneal@0:         for v in vs:
bgneal@0:             self.add_vertex(v)
bgneal@0:             
bgneal@0:         for e in es:
bgneal@0:             self.add_edge(e)
bgneal@0: 
bgneal@0:     def add_vertex(self, v):
bgneal@0:         """Add a vertex to the graph."""
bgneal@0:         self[v] = {}
bgneal@0: 
bgneal@0:     def add_edge(self, e):
bgneal@0:         """Adds and edge to the graph by adding an entry in both directions.
bgneal@0: 
bgneal@0:         If there is already an edge connecting these Vertices, the
bgneal@0:         new edge replaces it.
bgneal@0:         """
bgneal@0:         v, w = e
bgneal@0:         self[v][w] = e
bgneal@0:         self[w][v] = e
bgneal@0: 
bgneal@0: 
bgneal@0: def main(script, *args):
bgneal@0:     v = Vertex('v')
bgneal@0:     print v
bgneal@0:     w = Vertex('w')
bgneal@0:     print w
bgneal@0:     e = Edge(v, w)
bgneal@0:     print e
bgneal@0:     g = Graph([v,w], [e])
bgneal@0:     print g
bgneal@0: 
bgneal@0: 
bgneal@0: if __name__ == '__main__':
bgneal@0:     import sys
bgneal@0:     main(*sys.argv)