"""Graph manipuliation utilities. (dot generation adapted from pypy/translator/tool/make_dot.py) :copyright: 2000-2008 LOGILAB S.A. (Paris, FRANCE), all rights reserved. :contact: http://www.logilab.fr/ -- mailto:contact@logilab.fr :license: General Public License version 2 - http://www.gnu.org/licenses """ __docformat__ = "restructuredtext en" __metaclass__ = type import os.path as osp import os import tempfile def escape(value): """Make usable in a dot file.""" lines = [line.replace('"', '\\"') for line in value.split('\n')] data = '\\l'.join(lines) return '\\n' + data def target_info_from_filename(filename): """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png').""" abspath = osp.abspath(filename) basename = osp.basename(filename) storedir = osp.dirname(abspath) target = filename.split('.')[-1] return storedir, basename, target class DotBackend: """Dot File backend.""" def __init__(self, graphname, rankdir=None, size=None, ratio=None, charset='utf-8', renderer='dot', additionnal_param={}): self.graphname = graphname self.renderer = renderer self.lines = [] self._source = None self.emit("digraph %s {" % normalize_node_id(graphname)) if rankdir: self.emit('rankdir=%s' % rankdir) if ratio: self.emit('ratio=%s' % ratio) if size: self.emit('size="%s"' % size) if charset: assert charset.lower() in ('utf-8', 'iso-8859-1', 'latin1'), \ 'unsupported charset %s' % charset self.emit('charset="%s"' % charset) for param in additionnal_param.iteritems(): self.emit('='.join(param)) def get_source(self): """returns self._source""" if self._source is None: self.emit("}\n") self._source = '\n'.join(self.lines) del self.lines return self._source source = property(get_source) def generate(self, outputfile=None, dotfile=None): """Generates a graph file. :param outputfile: filename and path [defaults to graphname.png] :param dotfile: filename and path [defaults to graphname.dot] :rtype: str :return: a path to the generated file """ name = self.graphname dotfile = dotfile or ('%s.dot' % name) if outputfile is not None: storedir, basename, target = target_info_from_filename(outputfile) if target != "dot": pdot, dot_sourcepath = tempfile.mkstemp(".dot", name) else: dot_sourcepath = osp.join(storedir, dotfile) else: target = 'png' pdot, dot_sourcepath = tempfile.mkstemp(".dot", name) ppng, outputfile = tempfile.mkstemp(".png", name) pdot = open(dot_sourcepath,'w') if isinstance(self.source, unicode): pdot.write(self.source.encode('UTF8')) else: pdot.write(self.source) pdot.close() if target != 'dot': os.system('%s -T%s %s -o%s' % (self.renderer, target, dot_sourcepath, outputfile)) os.unlink(dot_sourcepath) return outputfile def emit(self, line): """Adds to final output.""" self.lines.append(line) def emit_edge(self, name1, name2, **props): """Emits edge from to . Authorized props: see http://www.graphviz.org/doc/info/attrs.html """ attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()] n_from, n_to = normalize_node_id(name1), normalize_node_id(name2) self.emit('%s -> %s [%s];' % (n_from, n_to, ", ".join(attrs)) ) def emit_node(self, name, **props): """Authorized props: see http://www.graphviz.org/doc/info/attrs.html """ attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()] self.emit('%s [%s];' % (normalize_node_id(name), ", ".join(attrs))) def normalize_node_id(nid): """Returns a suitable DOT node id for `nid`.""" return '"%s"' % nid class GraphGenerator: def __init__(self, backend): # the backend is responsible to output the graph is a particular format self.backend = backend def generate(self, visitor, propshdlr, outputfile=None): # the visitor # the properties handler is used to get nodes and edges properties # according to the graph and to the backend self.propshdlr = propshdlr for nodeid, node in visitor.nodes(): props = propshdlr.node_properties(node) self.backend.emit_node(nodeid, **props) for subjnode, objnode, edge in visitor.edges(): props = propshdlr.edge_properties(edge, subjnode, objnode) self.backend.emit_edge(subjnode, objnode, **props) return self.backend.generate(outputfile) def get_cycles(graph_dict, vertices=None): '''given a dictionnary representing an ordered graph (i.e. key are vertices and values is a list of destination vertices representing edges), return a list of detected cycles ''' if not graph_dict: return () result = [] if vertices is None: vertices = graph_dict.keys() for vertice in vertices: _get_cycles(graph_dict, vertice, [], result) return result def _get_cycles(graph_dict, vertice=None, path=None, result=None): """recursive function doing the real work for get_cycles""" if vertice in path: cycle = [vertice] for i in range(len(path)-1, 0, -1): node = path[i] if node == vertice: break cycle.insert(0, node) # make a canonical representation start_from = min(cycle) index = cycle.index(start_from) cycle = cycle[index:] + cycle[0:index] # append it to result if not already in if not cycle in result: result.append(cycle) return path.append(vertice) try: for node in graph_dict[vertice]: _get_cycles(graph_dict, node, path, result) except KeyError: pass path.pop() def has_path(graph_dict, fromnode, tonode, path=None): """generic function taking a simple graph definition as a dictionary, with node has key associated to a list of nodes directly reachable from it. Return None if no path exists to go from `fromnode` to `tonode`, else the first path found """ if path is None: path = [] elif fromnode in path: return False path.append(fromnode) for destnode in graph_dict[fromnode]: if destnode == tonode or has_path(graph_dict, destnode, tonode, path): return path[1:] path.pop() return None