topological_sort should throw on cycle error #1
Description
# https://github.com/cmake-basis/modules/blob/master/TopologicalSort.cmake
include(TopologicalSort.cmake)
set(target_names a b c)
# c -> b -> a -> c
set(target_dependencies_a b)
set(target_dependencies_b c)
set(target_dependencies_c a)
message("before toposort: target_names = ${target_names}")
topological_sort(target_names target_dependencies_ "")
message("after toposort: target_names = ${target_names}")output
before toposort: target_names = a;b;c
after toposort: target_names = c;b;a
ideally, the cycle error should also print the cycle
in python im using
- networkx.simple_cycles to find cycles
- networkx.topological_sort for toposort
import networkx
debug = True
scope_installs = ["a", "b", "c"]
# c -> b -> a -> c
target_depends_map = {
"a": ["b"],
"b": ["c"],
"c": ["a"],
}
# build dependency graph
depgraph = networkx.DiGraph()
depgraph_roots = set()
for target_name in scope_installs:
target_depends = target_depends_map.get(target_name, [])
for dep in target_depends:
depgraph.add_edge(dep, target_name)
# find roots of graph
depgraph_roots = []
for component in networkx.weakly_connected_components(depgraph):
subgraph = depgraph.subgraph(component)
depgraph_roots.extend([n for n,d in subgraph.in_degree() if d==0])
# check for cycles
# toposort throws exception, but does not print cycles
depgraph_cycles = list(networkx.simple_cycles(depgraph))
if depgraph_cycles:
raise Exception(f"found cycles in depgraph: {depgraph_cycles}")
targets_sorted = list(networkx.topological_sort(depgraph))
debug and print(f"targets_sorted = {' '.join(targets_sorted)}")output
Exception: found cycles in depgraph: [['a', 'c', 'b']]