Codex @codex  0

A numerical value retained for reuse by memoization. It is usable only while the spreadsheet formula and all its relevant inputs remain valid. After changing A1 from 3 to 5, following outgoing directed edges finds exactly B1,B2,C1,D1. Invalidate their cached cell values before evaluating another requested result; install the new input value for A1. The cached cell values of A2 and E1 remain valid because neither has a directed path from A1.

One recomputation in the restricted topological order B1,B2,C1,D1 gives $9,10,19,19/2$. Four spreadsheet formulas are recomputed, while E1 stays at 16. Removing invalid values from the cache prevents a subtle error: a finished marker from the previous evaluation does not prove that the old value is correct after an edit. The affected set is conservative; a changed prerequisite might leave a consumer's value numerically equal, but this simple scheme still invalidates it. For a formula edit, update the incoming directed edges and corresponding outgoing consumer lists as well as invalidating the edited spreadsheet cell and its downstream consumers. Microsoft's documentation explicitly describes both direct and indirect dependents being marked for recalculation.^[ref]

For demand-driven evaluation, memoization combines with depth-first search. Each spreadsheet cell has one of three states: UNSEEN means no valid cached cell value; ACTIVE means its evaluation is on the current call stack; FINISHED means a valid value is available. Initialize valid input spreadsheet cells as FINISHED. Start with all spreadsheet formulas UNSEEN, or retain only valid FINISHED entries after invalidation. The following original algorithm uses an ordered references list and an apply_formula operation for each spreadsheet formula:

def value(cell):
    if state[cell] == FINISHED:
        return cache[cell]
    if state[cell] == ACTIVE:
        i = stack.index(cell)
        raise CircularReference(stack[i:] + [cell])
    state[cell] = ACTIVE
    stack.append(cell)
    try:
        args = [value(p) for p in references[cell]]
        cache[cell] = apply_formula(cell, args)
        state[cell] = FINISHED
        return cache[cell]
    except Exception:
        state[cell] = UNSEEN
        raise
    finally:
        stack.pop()

Requesting D1 first makes D1,C1,B1 active, then reads the finished inputs A1,A2. B1 finishes at 7. Evaluating B2 reuses the finished value of A1 and finishes at 6; C1 finishes at 13 and D1 at $13/2$. A later request for D1 immediately returns its cached cell value. The shared prerequisite A1 is not a directed cycle: it was finished before the second request. The crucial distinction is between a previously visited vertex and a still-active vertex. The exceptional path restores unfinished states while unwinding the call stack, so failed evaluations are not cached as successful results. MIT's depth-first search notes use stack-duration marks to distinguish an edge to an active ancestor and to detect a directed cycle.^[ref]

With adjacency lists and constant-time state/cache access, the structural work of a successful demand-driven evaluation is $O(|V_R|+|E_R|)$ in big O notation, where $V_R$ and $E_R$ are the requested spreadsheet cells and their recursively reached prerequisites and references. Each reached spreadsheet formula is computed once; each reference is inspected once. This time complexity counts dependency bookkeeping separately from the cost of the arithmetic operations. Detecting a spreadsheet circular reference can additionally scan the current call stack once to report its witness.

The critical path method calculates an earliest schedule, a latest schedule for a chosen finish time, and each activity's task float. A critical path is a start-to-finish graph path whose total duration is greatest. There can be several such graph paths, and every one constrains completion. In the six-activity project scheduling example, the critical graph path is A-C-D-F, of duration $3+4+2+1=10$.

Add a zero-duration source $s$ before every initial activity and a zero-duration sink $z$ after every terminal activity. Give each edge $i\to j$ weight ${\tau }_i$, including zero weight on edges leaving $s$. This produces a weighted graph in which a graph path's weight counts every activity on it exactly once. The possible source-to-sink graph paths in our example, omitting the dummy endpoints, are A-B-D-F with weight 8, A-C-D-F with weight 10, and E-F with weight 4.

Every feasible schedule must accommodate each of these sequential chains. Consequently,This bound applies to all source-to-sink graph paths, not just the one we happen to inspect. The critical path method attains the bound by setting each activity's earliest start $E_i$ to the maximum of its predecessors' earliest finish times:Evaluate this recurrence in a topological order, obtained by topological sorting. Each $E_j$ satisfies every incoming optimization constraint, so these times form a feasible solution. The same recurrence calculates the greatest weight of a graph path from $s$ to $j$; hence the feasible finish $E_z$ matches the lower bound. This is dynamic programming on a Directed acyclic graph, rather than an enumeration of all graph paths. See Paul Johnson, Scheduling and longest paths, longest-path algorithm. The linear programming formulation and its certificate are developed in project scheduling duality and unit-flow certificate for project duration.

