Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Adjacency — where it appears

Which vertices a graph joins to which, and the choice of how to store it decides both the space and the cost of asking what a vertex touches. How it is stored decides both the space and the cost of asking what a vertex touches, and the two representations differ far more in transfers than in operations.

Named by 7 essays across 3 fields — each of them below, with the objects they name alongside it.

10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapDijkstra, all V queuedBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons

Counting on a graph

An instrumented array counts comparisons, swaps, reads and writes, and none of those is what a graph algorithm spends its time on. Three new primitives are needed — an adjacency scanned, a vertex first reached, an edge relaxed — and once they exist, breadth-first and depth-first search turn out to be the same algorithm by every count kept on arrays.

graphs · Graph 10010³1010010³nstack framesa stack of 512 framespivot: first-elementpivot: median of threepivot: random pivotMerge sortalready sorted input, n from 64 to 4,096one frame charged as one slot

The stack nobody counts

Merge sort makes 8,192 calls to sort 4,096 elements and holds fourteen of them at once. Depth-first search on a grid holds twelve vertices, or sixty-six, or a hundred and forty-four, depending on which of three equally standard implementations is running. The stack is a resource, it is the one that fails hard rather than slowly, and nothing that watches the data can see it.

space · Space sparse, fixed average degree10010³10³10⁴10⁵10⁶VworkDijkstra, binary heap — E log EDijkstra, all V queued — V^2dense, fixed density10010⁴10⁵VworkDijkstra, binary heap — V + EDijkstra, all V queued — Ethe class is a property of the sweep as much as of the algorithmwork = scans + visits + relaxations + queue comparisons

Two parameters, one bound, no order

With one size parameter the candidate classes are ordered — n beats n log n beats n², always, and comparing two bounds is reading them. With two, E log V and V² have no order at all, and which one is smaller is a property of the graph. Sweeping V at fixed degree and at fixed density are different experiments, and the same algorithm fits different classes in the two.

graphs · Graph adjacency scansrelaxationsqueue comparisonsvisitsBreadth-first14,336Dijkstra, all V queued2,118,656Dijkstra, binary heap56,973Bellman–Ford, all passes50,309,120Prim64,884Kruskal74,008V = 2048, E = 6,144, sparse, fixed average degreeevery segment counted exactly

The queue decides the class, and the pseudocode does not name it

Dijkstra's algorithm is eleven lines of pseudocode with a priority queue in the middle of them. Which queue is not stated, and it is the difference between 56,973 units of work and 2,118,656 on the same graph. Two of the three queues here also fail to fit the class they are famous for, in a regime each.

graphs · Graph with the edge — connected01234567all 8 edges presentwithout it — two components01234567one edge withheld, everything else identicalV = 8, E = 8Ω(E), by adversary rather than by counting

The adversary who hides the edge

The floor under comparison sorting comes from counting outputs — n! of them, so log₂(n!) comparisons. Connectivity has two outputs, so the same argument gives a floor of one comparison, which is useless. A different kind of argument gives Ω(E), and having both on the site is the point: lower bounds are not one technique.

floors · Floor 10³10³10⁴Vmodelled missesadjacency listCSR array96% miss27% miss64 lines × 8 elements, fully associative, LRU3.6× between two layouts of one graph

A list and a block of memory

The same traversal, over the same graph, examining the same edges in the same order, laid out two ways. Twelve thousand two hundred and eighty-eight edge slots either way; 11,812 modelled cache misses against 3,258. This is the site's largest gap between two counts of one run, and it exists because one of the layouts is a pointer chase and the other is a sweep.

graphs · Graph probe 1: 0–1 absent9 still to ask10 of 10 as good as anyprobe 2: 0–2 absent8 still to ask9 of 9 as good as anyprobe 3: 0–3 absent7 still to ask8 of 8 as good as anyprobe 4: 0–4 present6 still to ask7 of 7 as good as anyprobe 5: 1–2 absent5 still to ask6 of 6 as good as anyprobe 6: 1–3 absent4 still to ask5 of 5 as good as anyprobe 7: 1–4 present3 still to ask4 of 4 as good as anyprobe 8: 2–3 absent2 still to ask3 of 3 as good as anyprobe 9: 2–4 present1 still to ask2 of 2 as good as anyprobe 10: 3–4 absentdecided1 of 1 as good as any5 vertices · 10 pairs · 59,049 states solvedsolid: present · dotted: absent · coloured: this probe

Every pair must be asked

Ask whether a six-vertex graph is connected, one pair of vertices at a time, and the best possible algorithm needs all fifteen questions on its worst graph. The claim that this holds for every monotone property of graphs is a conjecture fifty years old. At four vertices it can be settled completely: all 2,046 properties that do not depend on vertex names need every pair. Name one vertex, and the count drops from ten to four.

floors · Floor

Named alongside it

The objects these essays reach for when they reach for this one.

TraversalDensityDijkstra's algorithmSparse graphAdjacency listAdversary argumentConnectivityDecision treeEvasivenessHeapLower boundSearch frontier

All concepts