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

authorNicolas Chauvat <nicolas.chauvat@logilab.fr>
changesetc6252aee1c87
branchstable
phasepublic
hiddenno
parent revision#da3b9cbfdfc3 refactor to ease overriding
child revision#4f4fc466af0c this will be version 0.54.1
files modified by this revision
graph.py
test/unittest_graph.py
# HG changeset patch
# User Nicolas Chauvat <nicolas.chauvat@logilab.fr>
# Date 1296495447 -3600
# Mon Jan 31 18:37:27 2011 +0100
# Branch stable
# Node ID c6252aee1c874cfe0bb4336939c78494c18d5ced
# Parent da3b9cbfdfc37666849be2b3fa752be3b628f81f
graph: fix and test ordered_nodes() [closes #60288]

diff --git a/graph.py b/graph.py
@@ -163,42 +163,52 @@
1              self.backend.emit_edge(subjnode, objnode, **props)
2          return self.backend.generate(outputfile=outputfile, mapfile=mapfile)
3 
4 
5  class UnorderableGraph(Exception):
6 -    def __init__(self, cycles):
7 -        self.cycles = cycles
8 -
9 -    def __str__(self):
10 -        return 'cycles in graph: %s' % self.cycles
11 +    pass
12 
13  def ordered_nodes(graph):
14      """takes a dependency graph dict as arguments and return an ordered tuple of
15      nodes starting with nodes without dependencies and up to the outermost node.
16 
17      If there is some cycle in the graph, :exc:`UnorderableGraph` will be raised.
18 
19      Also the given graph dict will be emptied.
20      """
21 +    # check graph consistency
22      cycles = get_cycles(graph)
23      if cycles:
24          cycles = '\n'.join([' -> '.join(cycle) for cycle in cycles])
25 -        raise UnorderableGraph(cycles)
26 -    ordered = []
27 +        raise UnorderableGraph('cycles in graph: %s' % cycles)
28 +    vertices = set(graph)
29 +    to_vertices = set()
30 +    for edges in graph.values():
31 +        to_vertices |= set(edges)
32 +    missing_vertices = to_vertices - vertices
33 +    if missing_vertices:
34 +        raise UnorderableGraph('missing vertices: %s' % ', '.join(missing_vertices))
35 +    # order vertices
36 +    order = []
37 +    order_set = set()
38 +    old_len = None
39      while graph:
40 -        # sorted to get predictable results
41 -        for node, deps in sorted(graph.items(), key=id):
42 -            if not deps:
43 -                ordered.append(node)
44 -                del graph[node]
45 -                for deps in graph.itervalues():
46 -                    try:
47 -                        deps.remove(node)
48 -                    except KeyError:
49 -                        continue
50 -    return tuple(reversed(ordered))
51 -
52 +        if old_len == len(graph):
53 +            raise UnorderableGraph('unknown problem with %s' % graph)
54 +        old_len = len(graph)
55 +        deps_ok = []
56 +        for node, node_deps in graph.items():
57 +            for dep in node_deps:
58 +                if dep not in order_set:
59 +                    break
60 +            else:
61 +                deps_ok.append(node)
62 +        order.extend(sorted(deps_ok))
63 +        order_set |= set(deps_ok)
64 +        for node in deps_ok:
65 +            del graph[node]
66 +    return tuple(order)
67 
68 
69  def get_cycles(graph_dict, vertices=None):
70      '''given a dictionary representing an ordered graph (i.e. key are vertices
71      and values is a list of destination vertices representing edges), return a
diff --git a/test/unittest_graph.py b/test/unittest_graph.py
@@ -16,11 +16,11 @@
72  #
73  # You should have received a copy of the GNU Lesser General Public License along
74  # with logilab-common.  If not, see <http://www.gnu.org/licenses/>.
75 
76  from logilab.common.testlib import TestCase, unittest_main
77 -from logilab.common.graph import get_cycles, has_path
78 +from logilab.common.graph import get_cycles, has_path, ordered_nodes, UnorderableGraph
79 
80  class getCyclesTC(TestCase):
81 
82      def test_known0(self):
83          self.assertEqual(get_cycles({1:[2], 2:[3], 3:[1]}), [[1, 2, 3]])
@@ -44,7 +44,43 @@
84          self.assertEqual(has_path({'A': ['B'], 'B': ['A']}, 'A', 'C'), None)
85 
86      def test_cycle(self):
87          self.assertEqual(has_path({'A': ['A']}, 'A', 'B'), None)
88 
89 +class ordered_nodesTC(TestCase):
90 +
91 +    def test_one_item(self):
92 +        graph = {'a':[]}
93 +        ordered = ordered_nodes(graph)
94 +        self.assertEqual(ordered, ('a',))
95 +
96 +    def test_single_dependency(self):
97 +        graph = {'a':[], 'b':['a']}
98 +        ordered = ordered_nodes(graph)
99 +        self.assertEqual(ordered, ('a','b'))
100 +
101 +    def test_two_items_no_dependency(self):
102 +        graph = {'a':[], 'b':[]}
103 +        ordered = ordered_nodes(graph)
104 +        self.assertEqual(ordered, ('a','b'))
105 +
106 +    def test_three_items_no_dependency(self):
107 +        graph = {'a':[], 'b':[], 'c':[]}
108 +        ordered = ordered_nodes(graph)
109 +        self.assertEqual(ordered, ('a', 'b', 'c'))
110 +
111 +    def test_three_items_one_dependency(self):
112 +        graph = {'a': ['b'], 'b': [], 'c':[]}
113 +        ordered = ordered_nodes(graph)
114 +        self.assertEqual(ordered, ('b', 'c', 'a'))
115 +
116 +    def test_three_items_two_dependencies(self):
117 +        graph = {'a': ['b'], 'b': ['c'], 'c':[]}
118 +        ordered = ordered_nodes(graph)
119 +        self.assertEqual(ordered, ('c', 'b', 'a'))
120 +
121 +    def test_bad_graph(self):
122 +        graph = {'a':['b']}
123 +        self.assertRaises(UnorderableGraph, ordered_nodes, graph)
124 +
125  if __name__ == "__main__":
126      unittest_main()