Directed acyclic graph

[5] However, different DAGs may give rise to the same reachability relation and the same partial order.

The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set (S, ≤), the graph that has a vertex for every element of S and an edge for every pair of elements in ≤ is automatically a transitively closed DAG, and has (S, ≤) as its reachability relation.

In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation.

[13] A multitree (also called a strongly unambiguous graph or a mangrove) is a DAG in which there is at most one directed path between any two vertices.

Equivalently, it is a DAG in which the subgraph reachable from any vertex induces an undirected tree.

[16] Kahn's algorithm for topological sorting builds the vertex ordering directly.

[17] Alternatively, a topological ordering may be constructed by reversing a postorder numbering of a depth-first search graph traversal.

Different total orders may lead to the same acyclic orientation, so an n-vertex graph can have fewer than n!

The number of acyclic orientations is equal to |χ(−1)|, where χ is the chromatic polynomial of the given graph.

[20] An arbitrary directed graph may also be transformed into a DAG, called its condensation, by contracting each of its strongly connected components into a single supervertex.

[22] Alternatively, it can be solved in time O(nω) where ω < 2.373 is the exponent for matrix multiplication algorithms; this is a theoretical improvement over the O(mn) bound for dense graphs.

[24] The closure problem takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices C, such that no edges leave C. The problem may be formulated for directed graphs without the assumption of acyclicity, but with no greater generality, because in this case it is equivalent to the same problem on the condensation of the graph.

[25] Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering.

[29] An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a spreadsheet after one of the cells has been changed, or the object files of a piece of computer software after its source code has been changed.

For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet.

[32] A somewhat different DAG-based formulation of scheduling constraints is used by the program evaluation and review technique (PERT), a method for management of large human projects that was one of the first applications of DAGs.

In this method, the vertices of a DAG represent milestones of a project rather than specific tasks to be performed.

Each such edge is labeled with an estimate for the amount of time that it will take a team of workers to perform the task.

Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.

For instance, in electronic circuit design, static combinational logic blocks can be represented as an acyclic system of logic gates that computes a function of an input, where the input and output of the function are represented as individual bits.

In general, the output of these blocks cannot be used as the input unless it is captured by a register or state element which maintains its acyclic properties.

This representation allows the compiler to perform common subexpression elimination efficiently.

[36] At a higher level of code organization, the acyclic dependencies principle states that the dependencies between modules or components of a large software system should form a directed acyclic graph.

[40] Another type of graph with a similar causal structure is an influence diagram, the vertices of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one vertex to another.

[41] In epidemiology, for instance, these diagrams are often used to estimate the expected value of different choices for intervention.

[44] Despite the name, these graphs are not necessarily trees because of the possibility of marriages between relatives (so a child has a common ancestor on both the mother's and father's side) causing pedigree collapse.

This structure allows point location queries to be answered efficiently: to find the location of a query point q in the Delaunay triangulation, follow a path in the history DAG, at each step moving to the replacement triangle that contains q.

The classic example comes from the citations between academic papers as pointed out in the 1965 article "Networks of Scientific Papers"[49] by Derek J. de Solla Price who went on to produce the first model of a citation network, the Price model.

By taking the special properties of directed acyclic graphs into account, one can analyse citation networks with techniques not available when analysing the general graphs considered in many studies using network analysis.

A directed acyclic word graph saves space over a trie by allowing paths to diverge and rejoin, so that a set of words with the same possible suffixes can be represented by a single tree vertex.