genericparser/pub/utils/toscaparsers/graph.py

   1 # Copyright 2018 ZTE Corporation.
   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
  15 from collections import deque
  16 from collections import OrderedDict
  17
  18
  19 class Graph(object):
  20
  21     def __init__(self, graph_dict=None):
  22         self.graph = OrderedDict()
  23         if graph_dict:
  24             for node, dep_nodes in graph_dict.iteritems():
  25                 self.add_node(node, dep_nodes)
  26
  27     def add_node(self, node, dep_nodes):
  28         if node not in self.graph:
  29             self.graph[node] = set()
  30         if isinstance(dep_nodes, list):
  31             for dep_node in dep_nodes:
  32                 if dep_node not in self.graph:
  33                     self.graph[dep_node] = set()
  34                 if dep_node not in self.graph[node]:
  35                     self.graph[node].add(dep_node)
  36
  37     def get_pre_nodes(self, node):
  38         return [k for k in self.graph if node in self.graph[k]]
  39
  40     def topo_sort(self):
  41         degree = {}
  42         for node in self.graph:
  43             degree[node] = 0
  44
  45         for node in self.graph:
  46             for dependent in self.graph[node]:
  47                 degree[dependent] += 1
  48
  49         queue = deque()
  50         for node in degree:
  51             if degree[node] == 0:
  52                 queue.appendleft(node)
  53
  54         sort_list = []
  55         while queue:
  56             node = queue.pop()
  57             sort_list.append(node)
  58             for dependent in self.graph[node]:
  59                 degree[dependent] -= 1
  60                 if degree[dependent] == 0:
  61                     queue.appendleft(dependent)
  62
  63         if len(sort_list) == len(self.graph):
  64             return sort_list
  65         else:
  66             return None
  67
  68     def to_dict(self):
  69         dict = {}
  70         for node, dependents in self.graph.iteritems():
  71             dict[node] = []
  72             for dep in dependents:
  73                 dict[node].append(dep)
  74         return dict