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.iteritems():
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 mapfile:
114 print '%s -Tcmapx -o%s -T%s %s -o%s' % (self.renderer, mapfile,
115 target, dot_sourcepath, outputfile)
116 subprocess.call('%s -Tcmapx -o%s -T%s %s -o%s' % (self.renderer, mapfile,
117 target, dot_sourcepath, outputfile), shell=True)
118 else:
119 subprocess.call('%s -T%s %s -o%s' % (self.renderer, target,
120 dot_sourcepath, outputfile), shell=True)
121 os.unlink(dot_sourcepath)
122 return outputfile
123
124 - def emit(self, line):
125 """Adds <line> to final output."""
126 self.lines.append(line)
127
129 """emit an edge from <name1> to <name2>.
130 edge properties: see http://www.graphviz.org/doc/info/attrs.html
131 """
132 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
133 n_from, n_to = normalize_node_id(name1), normalize_node_id(name2)
134 self.emit('%s -> %s [%s];' % (n_from, n_to, ", ".join(attrs)) )
135
137 """emit a node with given properties.
138 node properties: see http://www.graphviz.org/doc/info/attrs.html
139 """
140 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
141 self.emit('%s [%s];' % (normalize_node_id(name), ", ".join(attrs)))
142
144 """Returns a suitable DOT node id for `nid`."""
145 return '"%s"' % nid
146
149
150 self.backend = backend
151
152
153 - def generate(self, visitor, propshdlr, outputfile=None, mapfile=None):
154
155
156
157 self.propshdlr = propshdlr
158 for nodeid, node in visitor.nodes():
159 props = propshdlr.node_properties(node)
160 self.backend.emit_node(nodeid, **props)
161 for subjnode, objnode, edge in visitor.edges():
162 props = propshdlr.edge_properties(edge, subjnode, objnode)
163 self.backend.emit_edge(subjnode, objnode, **props)
164 return self.backend.generate(outputfile=outputfile, mapfile=mapfile)
165
166
169
171 """takes a dependency graph dict as arguments and return an ordered tuple of
172 nodes starting with nodes without dependencies and up to the outermost node.
173
174 If there is some cycle in the graph, :exc:`UnorderableGraph` will be raised.
175
176 Also the given graph dict will be emptied.
177 """
178
179 cycles = get_cycles(graph)
180 if cycles:
181 cycles = '\n'.join([' -> '.join(cycle) for cycle in cycles])
182 raise UnorderableGraph('cycles in graph: %s' % cycles)
183 vertices = set(graph)
184 to_vertices = set()
185 for edges in graph.values():
186 to_vertices |= set(edges)
187 missing_vertices = to_vertices - vertices
188 if missing_vertices:
189 raise UnorderableGraph('missing vertices: %s' % ', '.join(missing_vertices))
190
191 order = []
192 order_set = set()
193 old_len = None
194 while graph:
195 if old_len == len(graph):
196 raise UnorderableGraph('unknown problem with %s' % graph)
197 old_len = len(graph)
198 deps_ok = []
199 for node, node_deps in graph.items():
200 for dep in node_deps:
201 if dep not in order_set:
202 break
203 else:
204 deps_ok.append(node)
205 order.append(deps_ok)
206 order_set |= set(deps_ok)
207 for node in deps_ok:
208 del graph[node]
209 result = []
210 for grp in reversed(order):
211 result.extend(sorted(grp))
212 return tuple(result)
213
214
216 '''given a dictionary representing an ordered graph (i.e. key are vertices
217 and values is a list of destination vertices representing edges), return a
218 list of detected cycles
219 '''
220 if not graph_dict:
221 return ()
222 result = []
223 if vertices is None:
224 vertices = graph_dict.keys()
225 for vertice in vertices:
226 _get_cycles(graph_dict, vertice, [], result)
227 return result
228
229 -def _get_cycles(graph_dict, vertice=None, path=None, result=None):
230 """recursive function doing the real work for get_cycles"""
231 if vertice in path:
232 cycle = [vertice]
233 for node in path[::-1]:
234 if node == vertice:
235 break
236 cycle.insert(0, node)
237
238 start_from = min(cycle)
239 index = cycle.index(start_from)
240 cycle = cycle[index:] + cycle[0:index]
241
242 if not cycle in result:
243 result.append(cycle)
244 return
245 path.append(vertice)
246 try:
247 for node in graph_dict[vertice]:
248 _get_cycles(graph_dict, node, path, result)
249 except KeyError:
250 pass
251 path.pop()
252
253 -def has_path(graph_dict, fromnode, tonode, path=None):
254 """generic function taking a simple graph definition as a dictionary, with
255 node has key associated to a list of nodes directly reachable from it.
256
257 Return None if no path exists to go from `fromnode` to `tonode`, else the
258 first path found (as a list including the destination node at last)
259 """
260 if path is None:
261 path = []
262 elif fromnode in path:
263 return None
264 path.append(fromnode)
265 for destnode in graph_dict[fromnode]:
266 if destnode == tonode or has_path(graph_dict, destnode, tonode, path):
267 return path[1:] + [tonode]
268 path.pop()
269 return None
270