5923ab5373ccdf8292d1dab992571bea0d05297a
[ta/config-manager.git] / cmtopologicalsort.py
1 # Copyright 2019 Nokia
2
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
6 #
7 #     http://www.apache.org/licenses/LICENSE-2.0
8 #
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
14 from __future__ import print_function
15 from cmframework.apis import cmerror
16
17
18 class TopSort(object):
19     """
20     This class implements a topological sort algorithm.
21
22     It expects a dependency graph as an input and returns a sorted list as an
23     output. The returned list contains lists sorted accordingly to the dependency
24     graph:
25
26     Usage Example:
27         # The following graph indicates that 2 depends on 11, 9 depends on 11,8,10 and so on...
28         graph = {2: [11],
29                  9: [11, 8, 10],
30                 10: [11, 3],
31                 11: [7, 5],
32                 8: [7, 3]}
33
34         sort = TopSort(graph)
35         try:
36             sorted = sort.sort()
37             for entry in sorted:
38                 print('%r' % entry)
39         except cmerror.CMError as exp:
40            print('Got exception %s' % str(exp))
41
42     The above example will generate the following output:
43     [3, 5, 7]
44     [8, 11]
45     [2, 10]
46     [9]
47     """
48
49     def __init__(self, graph):
50         self.graph = graph
51         self.output = {}
52         self.recursionlevel = 0
53
54     def _get_dependent_entries(self, entry):
55         result = []
56         for e, deps in self.graph.iteritems():
57             if entry in deps:
58                 result.append(e)
59         return result
60
61     def _update_dependent_entries(self, entry):
62         maximumrecursion = (len(self.graph)) * (len(self.graph))
63         if (self.recursionlevel + 1) >= maximumrecursion:
64             raise cmerror.CMError('cyclic dependency detected, graph %r' % self.graph)
65         self.recursionlevel += 1
66         dependententries = self._get_dependent_entries(entry)
67         entrydepth = self.output[entry]
68         for e in dependententries:
69             if e in self.output:
70                 if entrydepth >= self.output[e]:
71                     self.output[e] = entrydepth + 1
72                     self._update_dependent_entries(e)
73
74     def sort(self):
75         for entry, deps in self.graph.iteritems():
76             depth = 0
77             if entry in self.output:
78                 depth = self.output[entry]
79
80             # calculate new depth according to dependencies
81             newdepth = depth
82             for dep in deps:
83                 if dep in self.output:
84                     weight = self.output[dep]
85                 else:
86                     weight = 0
87                     self.output[dep] = 0
88                 if weight >= newdepth:
89                     newdepth = weight + 1
90
91             # if our depth is changed we need to update the entries depending on us
92             self.output[entry] = newdepth
93             if newdepth > depth and entry in self.output:
94                 self.recursionlevel = 0
95                 self._update_dependent_entries(entry)
96
97         return self._getsorted()
98
99     def _getsorted(self):
100         import operator
101         sortedoutput = sorted(self.output.items(), key=operator.itemgetter(1))
102         result = {}
103         for entry in sortedoutput:
104             if entry[1] not in result:
105                 result[entry[1]] = []
106             result[entry[1]].append(entry[0])
107
108         returned = []
109         for entry, data in result.iteritems():
110             returned.append(data)
111
112         return returned
113
114
115 def main():
116     graph1 = {2: [11],
117               9: [11, 8, 10],
118               10: [11, 3],
119               11: [7, 5],
120               8: [7, 3]}
121
122     graph2 = {'playbook2.yaml': [], 'playbook1.yaml': ['playbook2.yaml']}
123
124     topsort1 = TopSort(graph1)
125     topsort2 = TopSort(graph2)
126
127     try:
128         print(graph1)
129         sortedlists1 = topsort1.sort()
130         for entry in sortedlists1:
131             print('%r' % entry)
132
133         print(graph2)
134         sortedlists2 = topsort2.sort()
135         for entry in sortedlists2:
136             print('%r' % entry)
137     except cmerror.CMError as exp:
138         print(str(exp))
139
140
141 if __name__ == '__main__':
142     main()