Directed acyclic graph

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG /ˈdæɡ/ (listen)), is a finite directed graph with no directed cycles. That is, it consists of finitely many vertices and edges (also called arcs), with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again. Equivalently, a DAG is a directed graph that has a topological ordering, a sequence of the vertices such that every edge is directed from earlier to later in the sequence. DAGs can model many different kinds of information. For example, a spreadsheet can be modeled as a DAG, with a vertex for each cell and an edge whenever the formula in one cell uses the value from another; a topological ordering of this DAG can be used to update all cell values when the spreadsheet is changed.Similarly, topological orderings of DAGs can be used to order the compilation operations in a makefile. The program evaluation and review technique (PERT) uses DAGs to model the milestones and activities of large human projects, and schedule these projects to use as little total time as possible. Combinational logic blocks in electronic circuit design, and the operations in dataflow programming languages, involve acyclic networks of processing elements. DAGs can also represent collections of events and their influence on each other, either in a probabilistic structure such as a Bayesian network or as a record of historical data such as family trees or the version histories of distributed revision control systems. DAGs can also be used as a compact representation of sequence data, such as the directed acyclic word graph representation of a collection of strings, or the binary decision diagram representation of sequences of binary choices. More abstractly, the reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability. Important polynomial time computational problems on DAGs include topological sorting (computing a topological ordering), construction of the transitive closure and transitive reduction (the largest and smallest DAGs with the same reachability relation, respectively) of sets, and the closure problem, in which the goal is to find a minimum-weight subset of vertices with no edges connecting them to the rest of the graph. Transforming a directed graph with cycles into a DAG by deleting as few vertices or edges as possible (the feedback vertex set and feedback edge set problem, respectively) is an NP-hard problem, but any directed graph can be made into a DAG (its condensation) by contracting each strongly connected component into a single supervertex. The problems of finding shortest paths and longest paths can be solved on DAGs in linear time, in contrast to arbitrary graphs for which shortest path algorithms are slower and longest path problems are NP-hard. The corresponding concept for undirected graphs is a forest, an undirected graph without cycles. Choosing an orientation for a forest produces a special kind of directed acyclic graph called a polytree. However, there are many other kinds of directed acyclic graph that are not formed by orienting the edges of an undirected acyclic graph. Moreover, every undirected graph has an acyclic orientation, an assignment of a direction for its edges that makes it into a directed acyclic graph. To emphasize that DAGs are not the same thing as directed versions of undirected acyclic graphs, some authors call them acyclic directed graphs or acyclic digraphs. A graph is formed by a collection of vertices and edges, where the vertices are structureless objects that are connected in pairs by edges. In the case of a directed graph, each edge has an orientation, from one vertex to another vertex.A path in a directed graph can be described by a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge. A directed acyclic graph is a directed graph that has no cycles. A vertex v of a directed graph is said to be reachable from another vertex u when there exists a path that starts at u and ends at v. As a special case, every vertex is considered to be reachable from itself (by a path with zero edges). If a vertex can reach itself via a nontrivial path (a path with one or more edges), then that path is a cycle, so another way to define directed acyclic graphs is that they are the graphs in which no vertex can reach itself via a nontrivial path. A topological ordering of a directed graph is an ordering of its vertices into a sequence, such that for every edge the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge.A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way. Therefore, every graph with a topological ordering is acyclic.Conversely, every directed acyclic graph has at least one topological ordering. Therefore, this property can be used as an alternative definition of the directed acyclic graphs: they are exactly the graphs that have topological orderings. The reachability relationship in any directed acyclic graph can be formalized as a partial order ≤ on the vertices of the DAG. In this partial order, two vertices u and v are ordered as u ≤ v exactly when there exists a directed path from u to v in the DAG; that is, when v is reachable from u. However, different DAGs may give rise to the same reachability relation and the same partial order. For example, the DAG with two edges a → b and b → c has the same reachability relation as the graph with three edges a → b, b → c, and a → c. Both of these DAGS produce the same partial order, in which the vertices are ordered as a ≤ b ≤ c.