| # Copyright (c) 2003-2013 LOGILAB S.A. (Paris, FRANCE). |
| # This program is free software; you can redistribute it and/or modify it under |
| # the terms of the GNU General Public License as published by the Free Software |
| # Foundation; either version 2 of the License, or (at your option) any later |
| # version. |
| # |
| # This program is distributed in the hope that it will be useful, but WITHOUT |
| # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
| # FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details |
| # |
| # You should have received a copy of the GNU General Public License along with |
| # this program; if not, write to the Free Software Foundation, Inc., |
| # 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. |
| |
| # This file was copied from logilab-common with the same license: |
| # copyright 2003-2011 LOGILAB S.A. (Paris, FRANCE), all rights reserved. |
| """Graph manipulation utilities. |
| |
| (dot generation adapted from pypy/translator/tool/make_dot.py) |
| """ |
| |
| import os.path as osp |
| import os |
| import sys |
| import tempfile |
| import codecs |
| |
| def target_info_from_filename(filename): |
| """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png').""" |
| basename = osp.basename(filename) |
| storedir = osp.dirname(osp.abspath(filename)) |
| target = filename.split('.')[-1] |
| return storedir, basename, target |
| |
| |
| class DotBackend(object): |
| """Dot File backend.""" |
| def __init__(self, graphname, rankdir=None, size=None, ratio=None, |
| charset='utf-8', renderer='dot', additional_param=None): |
| if additional_param is None: |
| additional_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 additional_param.items(): |
| 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, mapfile=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 |
| """ |
| import subprocess # introduced in py 2.4 |
| name = self.graphname |
| if not dotfile: |
| # if 'outputfile' is a dot file use it as 'dotfile' |
| if outputfile and outputfile.endswith(".dot"): |
| dotfile = outputfile |
| else: |
| dotfile = '%s.dot' % name |
| if outputfile is not None: |
| storedir, _, target = target_info_from_filename(outputfile) |
| if target != "dot": |
| pdot, dot_sourcepath = tempfile.mkstemp(".dot", name) |
| os.close(pdot) |
| else: |
| dot_sourcepath = osp.join(storedir, dotfile) |
| else: |
| target = 'png' |
| pdot, dot_sourcepath = tempfile.mkstemp(".dot", name) |
| ppng, outputfile = tempfile.mkstemp(".png", name) |
| os.close(pdot) |
| os.close(ppng) |
| pdot = codecs.open(dot_sourcepath, 'w', encoding='utf8') |
| pdot.write(self.source) |
| pdot.close() |
| if target != 'dot': |
| use_shell = sys.platform == 'win32' |
| if mapfile: |
| subprocess.call([self.renderer, '-Tcmapx', '-o', |
| mapfile, '-T', target, dot_sourcepath, |
| '-o', outputfile], |
| shell=use_shell) |
| else: |
| subprocess.call([self.renderer, '-T', target, |
| dot_sourcepath, '-o', outputfile], |
| shell=use_shell) |
| 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): |
| """emit an edge from <name1> to <name2>. |
| edge properties: 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(sorted(attrs)))) |
| |
| def emit_node(self, name, **props): |
| """emit a node with given properties. |
| node properties: 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(sorted(attrs)))) |
| |
| def normalize_node_id(nid): |
| """Returns a suitable DOT node id for `nid`.""" |
| return '"%s"' % nid |
| |
| def get_cycles(graph_dict, vertices=None): |
| '''given a dictionary 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, [], set(), result, vertice) |
| return result |
| |
| def _get_cycles(graph_dict, path, visited, result, vertice): |
| """recursive function doing the real work for get_cycles""" |
| if vertice in path: |
| cycle = [vertice] |
| for node in path[::-1]: |
| 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 cycle not in result: |
| result.append(cycle) |
| return |
| path.append(vertice) |
| try: |
| for node in graph_dict[vertice]: |
| # don't check already visited nodes again |
| if node not in visited: |
| _get_cycles(graph_dict, path, visited, result, node) |
| visited.add(node) |
| except KeyError: |
| pass |
| path.pop() |
