Mercurial > public > think_complexity

comparison RandomGraph.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
children
comparison
equal deleted inserted replaced
5:8e44660965ef 6:950a34c7e26b
1 """This module contains the RandomGraph class.
2
3 """
4 import random
5 import itertools
6
7 from Graph import Graph, Edge
8
9
10 class RandomGraph(Graph):
11 """A RandomGraph is a Graph that adds a method to generate random edges."""
12
13 def add_random_edges(self, p=0.5):
14 """This method first removes all edges, then adds edges at random such
15 that the probability is p that there is an edge between any two nodes.
16
17 p must be a float between 0 and 1, inclusive.
18
19 """
20 self.remove_all_edges()
21
22 # For each combination of 2 vertices, create an edge between them if we
23 # select a random number [0.0, 1.0) that is less than p.
24 for v, w in itertools.combinations(self.iterkeys(), 2):
25 if random.random() <= p:
26 self.add_edge(Edge(v, w))
27
28
29 if __name__ == '__main__':
30 import string
31 import sys
32 from Graph import Vertex
33 from GraphWorld import GraphWorld, CircleLayout
34
35 def main(script_name, n=10, p=0.5):
36
37 n = int(n)
38 p = float(p)
39
40 labels = string.ascii_lowercase + string.ascii_uppercase
41 vs = [Vertex(c) for c in labels[:n]]
42
43 g = RandomGraph(vs)
44 g.add_random_edges(p)
45 layout = CircleLayout(g)
46
47 gw = GraphWorld()
48 gw.show_graph(g, layout)
49 gw.mainloop()
50
51 main(*sys.argv)
52