annotate RandomGraph.py @ 7:69e5977417b3
Section 2.4, exercise 5, create an is_connected() method for the Graph.
Also implement breadth-first search.
| author |
Brian Neal <bgneal@gmail.com> |
| date |
Sun, 02 Dec 2012 21:51:51 -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
|
