Mercurial > public > think_complexity
annotate RandomGraph.py @ 9:9f1fccc13991
Added a program that does 2.3 exercise 6 (Paul Erdos).
author | Brian Neal <bgneal@gmail.com> |
---|---|
date | Mon, 03 Dec 2012 19:40:26 -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 |