Build a Dependency ResolverStep 5 of 5

Detect circular dependencies

12345

Step 5: Detect circular dependencies

Real build systems fail loudly on a circular dependency: package A needs B, B needs A, and no valid install order exists. We can detect this for free using the sort we just built.

Key insight: Kahn's algorithm can only place a node once its in-degree reaches 0. If the graph contains a cycle, the nodes in that cycle keep one another blocked, so they never become ready. That means topological_sort() returns fewer nodes than the graph has exactly when a cycle exists.

Implement has_cycle() returning True if the graph has a directed cycle, otherwise False.

acyclic:  a -> b -> c              has_cycle() -> False
cycle:    a -> b -> c -> a         has_cycle() -> True

This is only a couple of lines on top of topological_sort, no new traversal needed.

Hints
Starter code
from collections import deque


class Graph:
    def __init__(self):
        self.adj = {}

    def add_edge(self, u, v):
        if u not in self.adj:
            self.adj[u] = []
        if v not in self.adj:
            self.adj[v] = []
        self.adj[u].append(v)

    def nodes(self):
        return list(self.adj.keys())

    def neighbors(self, u):
        return self.adj.get(u, [])

    def bfs(self, start):
        seen = {start}
        queue = deque([start])
        order = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for nb in self.adj.get(node, []):
                if nb not in seen:
                    seen.add(nb)
                    queue.append(nb)
        return order

    def dfs(self, start):
        order = []
        seen = set()

        def visit(node):
            if node in seen:
                return
            seen.add(node)
            order.append(node)
            for nb in self.adj.get(node, []):
                visit(nb)

        visit(start)
        return order

    def topological_sort(self):
        indeg = {n: 0 for n in self.adj}
        for u in self.adj:
            for v in self.adj[u]:
                indeg[v] += 1
        order_index = {n: i for i, n in enumerate(self.adj)}
        available = [n for n in self.adj if indeg[n] == 0]
        result = []
        while available:
            available.sort(key=lambda n: order_index[n])
            node = available.pop(0)
            result.append(node)
            for v in self.adj[node]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    available.append(v)
        return result

    def has_cycle(self):
        """Return True if the graph contains a directed cycle.

        A cycle exists exactly when topological_sort() cannot place every node.
        """
        # TODO: compare the length of topological_sort() with the number of
        # nodes. Fewer placed nodes means a cycle. Return a bool.
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousAll challenges