Directed Acyclic Graph (DAG) Data Structure
A Directed Acyclic Graph (DAG) Data Structure is a directed graph data structure that can represent a directed acyclic graph.
- Context:
- It can enforce Partial Ordering.
- …
- Example(s):
- a Tree Data Structure.
- …
- Counter-Example(s):
- See: Bayesian Network Data Structure, Hypergraph, DAG Task Workflow.
References
2010
- https://ece.uwaterloo.ca/~dwharder/aads/Abstract_data_types/Partial_ordering/DAG/
- QUOTE: The data structures for storing a DAG are similar to those of a graph; however, unless it is known before hand that the connections do not violate the requirements of a partial ordering, it is necessary to determine whether adding a connection between two vertices forms a loop. This is a potentially expensive operation. In general, it is only necessary to store local relations, for example, "A precedes B" and "B precedes C". Algorithms can be implemented which to not require the explicit storing that consequently "A precedes C" which may be implicitly deduced from the two given relations.
Consequently, the most efficient data structure for storing a DAG is likely a list of explicitly defined dependencies.
One example of the source of the partial ordering are dependencies listed in a Makefile. The dependencies must satisfy a partial ordering and a topological sort yields an order in which the files may be compiled. When a file is changed, it is only necessary to recompile successors.
In this case, we have a local definition of a partial ordering: it may not be explicitly stated that
interface.cppdepends ongui.cpp, butinterface.cppis explicitly stated to depend onwindowing_app.cppwhich in turn depends ongui.cpp.
- QUOTE: The data structures for storing a DAG are similar to those of a graph; however, unless it is known before hand that the connections do not violate the requirements of a partial ordering, it is necessary to determine whether adding a connection between two vertices forms a loop. This is a potentially expensive operation. In general, it is only necessary to store local relations, for example, "A precedes B" and "B precedes C". Algorithms can be implemented which to not require the explicit storing that consequently "A precedes C" which may be implicitly deduced from the two given relations.