# 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)`:

```go
// 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`:

```go
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.