21     def __init__(self, root=None):  argument
22         self.__roots = None
24             self.__roots = {root}
25         self.__edge_map = collections.defaultdict(set)
26         self.__reverse_map = collections.defaultdict(set)
27         self.__nodes = set()
29     def add_node(self, node):  argument
33         self.__nodes.add(node)
35     def add_edge(self, source, target):  argument
41         self.__edge_map[source].add(target)
43             self.__reverse_map[target].add(source)
44         self.__nodes.add(source)
45         self.__nodes.add(target)
47     def roots(self):  argument
56         if not self.__roots:
57             self.__roots = set()
58             for n in self.__nodes:
59                 if n not in self.__reverse_map:
60                     self.__roots.add(n)
61         return self.__roots
63     def _tarjan(self):  argument
76         self.__stack = []
77         self.__scc_order = []
78         self.__index = 0
79         self.__tarjan_index = {}
80         self.__tarjan_low_link = {}
81         for v in self.__nodes:
82             self.__tarjan_index[v] = None
83         roots = sorted(self.roots(), key=node_key)
84         if self.__nodes and not roots:
85 …         raise Exception('TARJAN: No roots found in graph with {} nodes'.format(len(self.__nodes)))
88             self._tarjan_root(r)
92         for scc in self.__scc_order:
101     def _tarjan_root(self, v):  argument
104         if self.__tarjan_index.get(v) is not None:
107         self.__tarjan_index[v] = self.__tarjan_low_link[v] = self.__index
108         self.__index += 1
109         self.__stack.append(v)
111         for target in sorted(self.__edge_map[source], key=node_key):
112             if self.__tarjan_index[target] is None:
113                 self._tarjan_root(target)
114 …         self.__tarjan_low_link[v] = min(self.__tarjan_low_link[v], self.__tarjan_low_link[target])
115             elif target in self.__stack:
116 …         self.__tarjan_low_link[v] = min(self.__tarjan_low_link[v], self.__tarjan_low_link[target])
118         if self.__tarjan_low_link[v] == self.__tarjan_index[v]:
121                 scc.append(self.__stack.pop())
124             self.__scc_order.append(scc)
126     def scc_order(self):  argument
136         if not self.__scc_order:
137             self._tarjan()
138         return self.__scc_order
141     def depends_on(self, node):  argument
143         return sorted(self.__edge_map[node], key=node_key)
145     def required_by(self, node):  argument
147         return sorted(self.__reverse_map[node], key=node_key)