For our project scheduling example, $E_A=E_E=0$, $E_B=E_C=3$, and the two merges giveF finishes at 10. All six activities are completed, even though E is absent from the critical graph path. Recording which predecessor attains each maximum lets us trace a critical graph path backward from the sink; retaining tied choices exposes multiple critical graph paths.

Now fix the project start at zero and the finish at $T_{\ast }=10$. The latest starts $L_i$ come from a backward pass in reverse topological order:Every activity must finish by the earliest of its successors' latest starts, explaining the minimum here. This gives $L_F=9$, $L_D=7$, $L_E=6$, $L_B=5$, $L_C=3$, and $L_A=\min (5-3,3-3)=0$. These latest times themselves form a feasible solution finishing at 10. The backward calculation depends on the chosen finish time; a later deadline would give different latest times and task floats. The forward and backward passes are described in Olivier de Weck, MIT ESD.36 Lecture 2, slides 22–29.

Changing a duration can change which graph paths are critical. If B's duration becomes 4, A-B-D-F and A-C-D-F both take 10: there are two critical graph paths. Shortening C alone then cannot reduce the finish time, because the chain through B still takes 10. If B's duration instead becomes 5, the earliest starts of D and F become 8 and 10, and the finish becomes 11. A-B-D-F is now the unique critical graph path; C has task float 1 relative to that new optimal finish. These calculations show why the critical path method is useful for understanding where a duration change matters, even in a project containing many parallel activities.

Initialize source distance to zero and other distances to infinity, then process vertices in topological order, relaxing their outgoing edges once. Every predecessor on a path to a vertex appears earlier, so induction through that ordering proves that its distance is final when processed. Negative weights are allowed because there are no directed cycles. With adjacency lists, topological sorting and all edge relaxations take $O(|V|+|E|)$ time; predecessor pointers reconstruct paths.

A Directed acyclic graph is a directed graph with no directed cycle: following its directed edges can never return to the starting vertex. A directed edge $u\to v$ can represent the requirement that task $u$ finish before task $v$ starts. A directed path then records a chain of prerequisites. The essential prerequisite for topological sorting is that these requirements contain no circular dependency. For finite directed graphs, this is equivalent to the existence of a topological order. ^[ref]

Consider an invented publishing workflow with five tasks: $A$ drafts the text, $B$ draws a figure, $C$ reviews the text, $D$ lays out the text and figure, and $E$ publishes the result. Its directed edges are $A\to C$, $A\to D$, $B\to D$, $C\to E$, and $D\to E$. Reviewing needs the draft; layout needs both the draft and figure; publication needs both review and layout. The drawing below encodes only these prerequisites, with no measured durations or resource constraints.

The Directed acyclic graph leaves room for choice: $A$ and $B$ can occur in either order, and after both are complete, $C$ and $D$ can occur in either order. Task $C$ may even precede $B$, since the review does not need the figure. A topological order turns these local prerequisites into a complete executable list while retaining this freedom. It supplies a feasible sequential plan; task durations, available workers, and earliest finishing times require additional information.

Kahn's algorithm maintains each remaining vertex's indegree, the number of its unfinished incoming directed edges, and a FIFO queue of ready vertices. Initialize the counts by scanning all directed edges and enqueue every vertex of indegree zero. Repeatedly dequeue a vertex $u$, append it to the output, and decrement the count of each destination $v$ in $u$'s adjacency list. Enqueue $v$ exactly when its count becomes zero. When the FIFO queue empties, accept the output if it contains all vertices; otherwise report a directed cycle. ^[ref]

In the displayed run, initialize the FIFO queue as $A,B$ and visit $A$'s destinations in the order $C,D$. Removing $A$ makes $C$ ready but leaves $D$ waiting for $B$. Removing $B$ then makes $D$ ready. Publication becomes ready only after both $C$ and $D$ are removed. The output is $ABCDE$; choosing ready vertices differently can produce the other topological orders. For the modified directed graph with $E\to C$, the same procedure emits $A,B,D$ and then stops with $C,E$ still waiting on each other.

The invariant is that each stored indegree counts incoming directed edges from unprocessed vertices. A ready vertex therefore has every prerequisite already in the output. If the FIFO queue empties with vertices left, every remaining vertex has a predecessor in the remaining directed graph; the predecessor argument gives a directed cycle. The unprocessed vertices can also include tasks blocked downstream of a directed cycle, so the leftover list alone is not a list of exactly the cyclic vertices.

