Mercurial > public > think_complexity

annotate ch2ex6.py @ 27:78116556b491

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