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 __docformat__ = "restructuredtext en"
24
25 __metaclass__ = type
26
27 import os.path as osp
28 import os
29 import sys
30 import tempfile
31 import codecs
32 import errno
33
35 """Make <value> usable in a dot file."""
36 lines = [line.replace('"', '\\"') for line in value.split('\n')]
37 data = '\\l'.join(lines)
38 return '\\n' + data
39
41 """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png')."""
42 basename = osp.basename(filename)
43 storedir = osp.dirname(osp.abspath(filename))
44 target = filename.split('.')[-1]
45 return storedir, basename, target
46
47
49 """Dot File backend."""
50 - def __init__(self, graphname, rankdir=None, size=None, ratio=None,
51 charset='utf-8', renderer='dot', additionnal_param={}):
52 self.graphname = graphname
53 self.renderer = renderer
54 self.lines = []
55 self._source = None
56 self.emit("digraph %s {" % normalize_node_id(graphname))
57 if rankdir:
58 self.emit('rankdir=%s' % rankdir)
59 if ratio:
60 self.emit('ratio=%s' % ratio)
61 if size:
62 self.emit('size="%s"' % size)
63 if charset:
64 assert charset.lower() in ('utf-8', 'iso-8859-1', 'latin1'), \
65 'unsupported charset %s' % charset
66 self.emit('charset="%s"' % charset)
67 for param in sorted(additionnal_param.items()):
68 self.emit('='.join(param))
69
71 """returns self._source"""
72 if self._source is None:
73 self.emit("}\n")
74 self._source = '\n'.join(self.lines)
75 del self.lines
76 return self._source
77
78 source = property(get_source)
79
80 - def generate(self, outputfile=None, dotfile=None, mapfile=None):
81 """Generates a graph file.
82
83 :param outputfile: filename and path [defaults to graphname.png]
84 :param dotfile: filename and path [defaults to graphname.dot]
85
86 :rtype: str
87 :return: a path to the generated file
88 """
89 import subprocess
90 name = self.graphname
91 if not dotfile:
92
93 if outputfile and outputfile.endswith(".dot"):
94 dotfile = outputfile
95 else:
96 dotfile = '%s.dot' % name
97 if outputfile is not None:
98 storedir, basename, target = target_info_from_filename(outputfile)
99 if target != "dot":
100 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
101 os.close(pdot)
102 else:
103 dot_sourcepath = osp.join(storedir, dotfile)
104 else:
105 target = 'png'
106 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
107 ppng, outputfile = tempfile.mkstemp(".png", name)
108 os.close(pdot)
109 os.close(ppng)
110 pdot = codecs.open(dot_sourcepath, 'w', encoding='utf8')
111 pdot.write(self.source)
112 pdot.close()
113 if target != 'dot':
114 if sys.platform == 'win32':
115 use_shell = True
116 else:
117 use_shell = False
118 try:
119 if mapfile:
120 subprocess.call([self.renderer, '-Tcmapx', '-o', mapfile, '-T', target, dot_sourcepath, '-o', outputfile],
121 shell=use_shell)
122 else:
123 subprocess.call([self.renderer, '-T', target,
124 dot_sourcepath, '-o', outputfile],
125 shell=use_shell)
126 except OSError as e:
127 if e.errno == errno.ENOENT:
128 e.strerror = 'File not found: {0}'.format(self.renderer)
129 raise
130 os.unlink(dot_sourcepath)
131 return outputfile
132
133 - def emit(self, line):
134 """Adds <line> to final output."""
135 self.lines.append(line)
136
138 """emit an edge from <name1> to <name2>.
139 edge properties: see http://www.graphviz.org/doc/info/attrs.html
140 """
141 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
142 n_from, n_to = normalize_node_id(name1), normalize_node_id(name2)
143 self.emit('%s -> %s [%s];' % (n_from, n_to, ', '.join(sorted(attrs))) )
144
146 """emit a node with given properties.
147 node properties: see http://www.graphviz.org/doc/info/attrs.html
148 """
149 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
150 self.emit('%s [%s];' % (normalize_node_id(name), ', '.join(sorted(attrs))))
151
153 """Returns a suitable DOT node id for `nid`."""
154 return '"%s"' % nid
155
158
159 self.backend = backend
160
161
162 - def generate(self, visitor, propshdlr, outputfile=None, mapfile=None):
163
164
165
166 self.propshdlr = propshdlr
167 for nodeid, node in visitor.nodes():
168 props = propshdlr.node_properties(node)
169 self.backend.emit_node(nodeid, **props)
170 for subjnode, objnode, edge in visitor.edges():
171 props = propshdlr.edge_properties(edge, subjnode, objnode)
172 self.backend.emit_edge(subjnode, objnode, **props)
173 return self.backend.generate(outputfile=outputfile, mapfile=mapfile)
174
175
178
180 """takes a dependency graph dict as arguments and return an ordered tuple of
181 nodes starting with nodes without dependencies and up to the outermost node.
182
183 If there is some cycle in the graph, :exc:`UnorderableGraph` will be raised.
184
185 Also the given graph dict will be emptied.
186 """
187
188 cycles = get_cycles(graph)
189 if cycles:
190 cycles = '\n'.join([' -> '.join(cycle) for cycle in cycles])
191 raise UnorderableGraph('cycles in graph: %s' % cycles)
192 vertices = set(graph)
193 to_vertices = set()
194 for edges in graph.values():
195 to_vertices |= set(edges)
196 missing_vertices = to_vertices - vertices
197 if missing_vertices:
198 raise UnorderableGraph('missing vertices: %s' % ', '.join(missing_vertices))
199
200 order = []
201 order_set = set()
202 old_len = None
203 while graph:
204 if old_len == len(graph):
205 raise UnorderableGraph('unknown problem with %s' % graph)
206 old_len = len(graph)
207 deps_ok = []
208 for node, node_deps in graph.items():
209 for dep in node_deps:
210 if dep not in order_set:
211 break
212 else:
213 deps_ok.append(node)
214 order.append(deps_ok)
215 order_set |= set(deps_ok)
216 for node in deps_ok:
217 del graph[node]
218 result = []
219 for grp in reversed(order):
220 result.extend(sorted(grp))
221 return tuple(result)
222
223
225 '''given a dictionary representing an ordered graph (i.e. key are vertices
226 and values is a list of destination vertices representing edges), return a
227 list of detected cycles
228 '''
229 if not graph_dict:
230 return ()
231 result = []
232 if vertices is None:
233 vertices = graph_dict.keys()
234 for vertice in vertices:
235 _get_cycles(graph_dict, [], set(), result, vertice)
236 return result
237
238 -def _get_cycles(graph_dict, path, visited, result, vertice):
239 """recursive function doing the real work for get_cycles"""
240 if vertice in path:
241 cycle = [vertice]
242 for node in path[::-1]:
243 if node == vertice:
244 break
245 cycle.insert(0, node)
246
247 start_from = min(cycle)
248 index = cycle.index(start_from)
249 cycle = cycle[index:] + cycle[0:index]
250
251 if not cycle in result:
252 result.append(cycle)
253 return
254 path.append(vertice)
255 try:
256 for node in graph_dict[vertice]:
257
258 if node not in visited:
259 _get_cycles(graph_dict, path, visited, result, node)
260 visited.add(node)
261 except KeyError:
262 pass
263 path.pop()
264
265 -def has_path(graph_dict, fromnode, tonode, path=None):
266 """generic function taking a simple graph definition as a dictionary, with
267 node has key associated to a list of nodes directly reachable from it.
268
269 Return None if no path exists to go from `fromnode` to `tonode`, else the
270 first path found (as a list including the destination node at last)
271 """
272 if path is None:
273 path = []
274 elif fromnode in path:
275 return None
276 path.append(fromnode)
277 for destnode in graph_dict[fromnode]:
278 if destnode == tonode or has_path(graph_dict, destnode, tonode, path):
279 return path[1:] + [tonode]
280 path.pop()
281 return None
282