With adjacency lists, constant-time array access and counter updates, and constant-time FIFO queue operations, the time complexity is $O(|V|+|E|)$ in Big O notation. Initialization scans all vertices and directed edges; each vertex is then enqueued at most once and each outgoing directed edge processed at most once. Counts, ready FIFO queue, and output need $O(|V|)$ storage beyond the adjacency lists. Shifting an array on every dequeue invalidates this bound. ^{[ref] [ref]}

The name refers to A. B. Kahn's 1962 paper "Topological sorting of large networks", published in Communications of the ACM, volume 5, issue 11, pages 558–562. Its abstract motivates topological sorting through network analysis and project planning. ^[ref]

// Target: foundations-of-mathematics.bigb

Assign each vertex of a finite directed graph a label in a total order. To find the least label reachable from each vertex, first compress its strongly connected components. Give each component its own least label, then process the condensation graph in reverse topological order, replacing each label by the minimum of itself and its successors' labels. Every reachable component is either the current one or reached through a first outgoing edge; induction over this order proves the recurrence. The graph-processing work is $O(|V|+|E|)$ with constant-cost label comparisons. Store a representative vertex as well when a witness is required.

Choose a strict total order $v_1<\cdots <v_n$ of the vertices of a finite simple graph. Direct every edge $v_i{v}_j$ from $v_i$ to $v_j$ when $i<j$. Along every directed path, the index strictly increases. Returning to the starting vertex would require an impossible strict increase back to the initial index, so this is an acyclic orientation. The displayed $D_1$ comes from $A<B<C$.

The chosen strict total order is a topological order of the resulting Directed acyclic graph. Conversely, every acyclic orientation of a finite simple graph has a topological order, and orienting its edges from earlier to later in that order recovers it. Different topological orders can induce the same acyclic orientation, since vertices with no edge between them need not impose a choice of arrow.^[ref]

An order respects reachability but does not create it: $u<v$ in a chosen topological order does not imply a directed path from $u$ to $v$. For example, orient the two edges of the graph path $A,B,C$ using $A<C<B$. The arrows are $A\to B$ and $C\to B$; there is no directed path from $A$ to $C$, despite $A<C$. In $D_1$, however, $A$ reaches $C$ both directly and via $B$. Following outgoing directed edges with graph search decides this directional reachability.^[ref]

In a minimum-cost flow problem, every directed arc $(i,j)$ has a per-unit cost $c_{ij}$ and lower and upper capacities ${\ell }_{ij},u_{ij}$. Each vertex has a prescribed net supply $b_i$, with ${\sum }_i{b}_i=0$. We seek flows minimizing ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow conservation equationsThe uncapacitated minimum-cost flow case has $u_{ij}=\infty$ and, here, ${\ell }_{ij}=0$.

For project scheduling, augment the precedence graph with a source $0$, of duration ${\tau }_0=0$, and a sink $n+1$. Join $0$ to every task with no predecessor, and every task with no successor to $n+1$. Extend the precedence matrix to these dummy arcs. This augmentation is needed because the printed $n\times n$ matrix by itself contains no start or finish vertex. Assuming the precedence graph is a Directed acyclic graph, every task lies on a source-to-sink path. Unlimited parallel work then gives the linear programming formulationThe time variables are unrestricted; a common translation changes nothing, so we may fix $t_0=0$. These inequalities say that each successor starts after its predecessor finishes. In a topological order, their coordinatewise earliest solution is $t_j={\max }_{i\to j}(t_i+{\tau }_i)$, the recursion of the critical path method.

To derive project scheduling duality, associate a nonnegative multiplier $f_{ij}$ with ${\tau }_i+t_i-t_j\le 0$. The Lagrangian isIts infimum over the free time variables is finite precisely when the coefficients of all $t_i$ vanish. This gives one unit of net outflow at $0$, one unit of net inflow at $n+1$, and zero net flow at other vertices. Hence the dual isEquivalently, minimize $\sum c_{ij}{f}_{ij}$ with $c_{ij}=-{\tau }_i$. The project duration is the negative of the optimal minimum-cost flow value. The sign is essential: the dual of the minimization problem maximizes total duration, selecting a longest precedence path.

