backport a dot backend from yams

1 files changed, 155 insertions, 0 deletions

diff --git a/graph.py b/graph.py
new file mode 100644
index 0000000..d606162
--- /dev/null
+++ b/graph.py
@@ -0,0 +1,155 @@
+"""some various graph manipuliation utilities
+
+(dot generation adapted from pypy/translator/tool/make_dot.py)
+
+:version: $Revision: 1.6 $  
+:organization: Logilab
+:copyright: 2003-2005 LOGILAB S.A. (Paris, FRANCE), all rights reserved.
+:contact: http://www.logilab.fr/ -- mailto:contact@logilab.fr
+"""
+
+__docformat__ = "restructuredtext en"
+__metaclass__ = type
+
+def escape(value):
+    """make <value> 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):
+        self.graphname = graphname
+        self.lines = []
+        self._source = None
+        self.emit("digraph %s {" % graphname)
+        if rankdir:
+            self.emit('rankdir=%s' % rankdir)
+        if ratio:
+            self.emit('ratio=%s' % ratio)
+        if size:
+            self.emit('size="%s"' % size)
+
+    def get_source(self):
+        """returns self._source"""
+        if self._source is None:
+            self.emit("}")
+            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 target: output format ('png', 'ps', etc.). If None,
+                       the raw dot source will be returned
+        :return: a path to the generated file
+        """
+        if outputfile is not None:
+            storedir, basename, target = target_info_from_filename(outputfile)
+        else:
+            storedir = '/tmp'
+            basename = '%s.png' % (self.graphname)
+            target = 'png'
+            outputfile = osp.join(storedir, basename)
+        dotfile = dotfile or ('%s.dot' % self.graphname)
+        dot_sourcepath = osp.join(storedir, dotfile)
+        pdot = file(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('dot -T%s %s -o%s' % (target, dot_sourcepath, outputfile))
+            os.unlink(dot_sourcepath)
+        return outputfile
+
+    def emit(self, line):
+        """adds <line> to final output"""
+        self.lines.append(line)
+
+    def emit_edge(self, name1, name2, **props):
+        """emits edge from <name1> to <name2>
+        
+        authorized props: label, style, color, dir, weight
+        """
+        attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
+        self.emit('edge [%s];' % ", ".join(attrs))
+        self.emit('%s -> %s' % (name1.replace(' ', '_'), name2.replace(' ', '_')))
+
+    def emit_node(self, name, **props):
+        """authorized props: shape, label, color, fillcolor, style"""
+        attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
+        self.emit('%s [%s];' % (name.replace(' ', '_'), ", ".join(attrs)))
+
+
+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)
+            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()