bgneal@9: """ch2ex6.py - Program for Chapter 2.5, exercise 6.
bgneal@9: 
bgneal@9: This program generates random graphs with parameters n and p and computes the
bgneal@9: fraction of them that are connected.
bgneal@9: 
bgneal@9: """
bgneal@9: import string
bgneal@9: 
bgneal@9: from Graph import Vertex
bgneal@9: from RandomGraph import RandomGraph
bgneal@9: 
bgneal@9: 
bgneal@9: LABELS = string.letters + string.punctuation
bgneal@9: 
bgneal@9: def test_graph(n, p):
bgneal@9:     """Generate a RandomGraph with parameters n & p and return True if the
bgneal@9:     graph is connected, False otherwise.
bgneal@9: 
bgneal@9:     """
bgneal@9:     vs = [Vertex(c) for c in LABELS[:n]]
bgneal@9:     g = RandomGraph(vs)
bgneal@9:     g.add_random_edges(p)
bgneal@9:     return g.is_connected()
bgneal@9: 
bgneal@9: 
bgneal@9: def test_p(n, p, num):
bgneal@9:     """Generate num RandomGraphs with parameters n & p and return the number
bgneal@9:     of graphs that are connected.
bgneal@9: 
bgneal@9:     """
bgneal@9:     count = 0
bgneal@9:     for i in range(num):
bgneal@9:         if test_graph(n, p):
bgneal@9:             count += 1
bgneal@9: 
bgneal@9:     return count
bgneal@9: 
bgneal@9: 
bgneal@9: def main(script_name, n=26, p=0.1, num=1, *args):
bgneal@9:     """Generate num RandomGraphs with parameters n & p and print out the number
bgneal@9:     of graphs that are connected.
bgneal@9: 
bgneal@9:     """
bgneal@9: 
bgneal@9:     n = int(n)
bgneal@9:     p = float(p)
bgneal@9:     num = int(num)
bgneal@9: 
bgneal@9:     count = test_p(n, p, num)
bgneal@9:     print count
bgneal@9: 
bgneal@9: 
bgneal@9: if __name__ == '__main__':
bgneal@9:     import sys
bgneal@9:     main(*sys.argv)