CYCLE DETECTION is there a loop? — an edge that reconnects what is already connected
A cycle is a path that returns to where it started — and detecting one is a basic safety check: a cycle in a dependency graph is a deadlock, in a family tree an impossibility, in a filesystem an infinite loop. In an undirected graph, union-find spots it instantly: process edges one by one, and if an edge’s two endpoints are already in the same set, that edge closes a cycle. (In directed graphs, a back-edge during DFS does the same job.) A tree — connected with no cycle — has exactly n−1 edges; one more edge anywhere makes a loop. Here the 5-node graph with a 4-cycle is caught; a tree is not.
THE TECHNIQUE an edge joining two already-connected nodes closes a cycle (union-find)
The demo detects a cycle in a graph with a loop (an edge reconnecting a set) and finds none in a tree: live demo
HISTORY & CREDIT cycle detection · union-find / DFS back-edge
“Finding a cycle means searching all paths.” — one edge that reconnects an already-connected pair is a cycle; union-find catches it in a pass. cited
the test · process edges; if an edge’s endpoints share a root, it closes a cycle — union-find. the directed case · a DFS back-edge (to an ancestor still on the stack) is the same signal. the count · a tree has exactly n−1 edges; any extra edge makes a loop.
A loop revealed by an edge that reconnects what is already joined — cycles caught in one pass. recognizer
RECOMMEND FOR I-13 the loop check, on the compiler
On the canonical compiler, a graph with a 4-cycle is flagged (a reconnecting edge); a tree is not:
$ i13 run nw_cycledetection.i13 # edge into an existing set = cycle
RUN OK · 679 step(s) · peak stack 12 · call depth 6
cyc = 1 -- the cyclic graph
tree = 0 -- the tree (no cycle)
has_cycle = 1
Recommend as a NULL — a recognizer. Cycle detection tests whether a graph contains a loop (a validity predicate, B41) using union-find (B40); a keeper GENERATES an invariant rather than checking a property. Its answer is forall-pinned by the graph (B39). NULL — the deadlock detector, in one pass.