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

Source Code for Module logilab.common.graph

  1  """Graph manipulation utilities. 
  2   
  3  (dot generation adapted from pypy/translator/tool/make_dot.py) 
  4   
  5  :copyright: 2000-2009 LOGILAB S.A. (Paris, FRANCE), all rights reserved. 
  6  :contact: http://www.logilab.fr/ -- mailto:contact@logilab.fr 
  7  :license: General Public License version 2 - http://www.gnu.org/licenses 
  8  """ 
  9  __docformat__ = "restructuredtext en" 
 10   
 11  __metaclass__ = type 
 12   
 13  import os.path as osp 
 14  import os 
 15  import subprocess 
 16  import sys 
 17  import tempfile 
 18   
19 -def escape(value):
20 """Make <value> usable in a dot file.""" 21 lines = [line.replace('"', '\\"') for line in value.split('\n')] 22 data = '\\l'.join(lines) 23 return '\\n' + data
24
25 -def target_info_from_filename(filename):
26 """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png').""" 27 basename = osp.basename(filename) 28 storedir = osp.dirname(osp.abspath(filename)) 29 target = filename.split('.')[-1] 30 return storedir, basename, target
31 32
33 -class DotBackend:
34 """Dot File backend."""
35 - def __init__(self, graphname, rankdir=None, size=None, ratio=None, 36 charset='utf-8', renderer='dot', additionnal_param={}):
37 self.graphname = graphname 38 self.renderer = renderer 39 self.lines = [] 40 self._source = None 41 self.emit("digraph %s {" % normalize_node_id(graphname)) 42 if rankdir: 43 self.emit('rankdir=%s' % rankdir) 44 if ratio: 45 self.emit('ratio=%s' % ratio) 46 if size: 47 self.emit('size="%s"' % size) 48 if charset: 49 assert charset.lower() in ('utf-8', 'iso-8859-1', 'latin1'), \ 50 'unsupported charset %s' % charset 51 self.emit('charset="%s"' % charset) 52 for param in additionnal_param.iteritems(): 53 self.emit('='.join(param))
54
55 - def get_source(self):
56 """returns self._source""" 57 if self._source is None: 58 self.emit("}\n") 59 self._source = '\n'.join(self.lines) 60 del self.lines 61 return self._source
62 63 source = property(get_source) 64
65 - def generate(self, outputfile=None, dotfile=None):
66 """Generates a graph file. 67 68 :param outputfile: filename and path [defaults to graphname.png] 69 :param dotfile: filename and path [defaults to graphname.dot] 70 71 :rtype: str 72 :return: a path to the generated file 73 """ 74 name = self.graphname 75 if not dotfile: 76 # if 'outputfile' is a dot file use it as 'dotfile' 77 if outputfile and outputfile.endswith(".dot"): 78 dotfile = outputfile 79 else: 80 dotfile = '%s.dot' % name 81 if outputfile is not None: 82 storedir, basename, target = target_info_from_filename(outputfile) 83 if target != "dot": 84 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name) 85 os.close(pdot) 86 else: 87 dot_sourcepath = osp.join(storedir, dotfile) 88 else: 89 target = 'png' 90 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name) 91 ppng, outputfile = tempfile.mkstemp(".png", name) 92 os.close(pdot) 93 os.close(ppng) 94 pdot = open(dot_sourcepath,'w') 95 if isinstance(self.source, unicode): 96 pdot.write(self.source.encode('UTF8')) 97 else: 98 pdot.write(self.source) 99 pdot.close() 100 if target != 'dot': 101 subprocess.call('%s -T%s %s -o%s' % (self.renderer, target, 102 dot_sourcepath, outputfile), shell=True) 103 os.unlink(dot_sourcepath) 104 return outputfile
105
106 - def emit(self, line):
107 """Adds <line> to final output.""" 108 self.lines.append(line)
109
110 - def emit_edge(self, name1, name2, **props):
111 """emit an edge from <name1> to <name2>. 112 edge properties: see http://www.graphviz.org/doc/info/attrs.html 113 """ 114 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()] 115 n_from, n_to = normalize_node_id(name1), normalize_node_id(name2) 116 self.emit('%s -> %s [%s];' % (n_from, n_to, ", ".join(attrs)) )
117
118 - def emit_node(self, name, **props):
119 """emit a node with given properties. 120 node properties: see http://www.graphviz.org/doc/info/attrs.html 121 """ 122 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()] 123 self.emit('%s [%s];' % (normalize_node_id(name), ", ".join(attrs)))
124
125 -def normalize_node_id(nid):
126 """Returns a suitable DOT node id for `nid`.""" 127 return '"%s"' % nid
128
129 -class GraphGenerator:
130 - def __init__(self, backend):
131 # the backend is responsible to output the graph in a particular format 132 self.backend = backend
133
134 - def generate(self, visitor, propshdlr, outputfile=None):
135 # the visitor 136 # the property handler is used to get node and edge properties 137 # according to the graph and to the backend 138 self.propshdlr = propshdlr 139 for nodeid, node in visitor.nodes(): 140 props = propshdlr.node_properties(node) 141 self.backend.emit_node(nodeid, **props) 142 for subjnode, objnode, edge in visitor.edges(): 143 props = propshdlr.edge_properties(edge, subjnode, objnode) 144 self.backend.emit_edge(subjnode, objnode, **props) 145 return self.backend.generate(outputfile)
146 147 148
149 -def get_cycles(graph_dict, vertices=None):
150 '''given a dictionary representing an ordered graph (i.e. key are vertices 151 and values is a list of destination vertices representing edges), return a 152 list of detected cycles 153 ''' 154 if not graph_dict: 155 return () 156 result = [] 157 if vertices is None: 158 vertices = graph_dict.keys() 159 for vertice in vertices: 160 _get_cycles(graph_dict, vertice, [], result) 161 return result
162
163 -def _get_cycles(graph_dict, vertice=None, path=None, result=None):
164 """recursive function doing the real work for get_cycles""" 165 if vertice in path: 166 cycle = [vertice] 167 for node in path[::-1]: 168 if node == vertice: 169 break 170 cycle.insert(0, node) 171 # make a canonical representation 172 start_from = min(cycle) 173 index = cycle.index(start_from) 174 cycle = cycle[index:] + cycle[0:index] 175 # append it to result if not already in 176 if not cycle in result: 177 result.append(cycle) 178 return 179 path.append(vertice) 180 try: 181 for node in graph_dict[vertice]: 182 _get_cycles(graph_dict, node, path, result) 183 except KeyError: 184 pass 185 path.pop()
186
187 -def has_path(graph_dict, fromnode, tonode, path=None):
188 """generic function taking a simple graph definition as a dictionary, with 189 node has key associated to a list of nodes directly reachable from it. 190 191 Return None if no path exists to go from `fromnode` to `tonode`, else the 192 first path found (as a list including the destination node at last) 193 """ 194 if path is None: 195 path = [] 196 elif fromnode in path: 197 return None 198 path.append(fromnode) 199 for destnode in graph_dict[fromnode]: 200 if destnode == tonode or has_path(graph_dict, destnode, tonode, path): 201 return path[1:] + [tonode] 202 path.pop() 203 return None
204