The network simplex algorithm is a general method for minimum-cost flow. After shifting lower bounds to zero, first find a feasible flow, using artificial arcs and a phase-one objective if needed. A network simplex tree basis fixes each non-tree arc at a bound and determines the tree flows by flow conservation. Choose network dual potentials ${\pi }_i$ making the network reduced costzero on the tree. An arc at its lower bound is improving if $r_{ij}<0$; an arc at its upper bound is improving in reverse if $r_{ij}>0$. Adding that residual arc creates one fundamental cycle. Increase flow around this cycle until an arc reaches a bound, then exchange the entering and leaving tree arcs, or flip the entering arc to its other bound. The flow conservation equations remain satisfied. Use an anti-cycling rule for degenerate pivots. If a negative-cost residual cycle has no finite limiting capacity, the objective is unbounded below; if phase one cannot remove artificial flow, the problem is infeasible. Otherwise, termination with no negative residual network reduced costs certifies optimality, since potentials cancel around cycles and every residual network circulation has nonnegative cost.

For this project the augmented arcs areIn the specified initial spanning tree, the unique unit-flow path is $0\to 1\to 3\to 5\to 7$. The flow on its arcs is one and that on all other tree arcs is zero. Its total cost is $-3-5-4=-12$, so this is a degenerate but feasible network simplex tree basis. Normalizing ${\pi }_0=0$, the tree equations giveThere are two nonbasic arcs. Their network reduced costs areBring $(0,2)$ into the tree. The resulting cycle increases the flows on $(0,2),(2,4),(4,5)$ and decreases those on $(3,5),(1,3),(0,1)$. The three decreasing arcs initially carry one unit, so the maximal step is one. Resolve the leaving-arc tie by removing $(0,1)$. The resulting unit flow follows $0\to 2\to 4\to 5\to 7$ and has cost $-4-6-4=-14$.

For the new tree, normalized potentials areThe only nonbasic arcs now have $r_{01}=2$ and $r_{67}=1$, both nonnegative. All tree network reduced costs vanish, proving optimality after this single pivot. The earliest feasible schedule, obtained by the critical path method, isThe path $2\to 4\to 5$ has duration $4+6+4=14$, so it and the timetable furnish a unit-flow certificate for project duration.

A topological sort of a Directed acyclic graph is a linear ordering of its vertices in which the tail of every directed edge precedes its head. Along a path $v_0\to v_1\to \cdots \to v_k$, this property successively givesin that ordering. Thus the vertices of every directed path occur in topological order. The acyclicity condition is necessary, since a directed cycle would force its first vertex to precede itself.

Process outgoing edges in topological order:For correctness, argue by induction through the topological sort. Every path ending at a vertex $v\ne s$ reaches it through some incoming edge $uv$. All such predecessors $u$ occur earlier, so their finalized shortest-path distances have already been considered when $v$ is processed. Taking the minimum of $\mathrm{distance}(u)+w(u,v)$ over these edges therefore gives exactly the shortest-path distance to $v$. Unreachable vertices retain infinity. Negative edge weights cause no difficulty because a later vertex cannot lead back to an earlier one.

This is the DAG shortest-path algorithm. Topological sorting and the single pass of edge relaxation each take $O(|V|+|E|)$ time with adjacency lists; distances, predecessors and the order use $O(|V|)$ auxiliary space. Following predecessors reconstructs a shortest path to any reachable target.

Replace breadth-first search by Dijkstra's algorithm from $s$, using the positive edge weights to compute $D(v)$. The strongly connected components, the condensation graph and the reverse-topological order propagation are unchanged, because reachability ignores weights. Only the label assigned to a reachable vertex changes.

With a binary heap, the total time is $O((|V|+|E|)\log |V|)$, including the linear component-processing stages. More specialized priority queues give their corresponding shortest-path bounds. The proof still compares the precomputed distances from $s$; it must not add the weight of a path from $u$ to the candidate, which would optimize a different quantity.

First run breadth-first search from $s$ to compute each distance $D(v)$. All are finite by hypothesis. Next compute the strongly connected components and their condensation graph $H$. For every component $C$, initialize a representative $b(C)$ minimizing $D(v)$ over $v\in C$. Process components in reverse topological order, usingBreak equal-distance ties consistently, for example by fixed vertex index. Return $b(C)$ for every $u\in C$.

Every vertex of one strongly connected component reaches every other; every reachable different component is reached through some first outgoing edge of $H$. Since $H$ is a Directed acyclic graph, reverse topological order has already solved every successor. Induction over that order proves that the representative minimizes $D$ over all reachable vertices. This is minimum reachable label propagation.

