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

Source Code for Module common.graph

  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   
 27  import os.path as osp 
 28  import os 
 29  import sys 
 30  import tempfile 
 31  import codecs 
 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.items(): 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 = codecs.open(dot_sourcepath, 'w', encoding='utf8') 110 pdot.write(self.source) 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
131 - def emit_edge(self, name1, name2, **props):
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(sorted(attrs))) )
138
139 - def emit_node(self, name, **props):
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(sorted(attrs))))
145
146 -def normalize_node_id(nid):
147 """Returns a suitable DOT node id for `nid`.""" 148 return '"%s"' % nid
149
150 -class GraphGenerator:
151 - def __init__(self, backend):
152 # the backend is responsible to output the graph in a particular format 153 self.backend = backend
154 155 # XXX doesn't like space in outpufile / mapfile
156 - def generate(self, visitor, propshdlr, outputfile=None, mapfile=None):
157 # the visitor 158 # the property handler is used to get node and edge properties 159 # according to the graph and to the backend 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
170 -class UnorderableGraph(Exception):
171 pass
172
173 -def ordered_nodes(graph):
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 # check graph consistency 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 # order vertices 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
218 -def get_cycles(graph_dict, vertices=None):
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 # make a canonical representation 241 start_from = min(cycle) 242 index = cycle.index(start_from) 243 cycle = cycle[index:] + cycle[0:index] 244 # append it to result if not already in 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 # don't check already visited nodes again 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