Directed Acyclic Graph (DAG) — How the Cycle Check Works

A directed graph stores one-way edges: a -> b means you can go from a to b, but not necessarily back. In the adjacency list each edge is stored once, on the source vertex's out-list:

a -> b
b -> c

adjList:
  a: [b]
  b: [c]
  c: []

(Contrast with the undirected Graph, where a -> b is stored twice — in both a's and b's lists — which is why its Size() divides by two and the directed Size() does not.)

A DAG adds one rule: no cycles. You can never follow the arrows and end up back where you started. a -> b -> c -> a is forbidden.

1. Where the invariant is enforced

There is exactly one guard, inside AddVertex(from, to):

// from -> to closes a cycle iff "to" can already reach "from".
if gp.hasPath(to, from) {
    return false
}

The reasoning is short but important:

The graph is acyclic before every AddVertex call — it starts empty, and this guard has held every previous time. Given that, the only way the new edge from -> to can create a cycle is if a path to -> ... -> from already exists. The new edge would close that path into a loop.

So the question "would this edge create a cycle?" reduces to "can to already reach from?" — and that is a reachability query, answered by DFS.

Note the argument order: hasPath(to, from), not hasPath(from, to). You search forward from to trying to arrive back at from.

2. What DFS actually does

hasPath just seeds a fresh visited set and calls dfs:

func (gp *DAG[T]) dfs(current, dst T, visited map[T]bool) bool {
    if current == dst {          // (1) standing on the target -> found it
        return true
    }
    visited[current] = true       // (2) never revisit this vertex

    for _, next := range gp.adjList[current] {   // (3) each out-neighbor
        if !visited[next] && gp.dfs(next, dst, visited) {  // (4) ask the same question of it
            return true
        }
    }
    return false                  // (5) exhausted every path -> unreachable
}

The mental model: dfs does not know the answer itself. It asks "can I, current, reach dst?" by delegating the same question to each of its out-neighbors. If any neighbor can reach dst, then so can current, and the true bubbles straight up the call stack.

(1) is the only place true is born.
(2) the visited set guarantees termination. If the data ever did contain a cycle, without it the recursion would loop forever.
(4) short-circuits: the first neighbor that succeeds ends the search.
(5) if every branch dead-ends, there is no path.

3. Trace: rejecting a cycle

Graph is a -> b, b -> c. Someone calls AddVertex("c", "a"), which fires hasPath("a", "c") → dfs("a", "c", {}):

Call	`current`	`current == dst`?	neighbors	action
1	`a`	`a == c`? no	`[b]`	mark `a`, recurse into `b`
2	`b`	`b == c`? no	`[c]`	mark `b`, recurse into `c`
3	`c`	`c == c`? yes	—	return `true`

The true returns up through calls 2 and 1. hasPath is true, so c -> a is rejected — a could already reach c, so the edge would close a loop.

4. Trace: allowing an edge

Graph is just a -> b. Someone calls AddVertex("a", "c") → hasPath("c", "a") → dfs("c", "a", {}):

Call	`current`	`current == dst`?	neighbors	action
1	`c`	`c == a`? no	`[]`	mark `c`, loop body never runs
—				fall through → return `false`

No path → the edge a -> c is safe and gets appended.

5. Cost

Each AddVertex runs one DFS: O(V + E) time, O(V) space for visited. The self-loop case (from == to) is handled by a cheap equality check up front, before any DFS runs.

4.1 KiB Raw Permalink Blame History