graph: fix and test ordered_nodes() [closes #60288]

2 files changed, 66 insertions, 20 deletions

diff --git a/graph.py b/graph.py
index 6715e9b..ae27d45 100644
--- a/graph.py
+++ b/graph.py
@@ -165,11 +165,7 @@ class GraphGenerator:
 
 
 class UnorderableGraph(Exception):
-    def __init__(self, cycles):
-        self.cycles = cycles
-
-    def __str__(self):
-        return 'cycles in graph: %s' % self.cycles
+    pass
 
 def ordered_nodes(graph):
     """takes a dependency graph dict as arguments and return an ordered tuple of
@@ -179,24 +175,38 @@ def ordered_nodes(graph):
 
     Also the given graph dict will be emptied.
     """
+    # check graph consistency
     cycles = get_cycles(graph)
     if cycles:
         cycles = '\n'.join([' -> '.join(cycle) for cycle in cycles])
-        raise UnorderableGraph(cycles)
-    ordered = []
+        raise UnorderableGraph('cycles in graph: %s' % cycles)
+    vertices = set(graph)
+    to_vertices = set()
+    for edges in graph.values():
+        to_vertices |= set(edges)
+    missing_vertices = to_vertices - vertices
+    if missing_vertices:
+        raise UnorderableGraph('missing vertices: %s' % ', '.join(missing_vertices))
+    # order vertices
+    order = []
+    order_set = set()
+    old_len = None
     while graph:
-        # sorted to get predictable results
-        for node, deps in sorted(graph.items(), key=id):
-            if not deps:
-                ordered.append(node)
-                del graph[node]
-                for deps in graph.itervalues():
-                    try:
-                        deps.remove(node)
-                    except KeyError:
-                        continue
-    return tuple(reversed(ordered))
-
+        if old_len == len(graph):
+            raise UnorderableGraph('unknown problem with %s' % graph)
+        old_len = len(graph)
+        deps_ok = []
+        for node, node_deps in graph.items():
+            for dep in node_deps:
+                if dep not in order_set:
+                    break
+            else:
+                deps_ok.append(node)
+        order.extend(sorted(deps_ok))
+        order_set |= set(deps_ok)
+        for node in deps_ok:
+            del graph[node]
+    return tuple(order)
 
 
 def get_cycles(graph_dict, vertices=None):
diff --git a/test/unittest_graph.py b/test/unittest_graph.py
index 06e1046..e72d8d4 100644
--- a/test/unittest_graph.py
+++ b/test/unittest_graph.py
@@ -18,7 +18,7 @@
 # with logilab-common.  If not, see <http://www.gnu.org/licenses/>.
 
 from logilab.common.testlib import TestCase, unittest_main
-from logilab.common.graph import get_cycles, has_path
+from logilab.common.graph import get_cycles, has_path, ordered_nodes, UnorderableGraph
 
 class getCyclesTC(TestCase):
 
@@ -46,5 +46,41 @@ class hasPathTC(TestCase):
     def test_cycle(self):
         self.assertEqual(has_path({'A': ['A']}, 'A', 'B'), None)
 
+class ordered_nodesTC(TestCase):
+
+    def test_one_item(self):
+        graph = {'a':[]}
+        ordered = ordered_nodes(graph)
+        self.assertEqual(ordered, ('a',))
+
+    def test_single_dependency(self):
+        graph = {'a':[], 'b':['a']}
+        ordered = ordered_nodes(graph)
+        self.assertEqual(ordered, ('a','b'))
+
+    def test_two_items_no_dependency(self):
+        graph = {'a':[], 'b':[]}
+        ordered = ordered_nodes(graph)
+        self.assertEqual(ordered, ('a','b'))
+
+    def test_three_items_no_dependency(self):
+        graph = {'a':[], 'b':[], 'c':[]}
+        ordered = ordered_nodes(graph)
+        self.assertEqual(ordered, ('a', 'b', 'c'))
+
+    def test_three_items_one_dependency(self):
+        graph = {'a': ['b'], 'b': [], 'c':[]}
+        ordered = ordered_nodes(graph)
+        self.assertEqual(ordered, ('b', 'c', 'a'))
+
+    def test_three_items_two_dependencies(self):
+        graph = {'a': ['b'], 'b': ['c'], 'c':[]}
+        ordered = ordered_nodes(graph)
+        self.assertEqual(ordered, ('c', 'b', 'a'))
+
+    def test_bad_graph(self):
+        graph = {'a':['b']}
+        self.assertRaises(UnorderableGraph, ordered_nodes, graph)
+
 if __name__ == "__main__":
     unittest_main()