Original file line numberDiff line numberDiff line change@@ -49,54 +49,6 @@ def dfs(v: str) -> Iterator[set[str]]:
4949yieldfromdfs(v)
5050515152-deftopsort(
53-data: dict[Set[str], set[Set[str]]]
54-) ->Iterable[Set[Set[str]]]:
55-"""Topological sort.
56-57- Args:
58- data: A map from SCCs (represented as frozen sets of strings) to
59- sets of SCCs, its dependencies. NOTE: This data structure
60- is modified in place -- for normalization purposes,
61- self-dependencies are removed and entries representing
62- orphans are added.
63-64- Returns:
65- An iterator yielding sets of SCCs that have an equivalent
66- ordering. NOTE: The algorithm doesn't care about the internal
67- structure of SCCs.
68-69- Example:
70- Suppose the input has the following structure:
71-72- {A: {B, C}, B: {D}, C: {D}}
73-74- This is normalized to:
75-76- {A: {B, C}, B: {D}, C: {D}, D: {}}
77-78- The algorithm will yield the following values:
79-80- {D}
81- {B, C}
82- {A}
83-84- From https://code.activestate.com/recipes/577413-topological-sort/history/1/.
85- """
86-# TODO: Use a faster algorithm?
87-fork, vindata.items():
88-v.discard(k) # Ignore self dependencies.
89-foriteminset.union(*data.values()) -set(data.keys()):
90-data[item] =set()
91-whileTrue:
92-ready= {itemforitem, depindata.items() ifnotdep}
93-ifnotready:
94-break
95-yieldready
96-data= {item: (dep-ready) foritem, depindata.items() ifitemnotinready}
97-assertnotdata, f"A cyclic dependency exists amongst {data}"
98-99-10052deffind_cycles_in_scc(
10153graph: dict[str, Set[str]], scc: Set[str], start: str
10254) ->Iterable[list[str]]: