|
bgneal@0
|
1 """ Code example from Complexity and Computation, a book about
|
|
bgneal@0
|
2 exploring complexity science with Python. Available free from
|
|
bgneal@0
|
3
|
|
bgneal@0
|
4 http://greenteapress.com/complexity
|
|
bgneal@0
|
5
|
|
bgneal@0
|
6 Copyright 2011 Allen B. Downey.
|
|
bgneal@0
|
7 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
|
|
bgneal@0
|
8 """
|
|
bgneal@0
|
9
|
|
bgneal@0
|
10 class Vertex(object):
|
|
bgneal@0
|
11 """A Vertex is a node in a graph."""
|
|
bgneal@0
|
12
|
|
bgneal@0
|
13 def __init__(self, label=''):
|
|
bgneal@0
|
14 self.label = label
|
|
bgneal@0
|
15
|
|
bgneal@0
|
16 def __repr__(self):
|
|
bgneal@0
|
17 """Returns a string representation of this object that can
|
|
bgneal@0
|
18 be evaluated as a Python expression."""
|
|
bgneal@0
|
19 return 'Vertex(%s)' % repr(self.label)
|
|
bgneal@0
|
20
|
|
bgneal@0
|
21 __str__ = __repr__
|
|
bgneal@0
|
22 """The str and repr forms of this object are the same."""
|
|
bgneal@0
|
23
|
|
bgneal@0
|
24
|
|
bgneal@0
|
25 class Edge(tuple):
|
|
bgneal@0
|
26 """An Edge is a list of two vertices."""
|
|
bgneal@0
|
27
|
|
bgneal@0
|
28 def __new__(cls, *vs):
|
|
bgneal@0
|
29 """The Edge constructor takes two vertices."""
|
|
bgneal@0
|
30 if len(vs) != 2:
|
|
bgneal@0
|
31 raise ValueError, 'Edges must connect exactly two vertices.'
|
|
bgneal@0
|
32 return tuple.__new__(cls, vs)
|
|
bgneal@0
|
33
|
|
bgneal@0
|
34 def __repr__(self):
|
|
bgneal@0
|
35 """Return a string representation of this object that can
|
|
bgneal@0
|
36 be evaluated as a Python expression."""
|
|
bgneal@0
|
37 return 'Edge(%s, %s)' % (repr(self[0]), repr(self[1]))
|
|
bgneal@0
|
38
|
|
bgneal@0
|
39 __str__ = __repr__
|
|
bgneal@0
|
40 """The str and repr forms of this object are the same."""
|
|
bgneal@0
|
41
|
|
bgneal@0
|
42
|
|
bgneal@0
|
43 class Graph(dict):
|
|
bgneal@0
|
44 """A Graph is a dictionary of dictionaries. The outer
|
|
bgneal@0
|
45 dictionary maps from a vertex to an inner dictionary.
|
|
bgneal@0
|
46 The inner dictionary maps from other vertices to edges.
|
|
bgneal@0
|
47
|
|
bgneal@0
|
48 For vertices a and b, graph[a][b] maps
|
|
bgneal@0
|
49 to the edge that connects a->b, if it exists."""
|
|
bgneal@0
|
50
|
|
bgneal@0
|
51 def __init__(self, vs=[], es=[]):
|
|
bgneal@0
|
52 """Creates a new graph.
|
|
bgneal@0
|
53 vs: list of vertices;
|
|
bgneal@0
|
54 es: list of edges.
|
|
bgneal@0
|
55 """
|
|
bgneal@0
|
56 for v in vs:
|
|
bgneal@0
|
57 self.add_vertex(v)
|
|
bgneal@0
|
58
|
|
bgneal@0
|
59 for e in es:
|
|
bgneal@0
|
60 self.add_edge(e)
|
|
bgneal@0
|
61
|
|
bgneal@0
|
62 def add_vertex(self, v):
|
|
bgneal@0
|
63 """Add a vertex to the graph."""
|
|
bgneal@0
|
64 self[v] = {}
|
|
bgneal@0
|
65
|
|
bgneal@0
|
66 def add_edge(self, e):
|
|
bgneal@0
|
67 """Adds and edge to the graph by adding an entry in both directions.
|
|
bgneal@0
|
68
|
|
bgneal@0
|
69 If there is already an edge connecting these Vertices, the
|
|
bgneal@0
|
70 new edge replaces it.
|
|
bgneal@0
|
71 """
|
|
bgneal@0
|
72 v, w = e
|
|
bgneal@0
|
73 self[v][w] = e
|
|
bgneal@0
|
74 self[w][v] = e
|
|
bgneal@0
|
75
|
|
bgneal@0
|
76
|
|
bgneal@0
|
77 def main(script, *args):
|
|
bgneal@0
|
78 v = Vertex('v')
|
|
bgneal@0
|
79 print v
|
|
bgneal@0
|
80 w = Vertex('w')
|
|
bgneal@0
|
81 print w
|
|
bgneal@0
|
82 e = Edge(v, w)
|
|
bgneal@0
|
83 print e
|
|
bgneal@0
|
84 g = Graph([v,w], [e])
|
|
bgneal@0
|
85 print g
|
|
bgneal@0
|
86
|
|
bgneal@0
|
87
|
|
bgneal@0
|
88 if __name__ == '__main__':
|
|
bgneal@0
|
89 import sys
|
|
bgneal@0
|
90 main(*sys.argv)
|
