Chapter 5.5, exercise 6, #3: compute WS clustering coefficient
and characteristic length on a BA model graph.
| author |
Brian Neal <bgneal@gmail.com> |
| date |
Thu, 10 Jan 2013 19:24:02 -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)
|
