DevOps NetworkDevOpsNetwork
Join Free
Build it yourself

Dependency resolver with cycle detection

mediumConfig and dependencies

Problem statement

Given packages (or Terraform modules, Helm charts, services in a startup sequence) and what each one depends on, produce an order in which to install them so every package comes after all of its dependencies. If that is impossible because of a dependency cycle, say exactly which cycle.

API (Java: DependencyResolver.resolve(Map<String, List<String>> graph) and resolve(graph, List<String> targets), throwing CycleException)

◈ DIAGRAM
class CycleError(Exception)
resolve(graph: dict[str, list[str]], targets: list[str] | None = None) -> list[str]

graph[p] lists the packages p depends on.

Rules

  • Every package appears after all of its dependencies.
  • The output must be deterministic: whenever several packages are ready at once, take the alphabetically smallest first.
  • A dependency that is not a key of graph is a leaf package with no dependencies of its own. It is still part of the output.
  • With targets, output only the targets and everything they need, directly or indirectly.
  • If there is a cycle, raise CycleError with the message cycle: a -> b -> c -> a. To make the message deterministic, start from the alphabetically smallest package that cannot be installed and, at each step, follow its alphabetically smallest dependency that also cannot be installed, until a package repeats.
  • Duplicate entries in a dependency list are ignored.

Examples

Example 1

Input: graph = { "app": ["db-client", "logger"], "db-client": ["tls", "logger"], "logger": [], "metrics": ["logger"], "tls": [] } resolve(graph) resolve(graph, targets=["db-client"])

Output: [logger, metrics, tls, db-client, app] [logger, tls, db-client]

Explanation: logger and tls are ready first, and logger wins alphabetically. Installing it makes metrics ready, which sorts before tls. With a target, app and metrics are not needed.

Example 2

Input: resolve({"a": ["b"], "b": ["c"], "c": ["a"], "d": []}) resolve({"x": ["x"]}) resolve({"web": ["nginx-conf"]})

Output: error: cycle: a -> b -> c -> a error: cycle: x -> x [nginx-conf, web]

Explanation: A package depending on itself is a cycle of length one. nginx-conf is not a key, so it is a leaf.

Hints

Approach

Kahn's algorithm with a min-heap:

  1. Work out the node set: every package mentioned, or, with targets, everything reachable from the targets by a DFS over dependencies.
  2. For each package keep pending, its set of uninstalled dependencies, and build the reverse map dependents: d -> packages that need d.
  3. Put every package with an empty pending set into a min-heap. Pop the smallest, append it to the order, and remove it from each dependent's pending set, pushing any dependent whose set becomes empty.
  4. If fewer packages were output than exist, the remainder contains a cycle. Every remaining package still has a remaining dependency, so start at the smallest one and keep following its smallest remaining dependency. Because the set is finite, a package must repeat, and the path from its first visit is the cycle.

Using sets for pending handles duplicate entries in a dependency list for free.

ComplexityTime O((V + E) log V)Space O(V + E)
Python
import heapq
class CycleError(Exception):
pass
def _closure(graph, targets):
"""Every package reachable from targets (or every package mentioned, if targets is None)."""
if targets is None:
nodes = set(graph)
for deps in graph.values():
nodes.update(deps)
return nodes
nodes, stack = set(), list(targets)
while stack:
n = stack.pop()
if n not in nodes:
nodes.add(n)
stack.extend(graph.get(n, []))
return nodes
def _find_cycle(graph, remaining):
"""Every node left over has an unresolved dependency, so following one must loop."""
path, pos = [], {}
cur = min(remaining)
while cur not in pos:
pos[cur] = len(path)
path.append(cur)
cur = min(d for d in graph.get(cur, []) if d in remaining)
return path[pos[cur]:] + [cur]
def resolve(graph, targets=None):
nodes = _closure(graph, targets)
pending = {n: set(graph.get(n, [])) for n in nodes} # unresolved deps per package
dependents = {n: [] for n in nodes}
for n, deps in pending.items():
for d in deps:
dependents[d].append(n)
ready = [n for n, deps in pending.items() if not deps]
heapq.heapify(ready) # alphabetical tie-break
order = []
while ready:
n = heapq.heappop(ready)
order.append(n)
for m in dependents[n]:
pending[m].discard(n)
if not pending[m]:
heapq.heappush(ready, m)
if len(order) < len(nodes):
cycle = _find_cycle(graph, nodes - set(order))
raise CycleError("cycle: " + " -> ".join(cycle))
return order

Follow-up questions

  • Return install "waves": groups of packages that can install in parallel.
  • One package fails to install. Which others must be skipped?
  • Add version constraints (tls>=1.2). Why does that make the problem much harder?

Frequently asked questions

Both give a valid topological order in O(V + E). A DFS post-order is shorter to write and finds the cycle path naturally from its recursion stack. Kahn's algorithm makes the "what is ready now?" set explicit, which is exactly what you need for deterministic tie-breaking, and for running independent packages in parallel: everything in the ready set at the same moment can install concurrently.

In Go: map[string][]string in, maps for pending counts and dependents, and container/heap over a []string for the ready set. Return an error wrapping the cycle path instead of panicking. Production resolvers (package managers, Terraform's graph walker, build systems) also run the ready set in parallel with a worker limit, stop scheduling dependents of a node that failed, and report every cycle found, not only the first.

Dependency ordering is everywhere in their tooling: Terraform resources, Helm subcharts, Ansible roles, service startup order, CI pipelines as DAGs. The question checks that you recognise topological sort and can give a useful error when the graph is broken.