Mercurial > public > think_complexity
annotate ch2ex6.py @ 17:977628018b4b
The insert operation on the red-black tree seems to be working.
| author | Brian Neal <bgneal@gmail.com> |
|---|---|
| date | Wed, 19 Dec 2012 22:29:09 -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) |