TAOCP 7.1.4 Exercise 233
Let $G=(V,E)$ be a directed graph whose edges are linearly ordered as $E={e_1,\dots,e_m}$.
Section 7.1.4: Binary Decision Diagrams
Exercise 233. ▶ [25] [25] Design an algorithm that builds a ZDD for the family of all oriented cycles of a given digraph. (See exercise 226.)
Verified: no
Solve time: 2m22s
Solution
Let $G=(V,E)$ be a directed graph whose edges are linearly ordered as $E={e_1,\dots,e_m}$. A family of oriented cycles is the set of all subsets $C\subseteq E$ such that the subgraph $(V,C)$ consists of exactly one directed simple cycle, and every vertex has indegree and outdegree at most $1$, with equality $1$ precisely on vertices lying on the cycle.
A zero-suppressed decision diagram is built by recursive branching on whether each edge $e_k$ is included in the set or not. Each node of the construction corresponds to a pair consisting of a stage index $k$ and a state describing all partial constraints induced by decisions on ${e_1,\dots,e_{k-1}}$.
A state must encode three kinds of information. First, for every vertex $v\in V$, the pair $(\deg^+_C(v),\deg^-_C(v))\in{0,1}^2$ must be maintained, since any violation of degree constraints permanently invalidates all extensions. Second, the partial structure formed by edges already chosen induces a collection of directed paths; endpoints of these paths must be connected consistently when new edges are added. Third, the number of completed directed cycles formed so far must be tracked, denoted by $\kappa\in{0,1}$, since more than one cycle is forbidden.
To represent connectivity among partial paths, each vertex with $(\deg^+,\deg^-)=(1,0)$ is a tail and each vertex with $(0,1)$ is a head. We maintain an equivalence relation on currently active endpoints generated by the chosen edges, represented by a disjoint-set structure over endpoints. A component in this structure is either a directed path (with exactly one head and one tail) or a completed cycle (no exposed endpoints). Once a component becomes a cycle, it is removed from the endpoint structure and increments $\kappa$ by $1$.
The ZDD is constructed by a memoized recursion $\mathcal{Z}(k,S)$, where $S$ denotes the current state. The recursion returns a node representing all completions using edges ${e_k,\dots,e_m}$ consistent with $S$.
At step $k$, two transitions are defined.
The first transition excludes $e_k$, producing state $S_0$ identical to $S$ except that no updates are made.
The second transition includes $e_k=(u,v)$. This is permitted only if $\deg^+_C(u)=0$ and $\deg^-_C(v)=0$. In the updated state $S_1$, we set $\deg^+_C(u)\leftarrow 1$ and $\deg^-_C(v)\leftarrow 1$, and we merge connectivity endpoints according to the roles of $u$ and $v$. If both $u$ and $v$ are already endpoints in the same connected component, then adding $e_k$ closes a directed cycle inside that component; in this case the component is removed from the endpoint structure and $\kappa\leftarrow \kappa+1$. If this produces $\kappa>1$, the transition is rejected.
The recursion is then
$$ \mathcal{Z}(k,S)=\mathrm{NODE}\bigl(k,\mathcal{Z}(k+1,S_0),\mathcal{Z}(k+1,S_1)\bigr), $$
with zero-suppressed reduction applied, meaning that if the inclusion branch equals the exclusion branch, the node is replaced by the common child, and terminal nodes are $\top$ and $\bot$.
Terminal acceptance occurs at $k=m+1$. The state $S$ is accepted if and only if $\kappa=1$ and there are no open endpoints, meaning every vertex has either $(0,0)$ or lies in the unique completed cycle. Otherwise the terminal is $\bot$.
The root of the ZDD is $\mathcal{Z}(1,S_\emptyset)$, where all degrees are zero, no endpoints are connected, and $\kappa=0$.
Correctness follows from the invariant that every partial selection of edges consistent with a state $S$ corresponds exactly to a set of vertex-disjoint directed paths together with at most one completed cycle, and every transition preserves this characterization. Every valid oriented cycle of $G$ is generated by a unique sequence of edge decisions because the fixed ordering of edges prevents ambiguity in construction. Conversely, every accepting terminal state corresponds to exactly one directed simple cycle since $\kappa=1$ excludes multiple cycles and absence of endpoints excludes path components.
This completes the proof. ∎