Mercurial > public > think_complexity

comparison Graph.py @ 6:950a34c7e26b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update for section 2.2, exercise 4, random graphs.
author Brian Neal <bgneal@gmail.com>
date Sat, 01 Dec 2012 18:17:58 -0600
parents 8e44660965ef
children 69e5977417b3
comparison
equal deleted inserted replaced
5:8e44660965ef 6:950a34c7e26b
53 The inner dictionary maps from other vertices to edges. 53 The inner dictionary maps from other vertices to edges.
54 54
55 For vertices a and b, graph[a][b] maps 55 For vertices a and b, graph[a][b] maps
56 to the edge that connects a->b, if it exists.""" 56 to the edge that connects a->b, if it exists."""
57 57
58 def __init__(self, vs=[], es=[]): 58 def __init__(self, vs=None, es=None):
59 """Creates a new graph. 59 """Creates a new graph.
60 vs: list of vertices; 60 vs: list of vertices;
61 es: list of edges. 61 es: list of edges.
62 """ 62 """
63 for v in vs: 63 if vs:
64 self.add_vertex(v) 64 for v in vs:
65 65 self.add_vertex(v)
66 for e in es: 66
67 self.add_edge(e) 67 if es:
68 for e in es:
69 self.add_edge(e)
68 70
69 def add_vertex(self, v): 71 def add_vertex(self, v):
70 """Add a vertex to the graph.""" 72 """Add a vertex to the graph."""
71 self[v] = {} 73 self[v] = {}
72 74
135 # Clear all edges first 137 # Clear all edges first
136 self.remove_all_edges() 138 self.remove_all_edges()
137 139
138 # For each combination of 2 vertices, create an edge between them: 140 # For each combination of 2 vertices, create an edge between them:
139 for v, w in itertools.combinations(self.iterkeys(), 2): 141 for v, w in itertools.combinations(self.iterkeys(), 2):
140 e = Edge(v, w) 142 self.add_edge(Edge(v, w))
141 self[v][w] = e
142 self[w][v] = e
143 143
144 def add_regular_edges(self, k): 144 def add_regular_edges(self, k):
145 """Makes the graph regular by making every vertex have k edges. 145 """Makes the graph regular by making every vertex have k edges.
146 146
147 It is not always possible to create a regular graph with a given degree. 147 It is not always possible to create a regular graph with a given degree.