= Reachability-total layering criterion
{title2=$a\leadsto b\iff\ell(a)\leq\ell(b)$}
A positive-<integer> labeling with $a\leadsto b\Rightarrow\ell(a)\leq\ell(b)$ and $a\not\leadsto b\Rightarrow\ell(a)>\ell(b)$ exists exactly when the <condensation graph> is totally ordered by reachability. Mutual paths force equal labels, and equal labels force mutual paths. Two incomparable components would require strict inequalities in both directions. Conversely number the components in <topological order>; total comparability forces every earlier component to reach every later one, proving both conditions. Compute the labeling in linear time. Reachability here includes length-zero paths.
Back to article page
