Chapter 6. Graphs

Reachability, distance, and layering as LLP fixed-points on vertex vectors.

This page: LLP forms. View classical forms »

Setting

A directed graph $G = (V, E)$ has $n$ vertices $v_0, v_1, \ldots, v_{n-1}$ and $m$ edges. Each edge $(i, j) \in E$ goes from $i$ to $j$. The neighbors of a vertex $j$ split into its predecessors $\text{pre}(j) = \{ i \mid (i, j) \in E \}$ and its successors $\text{succ}(j) = \{ k \mid (j, k) \in E \}$. The book covers two storage formats: the $n \times n$ adjacency matrix (constant-time edge lookup, $O(n^2)$ space) and the adjacency list (one linked list of neighbors per vertex, $O(n + m)$ space, sparse-friendly). The demos below use the predecessor-list view because the LLP forbidden conditions are naturally stated over predecessors.

The LLP perspective

The graph problems above all admit the same "forbidden / advance" template introduced in Chapter 2. We pick a state vector $G$, write a predicate $B(G)$ describing feasibility, identify the indices that block $B$, and advance them. Three concrete instances:

• Reachability. $G[j] \in \{0, 1\}$ with $G[0] = 1$. Forbidden: some $i \in \text{pre}(j)$ has $G[i] = 1$ but $G[j] = 0$. Advance: $G[j] := 1$.
• BFS distance. $G[j] \in \mathbb{N} \cup \{\infty\}$ with $G[0] = 0$. Forbidden: $G[j] > G[i] + 1$ for some $i \in \text{pre}(j)$. Advance: $G[j] := \min_{i \in \text{pre}(j)} G[i] + 1$.
• DAG layering. $G[j] \in \mathbb{N}$, with a side flag $\text{fixed}[j]$. Forbidden: $\neg\text{fixed}[j] \wedge (\forall i \in \text{pre}(j): \text{fixed}[i])$. Advance: $G[j] := 1 + \max_{i \in \text{pre}(j)} G[i]$; $\text{fixed}[j] := \text{true}$.

All three lattices are finite distributive, so the LLP main loop converges to the unique least fixed point regardless of the order in which forbidden indices are picked. Choosing a priority on $G[j]$ (smallest distance first) recovers the classical BFS schedule; choosing sources first recovers the classical layering algorithm.

LLP-BFS

$G[j]$ is the current upper bound on the BFS distance from $v_0$ to $v_j$. The vector starts at $G = (0, \infty, \infty, \ldots)$. An index $j$ is forbidden when some predecessor $i$ satisfies $G[i] + 1 < G[j]$; the advance rule lowers $G[j]$ to $\min_{i \in \text{pre}(j)} G[i] + 1$. The fixed point is the BFS distance vector.

Time complexity: $O(n + m)$, where $n$ is the number of vertices and $m$ is the number of edges.

LLP-Layering

$G[j]$ is the current layer of vertex $j$ and $\text{fixed}[j]$ records whether the layer has been finalized. Initially $G[j] = 0$ for every $j$, $\text{fixed}[j] = \text{true}$ for sources, and $\text{fixed}[j] = \text{false}$ otherwise. An index $j$ is forbidden when it is not yet fixed but all of its predecessors are; the advance rule sets $G[j] := 1 + \max_{i \in \text{pre}(j)} G[i]$ and marks $j$ fixed. The default input is the DAG of the book's worked example (vertices $v_0, \ldots, v_5$ with $v_0, v_1$ as sources and longest path $v_0 \to v_3 \to v_4 \to v_5$).

Time complexity: $O(n + m)$, where $n$ is the number of vertices and $m$ is the number of edges.

LLP-Traversal

Reachability as a 1-bit lattice: $G[j] = 1$ iff vertex $j$ is reachable from the source. Forbidden: some predecessor is reached but $j$ is not. Advance: mark $j$ reached.

Time complexity: $O(n + m)$, where $n$ is the number of vertices and $m$ is the number of edges.

void LLPTraversal(set<int>[] pre, boolean[] G) {
  forbidden (j) : !G[j] && (exists i in pre[j] : G[i])  =>
    advance : G[j] = true;
}

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.