Package logilab :: Package common :: Module graph
[frames] | no frames]

Source Code for Module logilab.common.graph

  1  # copyright 2003-2010 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   
 27  import os.path as osp 
 28  import os 
 29  import sys 
 30  import tempfile 
 31  from logilab.common.compat import str_encode 
 32   
33 -def escape(value):
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
39 -def target_info_from_filename(filename):
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
47 -class DotBackend:
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
69 - def get_source(self):
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 # introduced in py 2.4 89 name = self.graphname 90 if not dotfile: 91 # if 'outputfile' is a dot file use it as 'dotfile' 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
128 - def emit_edge(self, name1, name2, **props):
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
136 - def emit_node(self, name, **props):
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
143 -def normalize_node_id(nid):
144 """Returns a suitable DOT node id for `nid`.""" 145 return '"%s"' % nid
146
147 -class GraphGenerator:
148 - def __init__(self, backend):
149 # the backend is responsible to output the graph in a particular format 150 self.backend = backend
151 152 # XXX doesn't like space in outpufile / mapfile
153 - def generate(self, visitor, propshdlr, outputfile=None, mapfile=None):
154 # the visitor 155 # the property handler is used to get node and edge properties 156 # according to the graph and to the backend 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
167 -class UnorderableGraph(Exception):
168 pass
169
170 -def ordered_nodes(graph):
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 # check graph consistency 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 # order vertices 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
215 -def get_cycles(graph_dict, vertices=None):
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 # make a canonical representation 238 start_from = min(cycle) 239 index = cycle.index(start_from) 240 cycle = cycle[index:] + cycle[0:index] 241 # append it to result if not already in 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