Mercurial > public > think_complexity

annotate 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
rev   line source
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@1 58 def __init__(self, vs=[], es=[]):
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@1 63 for v in vs:
bgneal@1 64 self.add_vertex(v)
bgneal@1 65
bgneal@1 66 for e in es:
bgneal@1 67 self.add_edge(e)
bgneal@1 68
bgneal@1 69 def add_vertex(self, v):
bgneal@1 70 """Add a vertex to the graph."""
bgneal@1 71 self[v] = {}
bgneal@1 72
bgneal@1 73 def add_edge(self, e):
bgneal@1 74 """Adds and edge to the graph by adding an entry in both directions.
bgneal@1 75
bgneal@1 76 If there is already an edge connecting these Vertices, the
bgneal@1 77 new edge replaces it.
bgneal@1 78 """
bgneal@1 79 v, w = e
bgneal@1 80 self[v][w] = e
bgneal@1 81 self[w][v] = e
bgneal@1 82
bgneal@1 83 def get_edge(self, v, w):
bgneal@1 84 """Returns the edge object that exists between the two vertices v & w,
bgneal@1 85 or None if no such edge exists.
bgneal@1 86
bgneal@1 87 """
bgneal@1 88 try:
bgneal@1 89 return self[v][w]
bgneal@1 90 except KeyError:
bgneal@1 91 return None
bgneal@1 92
bgneal@1 93 def remove_edge(self, e):
bgneal@1 94 """Removes the edge e from the graph."""
bgneal@1 95
bgneal@4 96 v, w = e
bgneal@4 97 del self[v][w]
bgneal@4 98 del self[w][v]
bgneal@1 99
bgneal@1 100 def vertices(self):
bgneal@1 101 """Returns a list of the vertices in the graph."""
bgneal@1 102
bgneal@1 103 return self.keys()
bgneal@1 104
bgneal@1 105 def edges(self):
bgneal@1 106 """"Returns a list of the edges in the graph."""
bgneal@1 107
bgneal@1 108 edge_set = set()
bgneal@4 109 for d in self.itervalues():
bgneal@4 110 edge_set.update(d.itervalues())
bgneal@1 111
bgneal@1 112 return list(edge_set)
bgneal@1 113
bgneal@1 114 def out_vertices(self, v):
bgneal@1 115 """Returns a list of vertices that are adjacent to the given vertex v.
bgneal@1 116
bgneal@1 117 """
bgneal@1 118 return self[v].keys()
bgneal@1 119
bgneal@1 120 def out_edges(self, v):
bgneal@1 121 """Returns a list of edges connected to a given vertex v."""
bgneal@1 122
bgneal@1 123 return self[v].values()
bgneal@1 124
bgneal@5 125 def remove_all_edges(self):
bgneal@5 126 """Removes all edges in the graph."""
bgneal@5 127 for v in self.iterkeys():
bgneal@5 128 self[v] = {}
bgneal@5 129
bgneal@1 130 def add_all_edges(self):
bgneal@1 131 """Makes the graph complete by adding edges between all pairs of
bgneal@1 132 vertices.
bgneal@1 133
bgneal@1 134 """
bgneal@1 135 # Clear all edges first
bgneal@5 136 self.remove_all_edges()
bgneal@1 137
bgneal@5 138 # For each combination of 2 vertices, create an edge between them:
bgneal@1 139 for v, w in itertools.combinations(self.iterkeys(), 2):
bgneal@1 140 e = Edge(v, w)
bgneal@1 141 self[v][w] = e
bgneal@1 142 self[w][v] = e
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@1 195
bgneal@1 196 def main(script, *args):
bgneal@1 197 import pprint
bgneal@1 198
bgneal@1 199 v = Vertex('v')
bgneal@1 200 print v
bgneal@1 201 w = Vertex('w')
bgneal@1 202 print w
bgneal@1 203 e = Edge(v, w)
bgneal@1 204 print e
bgneal@1 205 g = Graph([v,w], [e])
bgneal@1 206 pprint.pprint(g)
bgneal@1 207
bgneal@1 208 print "g.get_edge(v, w): ", g.get_edge(v, w)
bgneal@1 209 x = Vertex('x')
bgneal@1 210 print "g.get_edge(v, x): ", g.get_edge(v, x)
bgneal@1 211
bgneal@1 212 g.remove_edge(e)
bgneal@1 213 pprint.pprint(g)
bgneal@1 214
bgneal@1 215 print "vertices: ", g.vertices()
bgneal@1 216 print "edges: ", g.edges()
bgneal@1 217
bgneal@1 218 g.add_edge(e)
bgneal@1 219 u = Vertex('u')
bgneal@1 220 e1 = Edge(u, v)
bgneal@1 221 e2 = Edge(u, w)
bgneal@1 222 g.add_vertex(u)
bgneal@1 223 g.add_edge(e1)
bgneal@1 224 g.add_edge(e2)
bgneal@1 225 print "Adding vertex u and edges:"
bgneal@1 226 pprint.pprint(g)
bgneal@1 227 print "vertices: ", g.vertices()
bgneal@1 228 print "edges: ", g.edges()
bgneal@1 229
bgneal@1 230 print "Out vertices for v: ", g.out_vertices(v)
bgneal@1 231 print "Out edges for v: ", g.out_edges(v)
bgneal@1 232
bgneal@1 233 x = Vertex('x')
bgneal@1 234 g.add_vertex(x)
bgneal@1 235 g.add_all_edges()
bgneal@1 236 pprint.pprint(g)
bgneal@1 237
bgneal@1 238
bgneal@1 239 if __name__ == '__main__':
bgneal@1 240 import sys
bgneal@1 241 main(*sys.argv)