Package logilab :: Package common :: Module graph

[frames] | no frames]

# Source Code for Module logilab.common.graph

      1  # copyright 2003-2011 LOGILAB S.A. (Paris, FRANCE), all rights reserved.
      2  # contact http://www.logilab.fr/ -- mailto:contact@logilab.fr
      3  #
      4  # This file is part of logilab-common.
      5  #
      6  # logilab-common is free software: you can redistribute it and/or modify it under
      7  # the terms of the GNU Lesser General Public License as published by the Free
      8  # Software Foundation, either version 2.1 of the License, or (at your option) any
      9  # later version.
     10  #
     11  # logilab-common is distributed in the hope that it will be useful, but WITHOUT
     12  # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
     13  # FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
     14  # details.
     15  #
     16  # You should have received a copy of the GNU Lesser General Public License along
     17  # with logilab-common.  If not, see <http://www.gnu.org/licenses/>.
     18  """Graph manipulation utilities.
     19
     20  (dot generation adapted from pypy/translator/tool/make_dot.py)
     21  """
     22
     23  __docformat__ = "restructuredtext en"
     24
     25  __metaclass__ = type
     26
     27  import os.path as osp
     28  import os
     29  import sys
     30  import tempfile
     31  import codecs
     32  import errno
     33
     34 -def escape(value):
     35      """Make <value> usable in a dot file."""
     36      lines = [line.replace('"', '\\"') for line in value.split('\n')]
     37      data = '\\l'.join(lines)
     38      return '\\n' + data
     39
     40 -def target_info_from_filename(filename):
     41      """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png')."""
     42      basename = osp.basename(filename)
     43      storedir = osp.dirname(osp.abspath(filename))
     44      target = filename.split('.')[-1]
     45      return storedir, basename, target
     46
     47
     48 -class DotBackend:
     49      """Dot File backend."""
     50 -    def __init__(self, graphname, rankdir=None, size=None, ratio=None,
     51              charset='utf-8', renderer='dot', additionnal_param={}):
     52          self.graphname = graphname
     53          self.renderer = renderer
     54          self.lines = []
     55          self._source = None
     56          self.emit("digraph %s {" % normalize_node_id(graphname))
     57          if rankdir:
     58              self.emit('rankdir=%s' % rankdir)
     59          if ratio:
     60              self.emit('ratio=%s' % ratio)
     61          if size:
     62              self.emit('size="%s"' % size)
     63          if charset:
     64              assert charset.lower() in ('utf-8', 'iso-8859-1', 'latin1'), \
     65                     'unsupported charset %s' % charset
     66              self.emit('charset="%s"' % charset)
     67          for param in sorted(additionnal_param.items()):
     68              self.emit('='.join(param))
     69
     70 -    def get_source(self):
     71          """returns self._source"""
     72          if self._source is None:
     73              self.emit("}\n")
     74              self._source = '\n'.join(self.lines)
     75              del self.lines
     76          return self._source
     77
     78      source = property(get_source)
     79
     80 -    def generate(self, outputfile=None, dotfile=None, mapfile=None):
     81          """Generates a graph file.
     82
     83          :param outputfile: filename and path [defaults to graphname.png]
     84          :param dotfile: filename and path [defaults to graphname.dot]
     85
     86          :rtype: str
     87          :return: a path to the generated file
     88          """
     89          import subprocess # introduced in py 2.4
     90          name = self.graphname
     91          if not dotfile:
     92              # if 'outputfile' is a dot file use it as 'dotfile'
     93              if outputfile and outputfile.endswith(".dot"):
     94                  dotfile = outputfile
     95              else:
     96                  dotfile = '%s.dot' % name
     97          if outputfile is not None:
     98              storedir, basename, target = target_info_from_filename(outputfile)
     99              if target != "dot":
    100                  pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
    101                  os.close(pdot)
    102              else:
    103                  dot_sourcepath = osp.join(storedir, dotfile)
    104          else:
    105              target = 'png'
    106              pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
    107              ppng, outputfile = tempfile.mkstemp(".png", name)
    108              os.close(pdot)
    109              os.close(ppng)
    110          pdot = codecs.open(dot_sourcepath, 'w', encoding='utf8')
    111          pdot.write(self.source)
    112          pdot.close()
    113          if target != 'dot':
    114              if sys.platform == 'win32':
    115                  use_shell = True
    116              else:
    117                  use_shell = False
    118              try:
    119                  if mapfile:
    120                      subprocess.call([self.renderer,  '-Tcmapx', '-o', mapfile, '-T', target, dot_sourcepath, '-o', outputfile],
    121                                      shell=use_shell)
    122                  else:
    123                      subprocess.call([self.renderer, '-T',  target,
    124                                       dot_sourcepath, '-o',  outputfile],
    125                                      shell=use_shell)
    126              except OSError as e:
    127                  if e.errno == errno.ENOENT:
    128                      e.strerror = 'File not found: {0}'.format(self.renderer)
    129                      raise
    130              os.unlink(dot_sourcepath)
    131          return outputfile
    132
    133 -    def emit(self, line):
    134          """Adds <line> to final output."""
    135          self.lines.append(line)
    136
    137 -    def emit_edge(self, name1, name2, **props):
    138          """emit an edge from <name1> to <name2>.
    139          edge properties: see http://www.graphviz.org/doc/info/attrs.html
    140          """
    141          attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
    142          n_from, n_to = normalize_node_id(name1), normalize_node_id(name2)
    143          self.emit('%s -> %s [%s];' % (n_from, n_to, ', '.join(sorted(attrs))) )
    144
    145 -    def emit_node(self, name, **props):
    146          """emit a node with given properties.
    147          node properties: see http://www.graphviz.org/doc/info/attrs.html
    148          """
    149          attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
    150          self.emit('%s [%s];' % (normalize_node_id(name), ', '.join(sorted(attrs))))
    151
    152 -def normalize_node_id(nid):
    153      """Returns a suitable DOT node id for `nid`."""
    154      return '"%s"' % nid
    155
    156 -class GraphGenerator:
    157 -    def __init__(self, backend):
    158          # the backend is responsible to output the graph in a particular format
    159          self.backend = backend
    160
    161      # XXX doesn't like space in outpufile / mapfile
    162 -    def generate(self, visitor, propshdlr, outputfile=None, mapfile=None):
    163          # the visitor
    164          # the property handler is used to get node and edge properties
    165          # according to the graph and to the backend
    166          self.propshdlr = propshdlr
    167          for nodeid, node in visitor.nodes():
    168              props = propshdlr.node_properties(node)
    169              self.backend.emit_node(nodeid, **props)
    170          for subjnode, objnode, edge in visitor.edges():
    171              props = propshdlr.edge_properties(edge, subjnode, objnode)
    172              self.backend.emit_edge(subjnode, objnode, **props)
    173          return self.backend.generate(outputfile=outputfile, mapfile=mapfile)
    174
    175
    176 -class UnorderableGraph(Exception):
    177      pass
    178
    179 -def ordered_nodes(graph):
    180      """takes a dependency graph dict as arguments and return an ordered tuple of
    181      nodes starting with nodes without dependencies and up to the outermost node.
    182
    183      If there is some cycle in the graph, :exc:`UnorderableGraph` will be raised.
    184
    185      Also the given graph dict will be emptied.
    186      """
    187      # check graph consistency
    188      cycles = get_cycles(graph)
    189      if cycles:
    190          cycles = '\n'.join([' -> '.join(cycle) for cycle in cycles])
    191          raise UnorderableGraph('cycles in graph: %s' % cycles)
    192      vertices = set(graph)
    193      to_vertices = set()
    194      for edges in graph.values():
    195          to_vertices |= set(edges)
    196      missing_vertices = to_vertices - vertices
    197      if missing_vertices:
    198          raise UnorderableGraph('missing vertices: %s' % ', '.join(missing_vertices))
    199      # order vertices
    200      order = []
    201      order_set = set()
    202      old_len = None
    203      while graph:
    204          if old_len == len(graph):
    205              raise UnorderableGraph('unknown problem with %s' % graph)
    206          old_len = len(graph)
    207          deps_ok = []
    208          for node, node_deps in graph.items():
    209              for dep in node_deps:
    210                  if dep not in order_set:
    211                      break
    212              else:
    213                  deps_ok.append(node)
    214          order.append(deps_ok)
    215          order_set |= set(deps_ok)
    216          for node in deps_ok:
    217              del graph[node]
    218      result = []
    219      for grp in reversed(order):
    220          result.extend(sorted(grp))
    221      return tuple(result)
    222
    223
    224 -def get_cycles(graph_dict, vertices=None):
    225      '''given a dictionary representing an ordered graph (i.e. key are vertices
    226      and values is a list of destination vertices representing edges), return a
    227      list of detected cycles
    228      '''
    229      if not graph_dict:
    230          return ()
    231      result = []
    232      if vertices is None:
    233          vertices = graph_dict.keys()
    234      for vertice in vertices:
    235          _get_cycles(graph_dict, [], set(), result, vertice)
    236      return result
    237
    238 -def _get_cycles(graph_dict, path, visited, result, vertice):
    239      """recursive function doing the real work for get_cycles"""
    240      if vertice in path:
    241          cycle = [vertice]
    242          for node in path[::-1]:
    243              if node == vertice:
    244                  break
    245              cycle.insert(0, node)
    246          # make a canonical representation
    247          start_from = min(cycle)
    248          index = cycle.index(start_from)
    249          cycle = cycle[index:] + cycle[0:index]
    250          # append it to result if not already in
    251          if not cycle in result:
    252              result.append(cycle)
    253          return
    254      path.append(vertice)
    255      try:
    256          for node in graph_dict[vertice]:
    257              # don't check already visited nodes again
    258              if node not in visited:
    259                  _get_cycles(graph_dict, path, visited, result, node)
    260                  visited.add(node)
    261      except KeyError:
    262          pass
    263      path.pop()
    264
    265 -def has_path(graph_dict, fromnode, tonode, path=None):
    266      """generic function taking a simple graph definition as a dictionary, with
    267      node has key associated to a list of nodes directly reachable from it.
    268
    269      Return None if no path exists to go from `fromnode` to `tonode`, else the
    270      first path found (as a list including the destination node at last)
    271      """
    272      if path is None:
    273          path = []
    274      elif fromnode in path:
    275          return None
    276      path.append(fromnode)
    277      for destnode in graph_dict[fromnode]:
    278          if destnode == tonode or has_path(graph_dict, destnode, tonode, path):
    279              return path[1:] + [tonode]
    280      path.pop()
    281      return None
    282