Gourt Home::Gourt :: Directed acyclic graph
In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path starting and ending on v. DAGs appear in models where it doesn't make sense for a vertex to have a path to itself; for example, if an edge u→v indicates that v is a part of u, such a path would indicate that u is a part of itself, which is impossible.
Terminology
A source is a vertex with no incoming edges, while a sink is a vertex with no outgoing edges. A finite DAG has at least one source and at least one sink.
The length of a finite DAG is the length (number of edges) of a longest directed path.
Properties
Every directed acyclic graph has a topological sort, an ordering of the vertices such that each vertex comes before all vertices it has edges to. In general, this ordering is not unique.
DAGs can be considered to be a generalization of trees in which certain subtrees can be shared by different parts of the tree. In a tree with many identical subtrees, this can lead to a drastic decrease in space requirements to store the structure. Conversely, a DAG can be expanded to a forest of rooted trees using this simple algorithm:
- While there is a vertex v with in-degree n > 1,
- Make n copies of v, each with the same outgoing edges but no incoming edges.
- Attach one of the incoming edges of v to each vertex.
- Delete v.
Some algorithms become simpler when used on DAGs instead of general graphs. For example, search algorithms like depth-first search without iterative deepening normally must mark vertices they have already visited and not visit them again. If they fail to do this, they may never terminate because they follow a cycle of edges forever. Such cycles do not exist in DAGs.
The number of Non-Isomorphic DAGs is obtained by Weisstein's conjecture: the number of DAGs on n vertices is equal to the number of nxn matrices with entries from {0,1} and only positive real eigenvalues, proved by McKay et al. McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; and Wilf, H. "Acyclic Digraphs and Eigenvalues of (0,1)-Matrices." J. Integer Sequences 7, Article 04.3.3, 1-5, 2004. http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf or http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html.
Applications
Directed acyclic graphs have many important applications in computer science, including:
- The parse tree constructed by a compiler
- Bayesian networks
- A reference graph that can be garbage collected using simple reference counting
- The reference graph of a purely functional data structure (although some languages allow purely functional cyclic structures)
- Dependency graphs such as those used in instruction scheduling and makefiles
- Serializability Theory of Transaction Processing Systems
- Information categorisation systems, such as folders in a computer. Note that Categories can be cyclic.
- Realtime terrain Level Of Detail using SOAR (stateless one-pass adaptive refinement).
- Used in hierarchical scene graphs to optimise view frustum culling operations.
References
External links
Gerichteter azyklischer Graph | Graphe acyclique orienté | Skierowany graf acykliczny | Grafos acíclicos dirigidos
"Directed acyclic graph"