1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 """Graph manipulation utilities.
19
20 (dot generation adapted from pypy/translator/tool/make_dot.py)
21
22
23
24
25 """
26 __docformat__ = "restructuredtext en"
27
28 __metaclass__ = type
29
30 import os.path as osp
31 import os
32 import subprocess
33 import sys
34 import tempfile
35
37 """Make <value> usable in a dot file."""
38 lines = [line.replace('"', '\\"') for line in value.split('\n')]
39 data = '\\l'.join(lines)
40 return '\\n' + data
41
43 """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png')."""
44 basename = osp.basename(filename)
45 storedir = osp.dirname(osp.abspath(filename))
46 target = filename.split('.')[-1]
47 return storedir, basename, target
48
49
51 """Dot File backend."""
52 - def __init__(self, graphname, rankdir=None, size=None, ratio=None,
53 charset='utf-8', renderer='dot', additionnal_param={}):
54 self.graphname = graphname
55 self.renderer = renderer
56 self.lines = []
57 self._source = None
58 self.emit("digraph %s {" % normalize_node_id(graphname))
59 if rankdir:
60 self.emit('rankdir=%s' % rankdir)
61 if ratio:
62 self.emit('ratio=%s' % ratio)
63 if size:
64 self.emit('size="%s"' % size)
65 if charset:
66 assert charset.lower() in ('utf-8', 'iso-8859-1', 'latin1'), \
67 'unsupported charset %s' % charset
68 self.emit('charset="%s"' % charset)
69 for param in additionnal_param.iteritems():
70 self.emit('='.join(param))
71
73 """returns self._source"""
74 if self._source is None:
75 self.emit("}\n")
76 self._source = '\n'.join(self.lines)
77 del self.lines
78 return self._source
79
80 source = property(get_source)
81
82 - def generate(self, outputfile=None, dotfile=None, mapfile=None):
83 """Generates a graph file.
84
85 :param outputfile: filename and path [defaults to graphname.png]
86 :param dotfile: filename and path [defaults to graphname.dot]
87
88 :rtype: str
89 :return: a path to the generated file
90 """
91 name = self.graphname
92 if not dotfile:
93
94 if outputfile and outputfile.endswith(".dot"):
95 dotfile = outputfile
96 else:
97 dotfile = '%s.dot' % name
98 if outputfile is not None:
99 storedir, basename, target = target_info_from_filename(outputfile)
100 if target != "dot":
101 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
102 os.close(pdot)
103 else:
104 dot_sourcepath = osp.join(storedir, dotfile)
105 else:
106 target = 'png'
107 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
108 ppng, outputfile = tempfile.mkstemp(".png", name)
109 os.close(pdot)
110 os.close(ppng)
111 pdot = open(dot_sourcepath,'w')
112 if isinstance(self.source, unicode):
113 pdot.write(self.source.encode('UTF8'))
114 else:
115 pdot.write(self.source)
116 pdot.close()
117 if target != 'dot':
118 if mapfile:
119 subprocess.call('%s -Tcmapx -o%s -T%s %s -o%s' % (self.renderer, mapfile,
120 target, dot_sourcepath, outputfile), shell=True)
121 else:
122 subprocess.call('%s -T%s %s -o%s' % (self.renderer, target,
123 dot_sourcepath, outputfile), shell=True)
124 os.unlink(dot_sourcepath)
125 return outputfile
126
127 - def emit(self, line):
128 """Adds <line> to final output."""
129 self.lines.append(line)
130
132 """emit an edge from <name1> to <name2>.
133 edge properties: see http://www.graphviz.org/doc/info/attrs.html
134 """
135 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
136 n_from, n_to = normalize_node_id(name1), normalize_node_id(name2)
137 self.emit('%s -> %s [%s];' % (n_from, n_to, ", ".join(attrs)) )
138
140 """emit a node with given properties.
141 node properties: see http://www.graphviz.org/doc/info/attrs.html
142 """
143 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
144 self.emit('%s [%s];' % (normalize_node_id(name), ", ".join(attrs)))
145
147 """Returns a suitable DOT node id for `nid`."""
148 return '"%s"' % nid
149
152
153 self.backend = backend
154
155 - def generate(self, visitor, propshdlr, outputfile=None, mapfile=None):
156
157
158
159 self.propshdlr = propshdlr
160 for nodeid, node in visitor.nodes():
161 props = propshdlr.node_properties(node)
162 self.backend.emit_node(nodeid, **props)
163 for subjnode, objnode, edge in visitor.edges():
164 props = propshdlr.edge_properties(edge, subjnode, objnode)
165 self.backend.emit_edge(subjnode, objnode, **props)
166 return self.backend.generate(outputfile=outputfile, mapfile=mapfile)
167
168
172
174 return 'cycles in graph: %s' % self.cycles
175
177 """takes a dependency graph dict as arguments and return an ordered tuple of
178 nodes starting with nodes without dependencies and up to the outermost node.
179
180 If there is some cycle in the graph, :exc:`UnorderableGraph` will be raised.
181
182 Also the given graph dict will be emptied.
183 """
184 cycles = get_cycles(graph)
185 if cycles:
186 cycles = '\n'.join(' -> '.join(cycle) for cycle in cycles)
187 raise UnorderableGraph(cycles)
188 ordered = []
189 while graph:
190
191 for node, deps in sorted(graph.items()):
192 if not deps:
193 ordered.append(node)
194 del graph[node]
195 for deps in graph.itervalues():
196 try:
197 deps.remove(node)
198 except KeyError:
199 continue
200 return tuple(reversed(ordered))
201
202
203
205 '''given a dictionary representing an ordered graph (i.e. key are vertices
206 and values is a list of destination vertices representing edges), return a
207 list of detected cycles
208 '''
209 if not graph_dict:
210 return ()
211 result = []
212 if vertices is None:
213 vertices = graph_dict.keys()
214 for vertice in vertices:
215 _get_cycles(graph_dict, vertice, [], result)
216 return result
217
218 -def _get_cycles(graph_dict, vertice=None, path=None, result=None):
219 """recursive function doing the real work for get_cycles"""
220 if vertice in path:
221 cycle = [vertice]
222 for node in path[::-1]:
223 if node == vertice:
224 break
225 cycle.insert(0, node)
226
227 start_from = min(cycle)
228 index = cycle.index(start_from)
229 cycle = cycle[index:] + cycle[0:index]
230
231 if not cycle in result:
232 result.append(cycle)
233 return
234 path.append(vertice)
235 try:
236 for node in graph_dict[vertice]:
237 _get_cycles(graph_dict, node, path, result)
238 except KeyError:
239 pass
240 path.pop()
241
242 -def has_path(graph_dict, fromnode, tonode, path=None):
243 """generic function taking a simple graph definition as a dictionary, with
244 node has key associated to a list of nodes directly reachable from it.
245
246 Return None if no path exists to go from `fromnode` to `tonode`, else the
247 first path found (as a list including the destination node at last)
248 """
249 if path is None:
250 path = []
251 elif fromnode in path:
252 return None
253 path.append(fromnode)
254 for destnode in graph_dict[fromnode]:
255 if destnode == tonode or has_path(graph_dict, destnode, tonode, path):
256 return path[1:] + [tonode]
257 path.pop()
258 return None
259