Perform Tarjan's algorithm to find strongly connected components. See Also: :wikipedia:`Tarjan%27s_strongly_connected_components_algorithm`
(self)
| 130 | return result |
| 131 | |
| 132 | def _tarjan72(self): |
| 133 | """Perform Tarjan's algorithm to find strongly connected components. |
| 134 | |
| 135 | See Also: |
| 136 | :wikipedia:`Tarjan%27s_strongly_connected_components_algorithm` |
| 137 | """ |
| 138 | result, stack, low = [], [], {} |
| 139 | |
| 140 | def visit(node): |
| 141 | if node in low: |
| 142 | return |
| 143 | num = len(low) |
| 144 | low[node] = num |
| 145 | stack_pos = len(stack) |
| 146 | stack.append(node) |
| 147 | |
| 148 | for successor in self[node]: |
| 149 | visit(successor) |
| 150 | low[node] = min(low[node], low[successor]) |
| 151 | |
| 152 | if num == low[node]: |
| 153 | component = tuple(stack[stack_pos:]) |
| 154 | stack[stack_pos:] = [] |
| 155 | result.append(component) |
| 156 | for item in component: |
| 157 | low[item] = len(self) |
| 158 | |
| 159 | for node in self: |
| 160 | visit(node) |
| 161 | |
| 162 | return result |
| 163 | |
| 164 | def to_dot(self, fh, formatter=None): |
| 165 | """Convert the graph to DOT format. |