diff options
author | Olly Cope <olly@ollycope.com> | 2021-05-15 15:49:12 +0000 |
---|---|---|
committer | Olly Cope <olly@ollycope.com> | 2021-05-15 15:49:12 +0000 |
commit | f08bfbd8d3ed559f41965e7aec84f79ea00ab0e0 (patch) | |
tree | 77575e1820f2a95c2e6dac388acb3a0c5e6f450d /yoyo | |
parent | 2cd1652d1a55e3cb915d224deb27bdc72d1ed89b (diff) | |
download | yoyo-f08bfbd8d3ed559f41965e7aec84f79ea00ab0e0.tar.gz |
topological sort: raise CycleError if unsorted items remain at end
Diffstat (limited to 'yoyo')
-rw-r--r-- | yoyo/topologicalsort.py | 23 |
1 files changed, 17 insertions, 6 deletions
diff --git a/yoyo/topologicalsort.py b/yoyo/topologicalsort.py index 5399765..6d4e592 100644 --- a/yoyo/topologicalsort.py +++ b/yoyo/topologicalsort.py @@ -35,12 +35,7 @@ def topological_sort( blocked_on: Dict[T, Set[T]] = defaultdict(set) while pqueue: if seen_since_last_change == len(pqueue): - for item in blocked_on: - if item not in ordering: - raise ValueError( - f"Dependency graph contains a non-existent node {item!r}" - ) - raise CycleError("Dependency graph loop detected", [n for _, n in pqueue]) + raise_cycle_error(ordering, pqueue, blocked_on) _, n = heappop(pqueue) @@ -60,3 +55,19 @@ def topological_sort( seen_since_last_change = 0 else: seen_since_last_change += 1 + + if blocked_on: + raise_cycle_error(ordering, pqueue, blocked_on) + + +def raise_cycle_error(ordering, pqueue, blocked_on): + bad = next((item for item in blocked_on if item not in ordering), None) + if bad: + raise ValueError(f"Dependency graph contains a non-existent node {bad!r}") + unresolved = {n for _, n in pqueue} + unresolved.update(*blocked_on.values()) + if unresolved: + raise CycleError( + f"Dependency graph loop detected among {unresolved!r}", + list(sorted(unresolved, key=ordering.get)), + ) |