Abstract Directed Acyclic Graph / DAG ADT

Relation: explicitly defined partial ordering

The Abstract Directed Acyclic Graph (DAG) is defined on a set of objects called vertices and if tex:$$ a \rightarrow b $$ then the data structure stores a directed edge from tex:$$ a $$ to tex:$$ b $$. 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.

Operations Relevant for the Abstract DAGs

    bool insert_edge( Vertex, Vertex );
  • Add an edge between two vertices and return false if a cycle is created.
    bool insert_edge( Vertex, Vertex );
  • Determine if there is an edge from one vertex to another.
    bool adjacent( Vertex, Vertex ) const;
  • Return an iterator which walks through the adjacent vertices.
    iterator adjacent( Vertex ) const;
  • Remove an edge.
    void remove( Vertex, Vertex ) const;

Operations Relevant for Abstract Weighted DAGs

These are simply modifications of insertions and verification.

  • Add an edge between two vertices.
    void insert_edge( Vertex, Vertex, double );
  • Determine if there is an edge from one vertex to another.
    double adjacent( Vertex, Vertex ) const;

In the last case, the value numeric_limits::infinity() is used to denote that two vertices are not adjacent/connected (there is an infinite distance between the two).

Queries Relevant to the Complete DAG

  • Is there a path from one vertex to another?
    bool are_connected( Vertex, Vertex ) const;
  • Return an iterator which walks through the path connecting two vertices in order.
    iterator connected( Vertex, Vertex ) const;
  • Is a DAG weakly connected? (For each pair tex:$$ a $$ and tex:$$ b $$, is there at least one path from from either tex:$$ a $$ to tex:$$ b $$ or from tex:$$ b $$ to tex:$$ a $$?)
    bool is_weakly_connected() const;

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;.

Example Data Structures

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.