Relation: explicitly defined partial ordering
The Abstract Directed Acyclic Graph (DAG) is defined on a set of objects called vertices and if then the data structure stores a directed edge from to . The collection of vertices and directed edges are denoted G and E, respectively, and the number of vertices and edges are denoted |G| and |E|, respectively.
In the case of a weighted DAG, each directed edge is associated with a (usually a strictly positive numeric) weight.
The immediate successors may or may not be linearly ordered. If they are linearly ordered, it may be possible to perform some operations more efficiently.
These are simply modifications of insertions and verification.
In the last case, the value numeric_limits
The operation to determine if a path from one vertex to another exists would similarly change for a weighted graph: double are_connected( Vertex, Vertex ) const;.
The data structures for storing a DAG are similar to 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 is 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.cpp depends on gui.cpp, but interface.cpp is explicitly stated to depend on windowing_app.cpp which in turn depends on gui.cpp.