1 # Copyright 2018 ZTE Corporation.
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
7 # http://www.apache.org/licenses/LICENSE-2.0
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.
15 from collections import deque
16 from collections import OrderedDict
21 def __init__(self, graph_dict=None):
22 self.graph = OrderedDict()
24 for node, dep_nodes in list(graph_dict.items()):
25 self.add_node(node, dep_nodes)
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)
37 def get_pre_nodes(self, node):
38 return [k for k in self.graph if node in self.graph[k]]
42 for node in self.graph:
45 for node in self.graph:
46 for dependent in self.graph[node]:
47 degree[dependent] += 1
52 queue.appendleft(node)
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)
63 if len(sort_list) == len(self.graph):
70 for node, dependents in self.graph.items():
72 for dep in dependents:
73 dict[node].append(dep)