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 under 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) any 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 27import os.path as osp 28import os 29import sys 30import tempfile 31import codecs 32import errno 33 34def 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 40def 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 48class 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 152def normalize_node_id(nid): 153 """Returns a suitable DOT node id for `nid`.""" 154 return '"%s"' % nid 155 156class 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 176class UnorderableGraph(Exception): 177 pass 178 179def 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_vertices)) 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 224def 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 238def _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 265def 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 283