Skip to content

Cycle detection / fixed point [mp]

Micro pattern

Description

Detect repeated states or an exhausted dependency process to classify termination and prevent infinite traversal.

Problems

Fast and slow pointers

Advance pointers at different speeds to detect a cycle in a next-pointer structure.

Remember generated states

Stop when a generated state repeats or reaches a terminal state.

Topological exhaustion

Detect cycles when dependency processing cannot reach every required vertex.