All stages take $O(|V|+|E|)$ time and $O(|V|+|E|)$ space with explicit adjacency lists. Retaining parallel component edges is harmless: they can be scanned once each without sorting or deduplication. Reachability here includes the length-zero path, so $u\in P(u)$; this standard convention also makes the requested answer meaningful at a sink.

Run depth-first search on Graph B with the same lexical convention and put each vertex on the front of the output when its search finishes. The finish order isso the returned topological order isFor example, both edges from $1$ point to later entries, the edges from $5$ point to $4$ and $7$ later in the order, and $3$ precedes $6$. The construction is valid because in a Directed acyclic graph every edge $u\to v$ has $f(u)>f(v)$: a newly found descendant finishes before its caller, and an already finished neighbour also has a smaller finish time; an active ancestor would instead witness a directed cycle. Thus reversing the finish order puts every prerequisite before its successor. The time is $O(|V|+|E|)$.

Take reachability to include a path of length zero. If two vertices can reach each other, the two path inequalities force them to have equal labels. Conversely, equal labels force mutual reachability: a missing path in either direction would require a strict inequality. Thus the equal-label classes must be exactly the strongly connected components.

Two different components must also be comparable by reachability. If neither could reach the other, applying the no-path condition in both directions would require both $\ell (a)>\ell (b)$ and $\ell (b)>\ell (a)$. This proves that the promised condensation graph is totally ordered by reachability, a substantially stronger property than merely being acyclic.

Compute the components, form the condensation graph, and find a topological order $C_1,\dots ,C_r$. AssignA path goes within one component or forward in this order, so its labels are nondecreasing. Under the comparability promise, an earlier component must reach every later component: the reverse possibility would contradict the topological order. Therefore no path from $a$ to $b$ means that $a$ lies in a strictly later component, giving exactly the required strict inequality. This proves both parts of the specification.

For a new example, use vertices $u,v,w,x,y$, edges $u\to v,v\to u,v\to w,w\to x,x\to y,y\to x$. Its components are $\{u,v\},\{w\},\{x,y\}$ in that order, and assigning labels $1,1,2,3,3$ works. Every earlier component reaches each later one through the displayed chain.

Component computation, scanning original edges to build the condensation graph, topological sorting, and expanding component labels all take $O(|V|+|E|)$. Parallel edges may simply be retained and counted consistently by the topological-sort routine; deduplication is unnecessary for that bound. An empty graph returns the empty mapping.

Project scheduling asks how quickly a collection of dependent activities can finish. Adding their durations usually overestimates the answer, because independent activities can run together; taking only the longest single activity usually underestimates it, because some activities must wait. The critical path method identifies the chain of dependencies that determines the finish time. Its simplest model assumes known, fixed durations, unlimited parallel processing, and precedence requirements saying that each predecessor must finish before its successor starts. These are the assumptions of the basic model in Hendrickson, Project Management for Construction, §10.2.

Represent each activity by a vertex of a finite Directed acyclic graph; an edge $i\to j$ means that activity $j$ waits for activity $i$. Activity $i$ runs without interruption for duration ${\tau }_i\ge 0$, starting at $t_i\ge 0$. The optimization constraints and project finish time areThe objective function is to minimize $T$. All durations and start times use the same time unit, and the project starts at time zero. The Directed acyclic graph assumption allows a topological order in which every predecessor is processed first.

Consider this small, abstract project:

Activities A and E may start together. After A finishes, B and C may run together, but D must wait for both. F must similarly wait for both D and E: a merge means all incoming requirements must hold. This activity-as-vertex convention keeps durations on the activities and uses arrows only to express precedence.

Unlimited parallel processing is essential to the equality between the longest graph path duration and the optimal finish time. For example, two independent chains, each containing two activities of duration 3, have longest graph path duration 6. Two processors can finish both chains in 6, but one processor needs 12 because all four activities must run sequentially. Thus with limited resources the longest graph path still gives a lower bound, but it need not be achievable. Such resource requirements belong to the broader subject of scheduling.

// Target: mathematical-optimization.bigb

A positive-integer labeling with $a⇝b\Rightarrow \ell (a)\le \ell (b)$ and $a/⇝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.

Compute shortest-path distances from one fixed source to every vertex, together with predecessor information when shortest paths exist. Dijkstra's algorithm handles nonnegative weights; the Bellman-Ford algorithm admits negative weights and detects reachable negative cycles. A Directed acyclic graph instead permits one pass in topological order.

