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   
 24   
 25  """ 
 26  __docformat__ = "restructuredtext en" 
 27   
 28  __metaclass__ = type 
 29   
 30  import os.path as osp 
 31  import os 
 32  import subprocess 
 33  import sys 
 34  import tempfile 
 35   
36 -def escape(value):
37 """Make <value> usable in a dot file.""" 38 lines = [line.replace('"', '\\"') for line in value.split('\n')] 39 data = '\\l'.join(lines) 40 return '\\n' + data
41
42 -def target_info_from_filename(filename):
43 """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png').""" 44 basename = osp.basename(filename) 45 storedir = osp.dirname(osp.abspath(filename)) 46 target = filename.split('.')[-1] 47 return storedir, basename, target
48 49
50 -class DotBackend:
51 """Dot File backend."""
52 - def __init__(self, graphname, rankdir=None, size=None, ratio=None, 53 charset='utf-8', renderer='dot', additionnal_param={}):
54 self.graphname = graphname 55 self.renderer = renderer 56 self.lines = [] 57 self._source = None 58 self.emit("digraph %s {" % normalize_node_id(graphname)) 59 if rankdir: 60 self.emit('rankdir=%s' % rankdir) 61 if ratio: 62 self.emit('ratio=%s' % ratio) 63 if size: 64 self.emit('size="%s"' % size) 65 if charset: 66 assert charset.lower() in ('utf-8', 'iso-8859-1', 'latin1'), \ 67 'unsupported charset %s' % charset 68 self.emit('charset="%s"' % charset) 69 for param in additionnal_param.iteritems(): 70 self.emit('='.join(param))
71
72 - def get_source(self):
73 """returns self._source""" 74 if self._source is None: 75 self.emit("}\n") 76 self._source = '\n'.join(self.lines) 77 del self.lines 78 return self._source
79 80 source = property(get_source) 81
82 - def generate(self, outputfile=None, dotfile=None, mapfile=None):
83 """Generates a graph file. 84 85 :param outputfile: filename and path [defaults to graphname.png] 86 :param dotfile: filename and path [defaults to graphname.dot] 87 88 :rtype: str 89 :return: a path to the generated file 90 """ 91 name = self.graphname 92 if not dotfile: 93 # if 'outputfile' is a dot file use it as 'dotfile' 94 if outputfile and outputfile.endswith(".dot"): 95 dotfile = outputfile 96 else: 97 dotfile = '%s.dot' % name 98 if outputfile is not None: 99 storedir, basename, target = target_info_from_filename(outputfile) 100 if target != "dot": 101 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name) 102 os.close(pdot) 103 else: 104 dot_sourcepath = osp.join(storedir, dotfile) 105 else: 106 target = 'png' 107 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name) 108 ppng, outputfile = tempfile.mkstemp(".png", name) 109 os.close(pdot) 110 os.close(ppng) 111 pdot = open(dot_sourcepath,'w') 112 if isinstance(self.source, unicode): 113 pdot.write(self.source.encode('UTF8')) 114 else: 115 pdot.write(self.source) 116 pdot.close() 117 if target != 'dot': 118 if mapfile: 119 subprocess.call('%s -Tcmapx -o%s -T%s %s -o%s' % (self.renderer, mapfile, 120 target, dot_sourcepath, outputfile), shell=True) 121 else: 122 subprocess.call('%s -T%s %s -o%s' % (self.renderer, target, 123 dot_sourcepath, outputfile), shell=True) 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 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(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 props.items()] 144 self.emit('%s [%s];' % (normalize_node_id(name), ", ".join(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 - def generate(self, visitor, propshdlr, outputfile=None, mapfile=None):
156 # the visitor 157 # the property handler is used to get node and edge properties 158 # according to the graph and to the backend 159 self.propshdlr = propshdlr 160 for nodeid, node in visitor.nodes(): 161 props = propshdlr.node_properties(node) 162 self.backend.emit_node(nodeid, **props) 163 for subjnode, objnode, edge in visitor.edges(): 164 props = propshdlr.edge_properties(edge, subjnode, objnode) 165 self.backend.emit_edge(subjnode, objnode, **props) 166 return self.backend.generate(outputfile=outputfile, mapfile=mapfile)
167 168
169 -class UnorderableGraph(Exception):
170 - def __init__(self, cycles):
171 self.cycles = cycles
172
173 - def __str__(self):
174 return 'cycles in graph: %s' % self.cycles
175
176 -def ordered_nodes(graph):
177 """takes a dependency graph dict as arguments and return an ordered tuple of 178 nodes starting with nodes without dependencies and up to the outermost node. 179 180 If there is some cycle in the graph, :exc:`UnorderableGraph` will be raised. 181 182 Also the given graph dict will be emptied. 183 """ 184 cycles = get_cycles(graph) 185 if cycles: 186 cycles = '\n'.join(' -> '.join(cycle) for cycle in cycles) 187 raise UnorderableGraph(cycles) 188 ordered = [] 189 while graph: 190 # sorted to get predictable results 191 for node, deps in sorted(graph.items()): 192 if not deps: 193 ordered.append(node) 194 del graph[node] 195 for deps in graph.itervalues(): 196 try: 197 deps.remove(node) 198 except KeyError: 199 continue 200 return tuple(reversed(ordered))
201 202 203
204 -def get_cycles(graph_dict, vertices=None):
205 '''given a dictionary representing an ordered graph (i.e. key are vertices 206 and values is a list of destination vertices representing edges), return a 207 list of detected cycles 208 ''' 209 if not graph_dict: 210 return () 211 result = [] 212 if vertices is None: 213 vertices = graph_dict.keys() 214 for vertice in vertices: 215 _get_cycles(graph_dict, vertice, [], result) 216 return result
217
218 -def _get_cycles(graph_dict, vertice=None, path=None, result=None):
219 """recursive function doing the real work for get_cycles""" 220 if vertice in path: 221 cycle = [vertice] 222 for node in path[::-1]: 223 if node == vertice: 224 break 225 cycle.insert(0, node) 226 # make a canonical representation 227 start_from = min(cycle) 228 index = cycle.index(start_from) 229 cycle = cycle[index:] + cycle[0:index] 230 # append it to result if not already in 231 if not cycle in result: 232 result.append(cycle) 233 return 234 path.append(vertice) 235 try: 236 for node in graph_dict[vertice]: 237 _get_cycles(graph_dict, node, path, result) 238 except KeyError: 239 pass 240 path.pop()
241
242 -def has_path(graph_dict, fromnode, tonode, path=None):
243 """generic function taking a simple graph definition as a dictionary, with 244 node has key associated to a list of nodes directly reachable from it. 245 246 Return None if no path exists to go from `fromnode` to `tonode`, else the 247 first path found (as a list including the destination node at last) 248 """ 249 if path is None: 250 path = [] 251 elif fromnode in path: 252 return None 253 path.append(fromnode) 254 for destnode in graph_dict[fromnode]: 255 if destnode == tonode or has_path(graph_dict, destnode, tonode, path): 256 return path[1:] + [tonode] 257 path.pop() 258 return None
259