Perform Khan's simple topological sort algorithm from '62. See https://en.wikipedia.org/wiki/Topological_sorting
(self)
| 106 | return (obj for obj, adj in self.items() if adj) |
| 107 | |
| 108 | def _khan62(self): |
| 109 | """Perform Khan's simple topological sort algorithm from '62. |
| 110 | |
| 111 | See https://en.wikipedia.org/wiki/Topological_sorting |
| 112 | """ |
| 113 | count = Counter() |
| 114 | result = [] |
| 115 | |
| 116 | for node in self: |
| 117 | for successor in self[node]: |
| 118 | count[successor] += 1 |
| 119 | ready = [node for node in self if not count[node]] |
| 120 | |
| 121 | while ready: |
| 122 | node = ready.pop() |
| 123 | result.append(node) |
| 124 | |
| 125 | for successor in self[node]: |
| 126 | count[successor] -= 1 |
| 127 | if count[successor] == 0: |
| 128 | ready.append(successor) |
| 129 | result.reverse() |
| 130 | return result |
| 131 | |
| 132 | def _tarjan72(self): |
| 133 | """Perform Tarjan's algorithm to find strongly connected components. |