| 377 |
ira |
1 |
#!/usr/bin/env python
|
|
|
2 |
|
|
|
3 |
import Graph
|
|
|
4 |
import yapgvb
|
|
|
5 |
|
|
|
6 |
class Key (object):
|
|
|
7 |
"""A class that makes a unique key for each pair of vertices."""
|
|
|
8 |
|
|
|
9 |
def __init__ (self, v1, v2):
|
|
|
10 |
self.__key = [v1, v2]
|
|
|
11 |
self.__key.sort ()
|
|
|
12 |
|
|
|
13 |
def __eq__ (self, rhs):
|
|
|
14 |
return (self.__key[0] == rhs.__key[0]) and (self.__key[1] == rhs.__key[1])
|
|
|
15 |
|
|
|
16 |
|
|
|
17 |
class DrawGraph (object):
|
|
|
18 |
"""A class that will draw an unweighted, undirected graph given the vertices and
|
|
|
19 |
edges in the same form that is used for the Graph class."""
|
|
|
20 |
|
|
|
21 |
def __init__ (self, name, vertices, edges):
|
|
|
22 |
"""Constructor"""
|
|
|
23 |
self.__name = str(name)
|
|
|
24 |
self.__vertices = vertices
|
|
|
25 |
self.__edges = edges
|
|
|
26 |
|
|
|
27 |
def render_graph (self, filename):
|
|
|
28 |
"""Draw the graph given into the file given. Please end the
|
|
|
29 |
filename in .svg."""
|
|
|
30 |
dg = yapgvb.Graph (self.__name)
|
|
|
31 |
g = Graph.Graph (self.__vertices, self.__edges)
|
|
|
32 |
|
|
|
33 |
visited = []
|
|
|
34 |
|
|
|
35 |
for v in g.vertices:
|
|
|
36 |
node = dg.add_node (str(v), label=str(v),
|
|
|
37 |
shape=yapgvb.shapes.circle, fontsize=14)
|
|
|
38 |
|
|
|
39 |
for c in g.get_children (v):
|
|
|
40 |
k = Key (v, c)
|
|
|
41 |
|
|
|
42 |
if k not in visited:
|
|
|
43 |
node_c = dg.add_node (str(c), label=str(c),
|
|
|
44 |
shape=yapgvb.shapes.circle,
|
|
|
45 |
fontsize=14)
|
|
|
46 |
node >> node_c
|
|
|
47 |
visited.append (k)
|
|
|
48 |
|
|
|
49 |
# Do the rendering
|
|
|
50 |
dg.layout (yapgvb.engines.neato)
|
|
|
51 |
dg.render (filename)
|
|
|
52 |
|
|
|
53 |
|
|
|
54 |
def main ():
|
|
|
55 |
|
|
|
56 |
vertices = ['a', 'b', 'c', 'd', 'e']
|
|
|
57 |
edges = ( ['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'a'], ['b', 'c'],
|
|
|
58 |
['b', 'e'], ['e', 'b'], ['e', 'c'], ['e', 'd'],
|
|
|
59 |
['d', 'a'], ['d', 'c'], ['d', 'e'], ['c', 'a'],
|
|
|
60 |
['c', 'b'], ['c', 'd'], ['c', 'e'] )
|
|
|
61 |
|
|
|
62 |
print 'Drawing graph g1.svg'
|
|
|
63 |
DrawGraph ('g1', vertices, edges).render_graph ('g1.svg')
|
|
|
64 |
|
|
|
65 |
vertices = range (11)
|
|
|
66 |
edges = ( [0, 1], [0, 9], [0, 8], [8, 10], [8, 7], [9, 6], [9, 5],
|
|
|
67 |
[6, 7], [1, 4], [1, 3], [1, 2], [2, 0] )
|
|
|
68 |
|
|
|
69 |
print 'Drawing graph g2.svg'
|
|
|
70 |
DrawGraph ('g2', vertices, edges).render_graph ('g2.svg')
|
|
|
71 |
|
|
|
72 |
vertices = range (3)
|
|
|
73 |
edges = ( [0, 1], [1, 2], [2, 0] )
|
|
|
74 |
|
|
|
75 |
print 'Drawing graph g3.svg'
|
|
|
76 |
DrawGraph ('g3', vertices, edges).render_graph ('g3.svg')
|
|
|
77 |
|
|
|
78 |
|
|
|
79 |
if __name__ == '__main__':
|
|
|
80 |
main ()
|
|
|
81 |
|