annotate RandomGraph.py @ 24:5c2c4ce095ef
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 |
950a34c7e26b |
| children |
|
| rev |
line source |
|
bgneal@6
|
1 """This module contains the RandomGraph class.
|
|
bgneal@6
|
2
|
|
bgneal@6
|
3 """
|
|
bgneal@6
|
4 import random
|
|
bgneal@6
|
5 import itertools
|
|
bgneal@6
|
6
|
|
bgneal@6
|
7 from Graph import Graph, Edge
|
|
bgneal@6
|
8
|
|
bgneal@6
|
9
|
|
bgneal@6
|
10 class RandomGraph(Graph):
|
|
bgneal@6
|
11 """A RandomGraph is a Graph that adds a method to generate random edges."""
|
|
bgneal@6
|
12
|
|
bgneal@6
|
13 def add_random_edges(self, p=0.5):
|
|
bgneal@6
|
14 """This method first removes all edges, then adds edges at random such
|
|
bgneal@6
|
15 that the probability is p that there is an edge between any two nodes.
|
|
bgneal@6
|
16
|
|
bgneal@6
|
17 p must be a float between 0 and 1, inclusive.
|
|
bgneal@6
|
18
|
|
bgneal@6
|
19 """
|
|
bgneal@6
|
20 self.remove_all_edges()
|
|
bgneal@6
|
21
|
|
bgneal@6
|
22 # For each combination of 2 vertices, create an edge between them if we
|
|
bgneal@6
|
23 # select a random number [0.0, 1.0) that is less than p.
|
|
bgneal@6
|
24 for v, w in itertools.combinations(self.iterkeys(), 2):
|
|
bgneal@6
|
25 if random.random() <= p:
|
|
bgneal@6
|
26 self.add_edge(Edge(v, w))
|
|
bgneal@6
|
27
|
|
bgneal@6
|
28
|
|
bgneal@6
|
29 if __name__ == '__main__':
|
|
bgneal@6
|
30 import string
|
|
bgneal@6
|
31 import sys
|
|
bgneal@6
|
32 from Graph import Vertex
|
|
bgneal@6
|
33 from GraphWorld import GraphWorld, CircleLayout
|
|
bgneal@6
|
34
|
|
bgneal@6
|
35 def main(script_name, n=10, p=0.5):
|
|
bgneal@6
|
36
|
|
bgneal@6
|
37 n = int(n)
|
|
bgneal@6
|
38 p = float(p)
|
|
bgneal@6
|
39
|
|
bgneal@6
|
40 labels = string.ascii_lowercase + string.ascii_uppercase
|
|
bgneal@6
|
41 vs = [Vertex(c) for c in labels[:n]]
|
|
bgneal@6
|
42
|
|
bgneal@6
|
43 g = RandomGraph(vs)
|
|
bgneal@6
|
44 g.add_random_edges(p)
|
|
bgneal@6
|
45 layout = CircleLayout(g)
|
|
bgneal@6
|
46
|
|
bgneal@6
|
47 gw = GraphWorld()
|
|
bgneal@6
|
48 gw.show_graph(g, layout)
|
|
bgneal@6
|
49 gw.mainloop()
|
|
bgneal@6
|
50
|
|
bgneal@6
|
51 main(*sys.argv)
|
|
bgneal@6
|
52
|
