cmake-basis / modules Goto Github PK

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)}")