A stab at the L(p)/L(0) plot.
I still don't quite get how the graphs in the Watts and Strogatz paper were
generated. My results have basically the same shape, but don't converge to 0.
I'm not sure how this is possible if the rewire function does not remove edges.
| author |
Brian Neal <bgneal@gmail.com> |
| date |
Thu, 03 Jan 2013 18:41:13 -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)
|
