Package logilab-common-0 :: Package 36 :: Package 1 :: Module graph
[frames] | no frames]

Source Code for Module logilab-common-0.36.1.graph

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