Mercurial > public > think_complexity
comparison GraphCode.py @ 0:04e3a6590139
Adding GraphCode.py as obtained from the website.
| author | Brian Neal <bgneal@gmail.com> |
|---|---|
| date | Thu, 29 Nov 2012 19:06:55 -0600 |
| parents | |
| children |
comparison
equal
deleted
inserted
replaced
| -1:000000000000 | 0:04e3a6590139 |
|---|---|
| 1 """ Code example from Complexity and Computation, a book about | |
| 2 exploring complexity science with Python. Available free from | |
| 3 | |
| 4 http://greenteapress.com/complexity | |
| 5 | |
| 6 Copyright 2011 Allen B. Downey. | |
| 7 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html. | |
| 8 """ | |
| 9 | |
| 10 class Vertex(object): | |
| 11 """A Vertex is a node in a graph.""" | |
| 12 | |
| 13 def __init__(self, label=''): | |
| 14 self.label = label | |
| 15 | |
| 16 def __repr__(self): | |
| 17 """Returns a string representation of this object that can | |
| 18 be evaluated as a Python expression.""" | |
| 19 return 'Vertex(%s)' % repr(self.label) | |
| 20 | |
| 21 __str__ = __repr__ | |
| 22 """The str and repr forms of this object are the same.""" | |
| 23 | |
| 24 | |
| 25 class Edge(tuple): | |
| 26 """An Edge is a list of two vertices.""" | |
| 27 | |
| 28 def __new__(cls, *vs): | |
| 29 """The Edge constructor takes two vertices.""" | |
| 30 if len(vs) != 2: | |
| 31 raise ValueError, 'Edges must connect exactly two vertices.' | |
| 32 return tuple.__new__(cls, vs) | |
| 33 | |
| 34 def __repr__(self): | |
| 35 """Return a string representation of this object that can | |
| 36 be evaluated as a Python expression.""" | |
| 37 return 'Edge(%s, %s)' % (repr(self[0]), repr(self[1])) | |
| 38 | |
| 39 __str__ = __repr__ | |
| 40 """The str and repr forms of this object are the same.""" | |
| 41 | |
| 42 | |
| 43 class Graph(dict): | |
| 44 """A Graph is a dictionary of dictionaries. The outer | |
| 45 dictionary maps from a vertex to an inner dictionary. | |
| 46 The inner dictionary maps from other vertices to edges. | |
| 47 | |
| 48 For vertices a and b, graph[a][b] maps | |
| 49 to the edge that connects a->b, if it exists.""" | |
| 50 | |
| 51 def __init__(self, vs=[], es=[]): | |
| 52 """Creates a new graph. | |
| 53 vs: list of vertices; | |
| 54 es: list of edges. | |
| 55 """ | |
| 56 for v in vs: | |
| 57 self.add_vertex(v) | |
| 58 | |
| 59 for e in es: | |
| 60 self.add_edge(e) | |
| 61 | |
| 62 def add_vertex(self, v): | |
| 63 """Add a vertex to the graph.""" | |
| 64 self[v] = {} | |
| 65 | |
| 66 def add_edge(self, e): | |
| 67 """Adds and edge to the graph by adding an entry in both directions. | |
| 68 | |
| 69 If there is already an edge connecting these Vertices, the | |
| 70 new edge replaces it. | |
| 71 """ | |
| 72 v, w = e | |
| 73 self[v][w] = e | |
| 74 self[w][v] = e | |
| 75 | |
| 76 | |
| 77 def main(script, *args): | |
| 78 v = Vertex('v') | |
| 79 print v | |
| 80 w = Vertex('w') | |
| 81 print w | |
| 82 e = Edge(v, w) | |
| 83 print e | |
| 84 g = Graph([v,w], [e]) | |
| 85 print g | |
| 86 | |
| 87 | |
| 88 if __name__ == '__main__': | |
| 89 import sys | |
| 90 main(*sys.argv) |