Revert "Revert "pylint: upgrade to 1.3.1""

third_party/logilab/common/graph.py

 # copyright 2003-2011 LOGILAB S.A. (Paris, FRANCE), all rights reserved.
 # contact http://www.logilab.fr/ -- mailto:contact@logilab.fr
 #
 # This file is part of logilab-common.
 #
 # logilab-common is free software: you can redistribute it and/or modify it under
 # the terms of the GNU Lesser General Public License as published by the Free
 # Software Foundation, either version 2.1 of the License, or (at your option) any
 # later version.
 #
@@ skipping 10 matching lines @@
 """
 
 __docformat__ = "restructuredtext en"
 
 __metaclass__ = type
 
 import os.path as osp
 import os
 import sys
 import tempfile
-from logilab.common.compat import str_encode
+import codecs
+import errno
 
 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')."""
     basename = osp.basename(filename)
@@ skipping 14 matching lines @@
         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():
+        for param in sorted(additionnal_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
 
@@ skipping 22 matching lines @@
                 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 = open(dot_sourcepath, 'w')
-        pdot.write(str_encode(self.source, 'utf8'))
+        pdot = codecs.open(dot_sourcepath, 'w', encoding='utf8')
+        pdot.write(self.source)
         pdot.close()
         if target != 'dot':
             if sys.platform == 'win32':
                 use_shell = True
             else:
                 use_shell = False
-            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)
+            try:
+                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)
+            except OSError as e:
+                if e.errno == errno.ENOENT:
+                    e.strerror = 'File not found: {0}'.format(self.renderer)
+                    raise
             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(attrs)) )
+        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(attrs)))
+        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
 
 class GraphGenerator:
     def __init__(self, backend):
         # the backend is responsible to output the graph in a particular format
         self.backend = backend
 
@@ skipping 64 matching lines @@
     '''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, vertice, [], result)
+        _get_cycles(graph_dict, [], set(), result, vertice)
     return result
 
-def _get_cycles(graph_dict, vertice=None, path=None, result=None):
+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 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)
+            # 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()
 
 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 (as a list including the destination node at last)
     """
     if path is None:
         path = []
     elif fromnode in path:
         return None
     path.append(fromnode)
     for destnode in graph_dict[fromnode]:
         if destnode == tonode or has_path(graph_dict, destnode, tonode, path):
             return path[1:] + [tonode]
     path.pop()
     return None