Mercurial > public > think_complexity

comparison ch2ex6.py @ 9:9f1fccc13991

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added a program that does 2.3 exercise 6 (Paul Erdos).
author Brian Neal <bgneal@gmail.com>
date Mon, 03 Dec 2012 19:40:26 -0600
parents
children
comparison
equal deleted inserted replaced
8:1defe6fcf9d3 9:9f1fccc13991
1 """ch2ex6.py - Program for Chapter 2.5, exercise 6.
2
3 This program generates random graphs with parameters n and p and computes the
4 fraction of them that are connected.
5
6 """
7 import string
8
9 from Graph import Vertex
10 from RandomGraph import RandomGraph
11
12
13 LABELS = string.letters + string.punctuation
14
15 def test_graph(n, p):
16 """Generate a RandomGraph with parameters n & p and return True if the
17 graph is connected, False otherwise.
18
19 """
20 vs = [Vertex(c) for c in LABELS[:n]]
21 g = RandomGraph(vs)
22 g.add_random_edges(p)
23 return g.is_connected()
24
25
26 def test_p(n, p, num):
27 """Generate num RandomGraphs with parameters n & p and return the number
28 of graphs that are connected.
29
30 """
31 count = 0
32 for i in range(num):
33 if test_graph(n, p):
34 count += 1
35
36 return count
37
38
39 def main(script_name, n=26, p=0.1, num=1, *args):
40 """Generate num RandomGraphs with parameters n & p and print out the number
41 of graphs that are connected.
42
43 """
44
45 n = int(n)
46 p = float(p)
47 num = int(num)
48
49 count = test_p(n, p, num)
50 print count
51
52
53 if __name__ == '__main__':
54 import sys
55 main(*sys.argv)