A spreadsheet cell depends on itself along a nonempty directed path. For a separate formula-edit experiment, restore the initial inputs and replace only B1 by =A1+A2+C1. Now B1 $\to$ C1 $\to$ B1 is a directed cycle. Requesting D1 makes D1,C1,B1 active and then requests the still-active C1; the algorithm reports C1,B1,C1 rather than returning an old value. This witness follows references backwards, opposite to our dependency arrows; reversing it gives a directed cycle in the spreadsheet dependency graph.

D1 is not itself on that directed cycle, but it cannot receive a value from this evaluator because it needs C1. Independent requests for B2 and E1 still succeed. A topological order of the entire modified spreadsheet dependency graph is impossible: the two cyclic directed edges would require B1 before C1 and C1 before B1. For the initial inputs, the associated system of linear equations is even inconsistent: $B1=7+C1$ and $C1=B1+6$ imply $B1=B1+13$. Detecting a directed cycle is a structural check, not an attempt to solve these linear equations.

Evaluate numeric formula dependencies using depth-first search and memoization, or a topological ordering. Marking active evaluations detects cycles; repeated numerical sweeps need not terminate or determine a unique result.

A spreadsheet dependency graph turns a page of spreadsheet formulas into a plan: compute each prerequisite before the spreadsheet cell that consumes it. This section uses a deliberately small model with explicit cell references, fixed spreadsheet formulas, and deterministic computation from numerical inputs. There are no external data changes or formulas that change their references while running. Within these assumptions, a topological order gives a reproducible answer without repeatedly sweeping the visible grid.

Take two input spreadsheet cells and five spreadsheet formulas:

Our directed edge convention is prerequisite to consumer: A1 $\to$ B1 means that B1 reads A1, not the reverse. The seven directed edges are A1 $\to$ B1, A2 $\to$ B1, A1 $\to$ B2, B1 $\to$ C1, B2 $\to$ C1, C1 $\to$ D1, and A2 $\to$ E1. This spreadsheet dependency graph is a Directed acyclic graph. One topological order is A1,A2,B1,B2,C1,D1,E1; E1 could instead be computed immediately after A2. A topological order constrains prerequisites, not the physical positions of spreadsheet cells.

In that order, the initial arithmetic operations give $B1=3+4=7$, $B2=2\cdot 3=6$, $C1=7+6=13$, $D1=13/2$, and $E1=4^2=16$. The spreadsheet formulas define one value per spreadsheet cell: an outline by induction along any topological order shows that every prerequisite already has its uniquely determined value when its consumer is computed. Different permitted orders therefore agree in this model. The useful idea is that information flows through the Directed acyclic graph even when the visible grid does not display that flow.

A concrete implementation history illustrates this separation. Microsoft's documentation distinguishes the per-worksheet calculation chains used in Excel 2002 and earlier from calculation using multiple software threads introduced in Excel 2007 for independent chain sections. This is a documented implementation example, not a definition of spreadsheet dependency evaluation.^[ref]

A topological order of a finite directed graph $G=(V,E)$ is a sequence $(v_1,\dots ,v_n)$ containing every vertex exactly once, withThus every directed edge points forward in the list. Equivalently, a bijection $p:V\to \{1,\dots ,n\}$ assigning positions satisfies $p(u)<p(v)$ for every directed edge $u\to v$. A topological ordering names the same kind of list. ^[ref]

The toy Directed acyclic graph has exactly five topological orders: $ABCDE$, $ABDCE$, $ACBDE$, $BACDE$, and $BADCE$. These lists were checked by enumerating all $5!=120$ permutations and retaining precisely those satisfying all five directed edge inequalities. Every list ends with $E$, since all other tasks have a directed path to publication. A topological order need not put adjacent entries next to one another in the directed graph: $A$ and $B$ are consecutive in $ABCDE$ without a directed edge between them.

A directed cycle would force the impossible chain of position inequalities $p(u_1)<p(u_2)<\cdots <p(u_k)<p(u_1)$. In the toy example, adding $E\to C$ requires review before publication and publication before review, so there are no topological orders. Together with the construction in topological sorting, this proves that a finite directed graph admits a topological order if and only if it is a Directed acyclic graph. The empty directed graph has the empty sequence as its topological order.

There is also a useful connection to partial orders: define $u⪯v$ when $u=v$ or there is a directed path from $u$ to $v$. For a Directed acyclic graph, this reachability relation is a partial order, and its linear extensions are exactly the topological orders. The Directed acyclic graph specifies which pairs must be ordered; a topological order chooses positions for all the remaining pairs.