Acid
118 lines
4.1 KiB
Markdown
118 lines
4.1 KiB
Markdown
# 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.
|