In mathematics and computer science, a directed acyclic graph (DAG i/ˈdæɡ/), is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again.
DAGs may be used to model several different kinds of structure in mathematics and computer science. A collection of tasks that must be ordered into a sequence, subject to constraints that certain tasks must be performed earlier than others, may be represented as a DAG with a vertex for each task and an edge for each constraint; algorithms for topological ordering may be used to generate a valid sequence. DAGs may also be used to model processes in which information flows in a consistent direction through a network of processors. The reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability. Additionally, DAGs may be used as a space-efficient representation of a collection of sequences with overlapping subsequences.
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, and every undirected graph has an acyclic orientation, an assignment of a direction for its edges that makes it into a directed acyclic graph. For this reason it may be more accurate to call directed acyclic graphs acyclic directed graphs or acyclic digraphs.
Read more about Directed Acyclic Graph: Partial Orders and Topological Ordering, Data Processing Networks, Causal and Temporal Structures, Paths With Shared Structure, Relation To Other Kinds of Graphs, Enumeration
Famous quotes containing the words directed and/or graph:
“If Mr. Vincent Price were to be co-starred with Miss Bette Davis in a story by Mr. Edgar Allan Poe directed by Mr. Roger Corman, it could not fully express the pent-up violence and depravity of a single day in the life of the average family.”
—Quentin Crisp (b. 1908)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)