Directed acyclic graph

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.

A topological sorting is the task of constructing a topological order of a finite directed graph, or reporting that a directed cycle makes one impossible. Kahn's algorithm repeatedly takes a vertex with no unfinished prerequisites. This is useful whenever an operation consumes results produced by earlier operations: once a vertex is reached in a topological order, every prerequisite along a directed path has already been processed. ^[ref]

The reason a choice is always available in a nonempty finite Directed acyclic graph is simple. If every vertex had an incoming directed edge, repeatedly following predecessors would eventually revisit a vertex, giving a directed cycle. Removing a vertex and its incident directed edges cannot create a directed cycle, so the argument repeats until every vertex is listed. This proves existence of a topological order and explains why finiteness matters to this procedure.

// Target: combinatorics.bigb

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.

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

Two Directed acyclic graphs are Markov equivalent when they encode the same D-separations for all disjoint sets of vertices. They consequently impose the same global Markov property for a directed acyclic graph, although their causal interpretations can differ.

The completed partially directed acyclic graph of a Markov equivalence of directed acyclic graphs class has their common skeleton of a directed graph. An edge is directed exactly when its orientation agrees in every member of the class, and is otherwise undirected. It can be constructed by enumerating all acyclic orientations with the prescribed unshielded colliders and retaining only the common directions; practical PC algorithms use orientation propagation instead of enumeration.

Two Directed acyclic graphs are Markov equivalent directed acyclic graphs if and only if they have the same skeleton of a directed graph and the same unshielded colliders. Thus these two structures determine the observational equivalence class. This structural theorem is what converts the skeleton and collider phases of the PC algorithm into identification of an equivalence class.

The moral graph of a Directed acyclic graph joins every pair of vertices with a common child and then replaces every directed edge by an undirected edge.

For a strictly positive probability density, factorization into clique potentials of an undirected graph is equivalent to the global Markov conditional-independence property for that graph.

A topological ordering is a topological order: a list containing every vertex once and placing the source of every directed edge before its destination. In the parent-and-child language of a Directed acyclic graph, every parent precedes every child, and hence every ancestor precedes every descendant along a directed path. This is an ordering of the vertices, whereas topological sorting is the task of finding it. See topological order for the precise position condition and Kahn's algorithm for a construction.

D-separation blocks paths through conditioned noncolliders and through unconditioned colliders without conditioned descendants.

On a path in a directed graph, an interior vertex is a collider when both adjacent path edges have arrowheads pointing into it. A path through a collider is blocked unless that collider or one of its descendants is conditioned upon.

An unshielded collider in a Directed acyclic graph is a triple $a\to b\leftarrow c$ with $a$ and $c$ nonadjacent. The absence of an edge between its outer vertices makes this orientation detectable from conditional independence information under faithfulness of a directed acyclic graph.

A set d-separates two vertex sets when it blocks every path between them.

Conditioned on its parents, a vertex is d-separated from all nondescendants other than those parents.

The global Markov property of a Directed acyclic graph says that d-separation of vertex sets $A$ and $B$ by $S$ implies conditional independence of the corresponding random vectors given the variables at $S$.