|
bgneal@1
|
1 """ Code example from Complexity and Computation, a book about
|
|
bgneal@1
|
2 exploring complexity science with Python. Available free from
|
|
bgneal@1
|
3
|
|
bgneal@1
|
4 http://greenteapress.com/complexity
|
|
bgneal@1
|
5
|
|
bgneal@1
|
6 Copyright 2011 Allen B. Downey.
|
|
bgneal@1
|
7 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
|
|
bgneal@1
|
8 """
|
|
bgneal@1
|
9 import itertools
|
|
bgneal@1
|
10
|
|
bgneal@1
|
11
|
|
bgneal@5
|
12 class GraphError(Exception):
|
|
bgneal@5
|
13 """Exception for Graph errors"""
|
|
bgneal@5
|
14 pass
|
|
bgneal@5
|
15
|
|
bgneal@5
|
16
|
|
bgneal@1
|
17 class Vertex(object):
|
|
bgneal@1
|
18 """A Vertex is a node in a graph."""
|
|
bgneal@1
|
19
|
|
bgneal@1
|
20 def __init__(self, label=''):
|
|
bgneal@1
|
21 self.label = label
|
|
bgneal@1
|
22
|
|
bgneal@1
|
23 def __repr__(self):
|
|
bgneal@1
|
24 """Returns a string representation of this object that can
|
|
bgneal@1
|
25 be evaluated as a Python expression."""
|
|
bgneal@1
|
26 return 'Vertex(%s)' % repr(self.label)
|
|
bgneal@1
|
27
|
|
bgneal@1
|
28 __str__ = __repr__
|
|
bgneal@1
|
29 """The str and repr forms of this object are the same."""
|
|
bgneal@1
|
30
|
|
bgneal@1
|
31
|
|
bgneal@1
|
32 class Edge(tuple):
|
|
bgneal@1
|
33 """An Edge is a list of two vertices."""
|
|
bgneal@1
|
34
|
|
bgneal@1
|
35 def __new__(cls, *vs):
|
|
bgneal@1
|
36 """The Edge constructor takes two vertices."""
|
|
bgneal@1
|
37 if len(vs) != 2:
|
|
bgneal@1
|
38 raise ValueError, 'Edges must connect exactly two vertices.'
|
|
bgneal@1
|
39 return tuple.__new__(cls, vs)
|
|
bgneal@1
|
40
|
|
bgneal@1
|
41 def __repr__(self):
|
|
bgneal@1
|
42 """Return a string representation of this object that can
|
|
bgneal@1
|
43 be evaluated as a Python expression."""
|
|
bgneal@1
|
44 return 'Edge(%s, %s)' % (repr(self[0]), repr(self[1]))
|
|
bgneal@1
|
45
|
|
bgneal@1
|
46 __str__ = __repr__
|
|
bgneal@1
|
47 """The str and repr forms of this object are the same."""
|
|
bgneal@1
|
48
|
|
bgneal@1
|
49
|
|
bgneal@1
|
50 class Graph(dict):
|
|
bgneal@1
|
51 """A Graph is a dictionary of dictionaries. The outer
|
|
bgneal@1
|
52 dictionary maps from a vertex to an inner dictionary.
|
|
bgneal@1
|
53 The inner dictionary maps from other vertices to edges.
|
|
bgneal@1
|
54
|
|
bgneal@1
|
55 For vertices a and b, graph[a][b] maps
|
|
bgneal@1
|
56 to the edge that connects a->b, if it exists."""
|
|
bgneal@1
|
57
|
|
bgneal@6
|
58 def __init__(self, vs=None, es=None):
|
|
bgneal@1
|
59 """Creates a new graph.
|
|
bgneal@1
|
60 vs: list of vertices;
|
|
bgneal@1
|
61 es: list of edges.
|
|
bgneal@1
|
62 """
|
|
bgneal@6
|
63 if vs:
|
|
bgneal@6
|
64 for v in vs:
|
|
bgneal@6
|
65 self.add_vertex(v)
|
|
bgneal@1
|
66
|
|
bgneal@6
|
67 if es:
|
|
bgneal@6
|
68 for e in es:
|
|
bgneal@6
|
69 self.add_edge(e)
|
|
bgneal@1
|
70
|
|
bgneal@1
|
71 def add_vertex(self, v):
|
|
bgneal@1
|
72 """Add a vertex to the graph."""
|
|
bgneal@1
|
73 self[v] = {}
|
|
bgneal@1
|
74
|
|
bgneal@1
|
75 def add_edge(self, e):
|
|
bgneal@1
|
76 """Adds and edge to the graph by adding an entry in both directions.
|
|
bgneal@1
|
77
|
|
bgneal@1
|
78 If there is already an edge connecting these Vertices, the
|
|
bgneal@1
|
79 new edge replaces it.
|
|
bgneal@1
|
80 """
|
|
bgneal@1
|
81 v, w = e
|
|
bgneal@1
|
82 self[v][w] = e
|
|
bgneal@1
|
83 self[w][v] = e
|
|
bgneal@1
|
84
|
|
bgneal@1
|
85 def get_edge(self, v, w):
|
|
bgneal@1
|
86 """Returns the edge object that exists between the two vertices v & w,
|
|
bgneal@1
|
87 or None if no such edge exists.
|
|
bgneal@1
|
88
|
|
bgneal@1
|
89 """
|
|
bgneal@1
|
90 try:
|
|
bgneal@1
|
91 return self[v][w]
|
|
bgneal@1
|
92 except KeyError:
|
|
bgneal@1
|
93 return None
|
|
bgneal@1
|
94
|
|
bgneal@1
|
95 def remove_edge(self, e):
|
|
bgneal@1
|
96 """Removes the edge e from the graph."""
|
|
bgneal@1
|
97
|
|
bgneal@4
|
98 v, w = e
|
|
bgneal@4
|
99 del self[v][w]
|
|
bgneal@4
|
100 del self[w][v]
|
|
bgneal@1
|
101
|
|
bgneal@1
|
102 def vertices(self):
|
|
bgneal@1
|
103 """Returns a list of the vertices in the graph."""
|
|
bgneal@1
|
104
|
|
bgneal@1
|
105 return self.keys()
|
|
bgneal@1
|
106
|
|
bgneal@1
|
107 def edges(self):
|
|
bgneal@1
|
108 """"Returns a list of the edges in the graph."""
|
|
bgneal@1
|
109
|
|
bgneal@1
|
110 edge_set = set()
|
|
bgneal@4
|
111 for d in self.itervalues():
|
|
bgneal@4
|
112 edge_set.update(d.itervalues())
|
|
bgneal@1
|
113
|
|
bgneal@1
|
114 return list(edge_set)
|
|
bgneal@1
|
115
|
|
bgneal@1
|
116 def out_vertices(self, v):
|
|
bgneal@1
|
117 """Returns a list of vertices that are adjacent to the given vertex v.
|
|
bgneal@1
|
118
|
|
bgneal@1
|
119 """
|
|
bgneal@1
|
120 return self[v].keys()
|
|
bgneal@1
|
121
|
|
bgneal@1
|
122 def out_edges(self, v):
|
|
bgneal@1
|
123 """Returns a list of edges connected to a given vertex v."""
|
|
bgneal@1
|
124
|
|
bgneal@1
|
125 return self[v].values()
|
|
bgneal@1
|
126
|
|
bgneal@5
|
127 def remove_all_edges(self):
|
|
bgneal@5
|
128 """Removes all edges in the graph."""
|
|
bgneal@5
|
129 for v in self.iterkeys():
|
|
bgneal@5
|
130 self[v] = {}
|
|
bgneal@5
|
131
|
|
bgneal@1
|
132 def add_all_edges(self):
|
|
bgneal@1
|
133 """Makes the graph complete by adding edges between all pairs of
|
|
bgneal@1
|
134 vertices.
|
|
bgneal@1
|
135
|
|
bgneal@1
|
136 """
|
|
bgneal@1
|
137 # Clear all edges first
|
|
bgneal@5
|
138 self.remove_all_edges()
|
|
bgneal@1
|
139
|
|
bgneal@5
|
140 # For each combination of 2 vertices, create an edge between them:
|
|
bgneal@1
|
141 for v, w in itertools.combinations(self.iterkeys(), 2):
|
|
bgneal@6
|
142 self.add_edge(Edge(v, w))
|
|
bgneal@1
|
143
|
|
bgneal@5
|
144 def add_regular_edges(self, k):
|
|
bgneal@5
|
145 """Makes the graph regular by making every vertex have k edges.
|
|
bgneal@5
|
146
|
|
bgneal@5
|
147 It is not always possible to create a regular graph with a given degree.
|
|
bgneal@5
|
148 If a graph has n vertices, then a regular graph can be constructed with
|
|
bgneal@5
|
149 degree k if n >= k + 1 and n * k is even. If these conditions are not
|
|
bgneal@5
|
150 met a GraphError exception is raised.
|
|
bgneal@5
|
151
|
|
bgneal@5
|
152 """
|
|
bgneal@5
|
153 n = len(self.vertices())
|
|
bgneal@5
|
154 if n < k + 1:
|
|
bgneal@5
|
155 raise GraphError("Can't make a regular graph with degree >= number"
|
|
bgneal@5
|
156 " of vertices")
|
|
bgneal@5
|
157 if (n * k) % 2 != 0:
|
|
bgneal@5
|
158 raise GraphError("Can't make a regular graph of degree k and"
|
|
bgneal@5
|
159 " order n where k * n is odd")
|
|
bgneal@5
|
160
|
|
bgneal@5
|
161 # Remove all edges first
|
|
bgneal@5
|
162 self.remove_all_edges()
|
|
bgneal@5
|
163
|
|
bgneal@5
|
164 if k % 2 != 0: # if k is odd
|
|
bgneal@5
|
165 self._add_regular_edges_even(k - 1)
|
|
bgneal@5
|
166 self._add_regular_edges_odd()
|
|
bgneal@5
|
167 else:
|
|
bgneal@5
|
168 self._add_regular_edges_even(k)
|
|
bgneal@5
|
169
|
|
bgneal@5
|
170 def _add_regular_edges_even(self, k):
|
|
bgneal@5
|
171 """Make a regular graph with degree k. k must be even."""
|
|
bgneal@5
|
172
|
|
bgneal@5
|
173 vs = self.vertices()
|
|
bgneal@5
|
174 vs2 = vs * 2
|
|
bgneal@5
|
175
|
|
bgneal@5
|
176 for i, v in enumerate(vs):
|
|
bgneal@5
|
177 for j in range(1, k / 2 + 1):
|
|
bgneal@5
|
178 w = vs2[i + j]
|
|
bgneal@5
|
179 self.add_edge(Edge(v, w))
|
|
bgneal@5
|
180
|
|
bgneal@5
|
181 def _add_regular_edges_odd(self):
|
|
bgneal@5
|
182 """Adds an extra edge across the graph to finish off a regular graph
|
|
bgneal@5
|
183 with odd degree. The number of vertices must be even.
|
|
bgneal@5
|
184
|
|
bgneal@5
|
185 """
|
|
bgneal@5
|
186 vs = self.vertices()
|
|
bgneal@5
|
187 vs2 = vs * 2
|
|
bgneal@5
|
188 n = len(vs)
|
|
bgneal@5
|
189
|
|
bgneal@5
|
190 for i in range(n / 2):
|
|
bgneal@5
|
191 v = vs2[i]
|
|
bgneal@5
|
192 w = vs2[i + n / 2]
|
|
bgneal@5
|
193 self.add_edge(Edge(v, w))
|
|
bgneal@5
|
194
|
|
bgneal@7
|
195 def bfs(self, start, visit_func=None):
|
|
bgneal@7
|
196 """Perform a breadth first search starting at node start.
|
|
bgneal@7
|
197
|
|
bgneal@7
|
198 The function visit_func, if supplied, is invoked on each node.
|
|
bgneal@7
|
199
|
|
bgneal@7
|
200 """
|
|
bgneal@7
|
201 # Mark all vertices as unvisited
|
|
bgneal@7
|
202 vs = self.vertices()
|
|
bgneal@7
|
203 for v in vs:
|
|
bgneal@7
|
204 v.visited = False
|
|
bgneal@7
|
205
|
|
bgneal@7
|
206 # Create a work queue consisting initially of the starting node
|
|
bgneal@7
|
207 queue = [start]
|
|
bgneal@7
|
208
|
|
bgneal@7
|
209 while queue:
|
|
bgneal@7
|
210 # retrieve first item from the queue
|
|
bgneal@7
|
211 v = queue.pop(0)
|
|
bgneal@7
|
212
|
|
bgneal@7
|
213 if v.visited:
|
|
bgneal@7
|
214 continue # Skip this one if we've seen it before
|
|
bgneal@7
|
215
|
|
bgneal@7
|
216 # Mark it as visited and invoke user's function on it
|
|
bgneal@7
|
217 v.visited = True
|
|
bgneal@7
|
218 if visit_func:
|
|
bgneal@7
|
219 visit_func(v)
|
|
bgneal@7
|
220
|
|
bgneal@7
|
221 # Add the adjacent neigbors to the node to the queue
|
|
bgneal@7
|
222 queue.extend(self.out_vertices(v))
|
|
bgneal@7
|
223
|
|
bgneal@7
|
224 def is_connected(self):
|
|
bgneal@7
|
225 """Returns True if the graph is connected (there is a path from every
|
|
bgneal@7
|
226 node to every other node) and False otherwise.
|
|
bgneal@7
|
227
|
|
bgneal@7
|
228 """
|
|
bgneal@7
|
229 vs = self.vertices()
|
|
bgneal@7
|
230 if len(vs):
|
|
bgneal@7
|
231 self.bfs(vs[0])
|
|
bgneal@7
|
232 # See if all nodes have been visited
|
|
bgneal@7
|
233 for v in vs:
|
|
bgneal@7
|
234 if not v.visited:
|
|
bgneal@7
|
235 return False
|
|
bgneal@7
|
236 return True
|
|
bgneal@7
|
237
|
|
bgneal@7
|
238 return False # Graph is empty
|
|
bgneal@7
|
239
|
|
bgneal@1
|
240
|
|
bgneal@1
|
241 def main(script, *args):
|
|
bgneal@1
|
242 import pprint
|
|
bgneal@1
|
243
|
|
bgneal@1
|
244 v = Vertex('v')
|
|
bgneal@1
|
245 print v
|
|
bgneal@1
|
246 w = Vertex('w')
|
|
bgneal@1
|
247 print w
|
|
bgneal@1
|
248 e = Edge(v, w)
|
|
bgneal@1
|
249 print e
|
|
bgneal@1
|
250 g = Graph([v,w], [e])
|
|
bgneal@1
|
251 pprint.pprint(g)
|
|
bgneal@1
|
252
|
|
bgneal@1
|
253 print "g.get_edge(v, w): ", g.get_edge(v, w)
|
|
bgneal@1
|
254 x = Vertex('x')
|
|
bgneal@1
|
255 print "g.get_edge(v, x): ", g.get_edge(v, x)
|
|
bgneal@1
|
256
|
|
bgneal@1
|
257 g.remove_edge(e)
|
|
bgneal@1
|
258 pprint.pprint(g)
|
|
bgneal@1
|
259
|
|
bgneal@1
|
260 print "vertices: ", g.vertices()
|
|
bgneal@1
|
261 print "edges: ", g.edges()
|
|
bgneal@1
|
262
|
|
bgneal@1
|
263 g.add_edge(e)
|
|
bgneal@1
|
264 u = Vertex('u')
|
|
bgneal@1
|
265 e1 = Edge(u, v)
|
|
bgneal@1
|
266 e2 = Edge(u, w)
|
|
bgneal@1
|
267 g.add_vertex(u)
|
|
bgneal@1
|
268 g.add_edge(e1)
|
|
bgneal@1
|
269 g.add_edge(e2)
|
|
bgneal@1
|
270 print "Adding vertex u and edges:"
|
|
bgneal@1
|
271 pprint.pprint(g)
|
|
bgneal@1
|
272 print "vertices: ", g.vertices()
|
|
bgneal@1
|
273 print "edges: ", g.edges()
|
|
bgneal@1
|
274
|
|
bgneal@1
|
275 print "Out vertices for v: ", g.out_vertices(v)
|
|
bgneal@1
|
276 print "Out edges for v: ", g.out_edges(v)
|
|
bgneal@1
|
277
|
|
bgneal@1
|
278 x = Vertex('x')
|
|
bgneal@1
|
279 g.add_vertex(x)
|
|
bgneal@1
|
280 g.add_all_edges()
|
|
bgneal@1
|
281 pprint.pprint(g)
|
|
bgneal@1
|
282
|
|
bgneal@7
|
283 print "g is connected?", g.is_connected()
|
|
bgneal@7
|
284 edges = g.out_edges(v)
|
|
bgneal@7
|
285 for e in edges:
|
|
bgneal@7
|
286 g.remove_edge(e)
|
|
bgneal@7
|
287 pprint.pprint(g)
|
|
bgneal@7
|
288 print "g is connected?", g.is_connected()
|
|
bgneal@7
|
289
|
|
bgneal@7
|
290 # Isolate v and check is_connected() again
|
|
bgneal@7
|
291
|
|
bgneal@1
|
292
|
|
bgneal@1
|
293 if __name__ == '__main__':
|
|
bgneal@1
|
294 import sys
|
|
bgneal@1
|
295 main(*sys.argv)
|
