Graph Algorithms Reconstructed

10.1 Traversal, order and components

Breadth-first search from $s$ visits vertices in order of hop distance and computes $\mathrm{dist}(s, \cdot)$ in $\Theta(n + m)$; depth-first search visits each vertex and edge once and classifies edges by discovery and finishing times. Both are textbook algorithms [Cormen et al. 2022]. Three classical consequences:

• Topological sorting. A DAG’s vertices can be ordered so that every edge goes forward; Kahn’s algorithm repeatedly removes a vertex of in-degree zero, in $\Theta(n + m)$, and reports a cycle if it gets stuck [Kahn 1962].
• Strongly connected components. Tarjan’s algorithm [Tarjan 1972] finds them in one DFS using low-link values, and numbers them in reverse topological order of the condensation (the SDK’s tarjan_scc returns that numbering, so component $0$ is a sink).
• Reachability and closure. The reflexive–transitive closure — the semantics $\sem{E^*}$ of Chapter 6 — can be computed by condensing SCCs and OR-ing bitset rows in reverse topological order: each OR of $n$-bit rows costs $\lceil n / w \rceil$ word operations.

from cgtsdk import Cost
from cgtsdk.algorithms import bfs, tarjan_scc, topological_sort, transitive_closure
from cgtsdk.lab import random_digraph

for name, adj in (("random DAG", random_digraph(2000, 2.0, seed=1, dag=True)),
                  ("random digraph", random_digraph(2000, 2.0, seed=1))):
    c1, c2, c3 = Cost(), Cost(), Cost()
    d = bfs(adj, 0, c1)
    comp, k = tarjan_scc(adj, c2)
    order = topological_sort(adj)
    rows = transitive_closure(adj, c3)
    pairs = sum(bin(r).count("1") for r in rows)
    print(f"{name:15s} m={sum(map(len, adj))}  BFS edges={c1.counts['edge']}  SCCs={k}  "
          f"topological order: {'yes' if order else 'no (cycle)'}  closure pairs={pairs}  closure cost={c3.total}")

random DAG      m=4000  BFS edges=20  SCCs=2000  topological order: yes  closure pairs=26226  closure cost=136000
random digraph  m=4000  BFS edges=3240  SCCs=718  topological order: no (cycle)  closure pairs=2575275  closure cost=39584

On the random digraph a giant strongly connected component absorbs 1,283 of the 2,000 vertices; condensing it shares one closure row among all its members, which is why the closure of a graph with more reachable pairs costs fewer steps. This is the sharing mechanism (M-SHARE) at work inside a classical algorithm.

10.2 Shortest paths and spanning trees

All are implemented in cgtsdk.algorithms and tested against one another and against brute force: Dijkstra and Bellman–Ford against Floyd–Warshall on random weighted digraphs, Kruskal against Prim and against exhaustive search over edge subsets on small graphs.

In the path-algebra view of Chapter 6 all three shortest-path algorithms evaluate the same path grammar $E E^*$ in the tropical semiring $(\min, +)$; they differ in evaluation strategy. Dijkstra exploits a property of the algebra on non-negative weights — once a vertex is settled its distance never improves — to evaluate each vertex once in increasing order of distance. Bellman–Ford makes no such assumption and relaxes every edge up to $n - 1$ times. Floyd–Warshall is Kleene’s algorithm for the closure of a matrix: it allows intermediate vertices $0, 1, \dots, k$ in turn. The grammar is common; the costs come from the semantics’ algebraic properties and the evaluation order. A grammatical description, by itself, does not choose the order.

10.3 Evaluating a path grammar

We now make that last sentence precise. The closure $P^+ = \sem{E E^*}$ (paths of length at least one) is the least relation $P$ satisfying either of two grammars:

Both have the same meaning (Chapter 6). Evaluate each bottom-up: start from the facts $E(u,v)$, and repeatedly apply the productions to newly derived facts until nothing new appears (semi-naive evaluation, standard in Datalog).

Part 1 says something exact and somewhat deflating: evaluating the path grammar is computing the closure, with the work of one reverse search per target. The recursive description of paths, however elegant, does no less work than the classical algorithm. Parts 2 and 3 show that the shape of a grammar is a real cost parameter: the doubling grammar does asymptotically more work on long paths but needs exponentially fewer rounds — the trade between total work and parallel depth behind computing transitive closure by repeated squaring. This is well known in Datalog practice (linear versus non-linear recursion); the exact count in part 1 is, as far as this research has found, a convenient statement rather than a new result.

The SDK checks part 1 exactly on every test graph. The experiment of the ledger measured the doubling grammar on directed paths (CGT-EXP-007): its rule applications grew by a factor of about $8$ each time $n$ doubled (cubic), while the right-linear grammar’s grew by $4$ (quadratic).

from cgtsdk import Cost
from cgtsdk.algorithms import path_grammar_closure

for n in (32, 64, 128):
    path = [[i + 1] if i + 1 < n else [] for i in range(n)]
    lin, dbl = Cost(), Cost()
    P1 = path_grammar_closure(path, "linear", lin)
    P2 = path_grammar_closure(path, "doubling", dbl)
    assert P1 == P2
    pairs = sum(map(len, P1))
    formula = (n - 1) + sum(len(P1[w]) * (1 if w > 0 else 0) for w in range(n))
    print(f"n={n:4d} |P+|={pairs:5d}  right-linear rules={lin.counts['rule']:6d} (formula {formula})  doubling rules={dbl.counts['rule']:8d}")

n=  32 |P+|=  496  right-linear rules=   496 (formula 496)  doubling rules=    9516
n=  64 |P+|= 2016  right-linear rules=  2016 (formula 2016)  doubling rules=   81500
n= 128 |P+|= 8128  right-linear rules=  8128 (formula 8128)  doubling rules=  675004

(On a directed path every vertex except the first has in-degree $1$, so the formula reduces to $m + \sum_{w > 0} |P(w)| = |P^+|$.)

10.4 The mapping, algorithm by algorithm

The verdict for graph algorithms is again equivalence: each classical algorithm is an evaluation strategy for a path grammar in some algebra, and the grammar alone does not supply the strategy. The grammatical view earns its keep by making the shared structure explicit — which is what made the product construction of Chapter 8 and the constrained random surfer of Chapter 16 straightforward to derive.

Report an erratum or an unclear passage in this chapter