OLD | NEW |
(Empty) | |
| 1 # copyright 2003-2011 LOGILAB S.A. (Paris, FRANCE), all rights reserved. |
| 2 # contact http://www.logilab.fr/ -- mailto:contact@logilab.fr |
| 3 # |
| 4 # This file is part of logilab-common. |
| 5 # |
| 6 # logilab-common is free software: you can redistribute it and/or modify it unde
r |
| 7 # the terms of the GNU Lesser General Public License as published by the Free |
| 8 # Software Foundation, either version 2.1 of the License, or (at your option) an
y |
| 9 # later version. |
| 10 # |
| 11 # logilab-common is distributed in the hope that it will be useful, but WITHOUT |
| 12 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
| 13 # FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more |
| 14 # details. |
| 15 # |
| 16 # You should have received a copy of the GNU Lesser General Public License along |
| 17 # with logilab-common. If not, see <http://www.gnu.org/licenses/>. |
| 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 |
| 34 def escape(value): |
| 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 |
| 40 def target_info_from_filename(filename): |
| 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 |
| 48 class DotBackend: |
| 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 |
| 70 def get_source(self): |
| 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 # introduced in py 2.4 |
| 90 name = self.graphname |
| 91 if not dotfile: |
| 92 # if 'outputfile' is a dot file use it as 'dotfile' |
| 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 |
| 137 def emit_edge(self, name1, name2, **props): |
| 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 |
| 145 def emit_node(self, name, **props): |
| 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 |
| 152 def normalize_node_id(nid): |
| 153 """Returns a suitable DOT node id for `nid`.""" |
| 154 return '"%s"' % nid |
| 155 |
| 156 class GraphGenerator: |
| 157 def __init__(self, backend): |
| 158 # the backend is responsible to output the graph in a particular format |
| 159 self.backend = backend |
| 160 |
| 161 # XXX doesn't like space in outpufile / mapfile |
| 162 def generate(self, visitor, propshdlr, outputfile=None, mapfile=None): |
| 163 # the visitor |
| 164 # the property handler is used to get node and edge properties |
| 165 # according to the graph and to the backend |
| 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 |
| 176 class UnorderableGraph(Exception): |
| 177 pass |
| 178 |
| 179 def ordered_nodes(graph): |
| 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 # check graph consistency |
| 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_vertic
es)) |
| 199 # order vertices |
| 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 |
| 224 def get_cycles(graph_dict, vertices=None): |
| 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 # make a canonical representation |
| 247 start_from = min(cycle) |
| 248 index = cycle.index(start_from) |
| 249 cycle = cycle[index:] + cycle[0:index] |
| 250 # append it to result if not already in |
| 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 # don't check already visited nodes again |
| 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 |
OLD | NEW |