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()