(G)
| 258 | |
| 259 | |
| 260 | def topological_generations(G): |
| 261 | if not G.is_directed(): |
| 262 | raise AssertionError("Topological sort not defined on undirected graphs.") |
| 263 | indegree_map = {v: d for v, d in G.in_degree() if d > 0} |
| 264 | zero_indegree = [v for v, d in G.in_degree() if d == 0] |
| 265 | while zero_indegree: |
| 266 | this_generation = zero_indegree |
| 267 | zero_indegree = [] |
| 268 | for node in this_generation: |
| 269 | if node not in G: |
| 270 | raise RuntimeError("Graph changed during iteration") |
| 271 | for child in G.neighbors(node): |
| 272 | try: |
| 273 | indegree_map[child] -= 1 |
| 274 | except KeyError as err: |
| 275 | raise RuntimeError("Graph changed during iteration") from err |
| 276 | if indegree_map[child] == 0: |
| 277 | zero_indegree.append(child) |
| 278 | del indegree_map[child] |
| 279 | yield this_generation |
| 280 | |
| 281 | if indegree_map: |
| 282 | raise AssertionError("Graph contains a cycle or graph changed during iteration") |
| 283 | |
| 284 | |
| 285 | def topological_sort(G): |
nothing calls this directly
no test coverage detected