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