Mercurial > public > think_complexity

comparison Graph.py @ 5:8e44660965ef

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Completed chapter 2, exercise 3 on regular graphs.
author Brian Neal <bgneal@gmail.com>
date Sat, 01 Dec 2012 16:51:39 -0600
parents 9d0cf96b6a3b
children 950a34c7e26b
comparison
equal deleted inserted replaced
4:9d0cf96b6a3b 5:8e44660965ef
5 5
6 Copyright 2011 Allen B. Downey. 6 Copyright 2011 Allen B. Downey.
7 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html. 7 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
8 """ 8 """
9 import itertools 9 import itertools
10
11
12 class GraphError(Exception):
13 """Exception for Graph errors"""
14 pass
10 15
11 16
12 class Vertex(object): 17 class Vertex(object):
13 """A Vertex is a node in a graph.""" 18 """A Vertex is a node in a graph."""
14 19
115 def out_edges(self, v): 120 def out_edges(self, v):
116 """Returns a list of edges connected to a given vertex v.""" 121 """Returns a list of edges connected to a given vertex v."""
117 122
118 return self[v].values() 123 return self[v].values()
119 124
125 def remove_all_edges(self):
126 """Removes all edges in the graph."""
127 for v in self.iterkeys():
128 self[v] = {}
129
120 def add_all_edges(self): 130 def add_all_edges(self):
121 """Makes the graph complete by adding edges between all pairs of 131 """Makes the graph complete by adding edges between all pairs of
122 vertices. 132 vertices.
123 133
124 """ 134 """
125 # Clear all edges first 135 # Clear all edges first
126 for v in self.iterkeys(): 136 self.remove_all_edges()
127 self[v] = {} 137
128 138 # For each combination of 2 vertices, create an edge between them:
129 for v, w in itertools.combinations(self.iterkeys(), 2): 139 for v, w in itertools.combinations(self.iterkeys(), 2):
130 e = Edge(v, w) 140 e = Edge(v, w)
131 self[v][w] = e 141 self[v][w] = e
132 self[w][v] = e 142 self[w][v] = e
143
144 def add_regular_edges(self, k):
145 """Makes the graph regular by making every vertex have k edges.
146
147 It is not always possible to create a regular graph with a given degree.
148 If a graph has n vertices, then a regular graph can be constructed with
149 degree k if n >= k + 1 and n * k is even. If these conditions are not
150 met a GraphError exception is raised.
151
152 """
153 n = len(self.vertices())
154 if n < k + 1:
155 raise GraphError("Can't make a regular graph with degree >= number"
156 " of vertices")
157 if (n * k) % 2 != 0:
158 raise GraphError("Can't make a regular graph of degree k and"
159 " order n where k * n is odd")
160
161 # Remove all edges first
162 self.remove_all_edges()
163
164 if k % 2 != 0: # if k is odd
165 self._add_regular_edges_even(k - 1)
166 self._add_regular_edges_odd()
167 else:
168 self._add_regular_edges_even(k)
169
170 def _add_regular_edges_even(self, k):
171 """Make a regular graph with degree k. k must be even."""
172
173 vs = self.vertices()
174 vs2 = vs * 2
175
176 for i, v in enumerate(vs):
177 for j in range(1, k / 2 + 1):
178 w = vs2[i + j]
179 self.add_edge(Edge(v, w))
180
181 def _add_regular_edges_odd(self):
182 """Adds an extra edge across the graph to finish off a regular graph
183 with odd degree. The number of vertices must be even.
184
185 """
186 vs = self.vertices()
187 vs2 = vs * 2
188 n = len(vs)
189
190 for i in range(n / 2):
191 v = vs2[i]
192 w = vs2[i + n / 2]
193 self.add_edge(Edge(v, w))
133 194
134 195
135 def main(script, *args): 196 def main(script, *args):
136 import pprint 197 import pprint
137 198