Mercurial > public > think_complexity
annotate RandomGraph.py @ 11:0f98bcb5bd3f
Added the bisection() function for Ch 3.3 exercise 3.
| author | Brian Neal <bgneal@gmail.com> |
|---|---|
| date | Mon, 10 Dec 2012 19:25:20 -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 |