Class DirectedAcyclicGraph<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<V>, DirectedGraph<V,​E>, Graph<V,​E>

    public class DirectedAcyclicGraph<V,​E>
    extends SimpleDirectedGraph<V,​E>
    implements java.lang.Iterable<V>

    DirectedAcyclicGraph implements a DAG that can be modified (vertices & edges added and removed), is guaranteed to remain acyclic, and provides fast topological order iteration.

    This is done using a dynamic topological sort which is based on the algorithm PK described in "D. Pearce & P. Kelly, 2007: A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs", (see Paper or ACM link for details).

    The implementation differs from the algorithm specified in the above paper in some ways, perhaps most notably in that the topological ordering is stored by default using two HashMaps, which will have some effects on runtime, but also allows for vertex addition and removal, and other operations which are helpful for manipulating or combining DAGs. This storage mechanism is pluggable for subclassers.

    This class makes no claims to thread safety, and concurrent usage from multiple threads will produce undefined results.

    See Also:
    Serialized Form
    • Constructor Detail

      • DirectedAcyclicGraph

        public DirectedAcyclicGraph​(java.lang.Class<? extends E> edgeClass)
        Construct a directed acyclic graph.
        Parameters:
        edgeClass - the edge class
      • DirectedAcyclicGraph

        public DirectedAcyclicGraph​(EdgeFactory<V,​E> ef)
        Construct a directed acyclic graph.
        Parameters:
        ef - the edge factory
    • Method Detail

      • initialize

        private void initialize()
        set the topoOrderMap based on the current factory, and create the comparator;
      • iterator

        public java.util.Iterator<V> iterator()
        iterator will traverse the vertices in topological order, meaning that for a directed graph G = (V,E), if there exists a path from vertex va to vertex vb then va is guaranteed to come before vertex vb in the iteration order.
        Specified by:
        iterator in interface java.lang.Iterable<V>
        Returns:
        an iterator that will traverse the graph in topological order
      • addVertex

        public boolean addVertex​(V v)
        Adds the vertex if it wasn't already in the graph, and puts it at the top of the internal topological vertex ordering.
        Specified by:
        addVertex in interface Graph<V,​E>
        Overrides:
        addVertex in class AbstractBaseGraph<V,​E>
        Parameters:
        v - the vertex to add
        Returns:
        true if this graph did not already contain the specified vertex.
      • addVertex

        public boolean addVertex​(V v,
                                 boolean addToTop)
        Adds the vertex if it wasn't already in the graph, and puts it either at the top or the bottom of the topological ordering, depending on the value of addToTop. This may provide useful optimizations for merging DirectedAcyclicGraphs that become connected.
        Parameters:
        v - the vertex to add
        addToTop - if true the vertex is added at the top of the topological ordering, if false at the bottom
        Returns:
        whether new vertex was added
      • addDagEdge

        public E addDagEdge​(V fromVertex,
                            V toVertex)
                     throws DirectedAcyclicGraph.CycleFoundException

        Adds the given edge and updates the internal topological order for consistency IFF

        • there is not already an edge (fromVertex, toVertex) in the graph
        • the edge does not induce a cycle in the graph
        Parameters:
        fromVertex - from vertex
        toVertex - to vertex
        Returns:
        null if the edge is already in the graph, else the created edge is returned
        Throws:
        java.lang.IllegalArgumentException - If either fromVertex or toVertex is not a member of the graph
        DirectedAcyclicGraph.CycleFoundException - if the edge would induce a cycle in the graph
        See Also:
        Graph.addEdge(Object, Object, Object)
      • addEdge

        public E addEdge​(V sourceVertex,
                         V targetVertex)
        identical to addDagEdge(Object, Object), except an unchecked IllegalArgumentException is thrown if a cycle would have been induced by this edge
        Specified by:
        addEdge in interface Graph<V,​E>
        Overrides:
        addEdge in class AbstractBaseGraph<V,​E>
        Parameters:
        sourceVertex - source vertex of the edge.
        targetVertex - target vertex of the edge.
        Returns:
        The newly created edge if added to the graph, otherwise null.
        See Also:
        Graph.getEdgeFactory()
      • addDagEdge

        public boolean addDagEdge​(V fromVertex,
                                  V toVertex,
                                  E e)
                           throws DirectedAcyclicGraph.CycleFoundException

        Adds the given edge and updates the internal topological order for consistency IFF

        • the given edge is not already a member of the graph
        • there is not already an edge (fromVertex, toVertex) in the graph
        • the edge does not induce a cycle in the graph
        Parameters:
        fromVertex - the from vertex
        toVertex - the to vertex
        e - the edge
        Returns:
        true if the edge was added to the graph
        Throws:
        DirectedAcyclicGraph.CycleFoundException - if adding an edge (fromVertex, toVertex) to the graph would induce a cycle.
        See Also:
        Graph.addEdge(Object, Object, Object)
      • removeVertex

        public boolean removeVertex​(V v)
        Description copied from class: AbstractBaseGraph
        Removes the specified vertex from this graph including all its touching edges if present. More formally, if the graph contains a vertex u such that u.equals(v), the call removes all edges that touch u and then removes u itself. If no such u is found, the call leaves the graph unchanged. Returns true if the graph contained the specified vertex. (The graph will not contain the specified vertex once the call returns).

        If the specified vertex is null returns false.

        Specified by:
        removeVertex in interface Graph<V,​E>
        Overrides:
        removeVertex in class AbstractBaseGraph<V,​E>
        Parameters:
        v - vertex to be removed from this graph, if present.
        Returns:
        true if the graph contained the specified vertex; false otherwise.
      • removeAllVertices

        public boolean removeAllVertices​(java.util.Collection<? extends V> arg0)
        Description copied from interface: Graph
        Removes all the vertices in this graph that are also contained in the specified vertex collection. After this call returns, this graph will contain no vertices in common with the specified vertices. This method will invoke the Graph.removeVertex(Object) method.
        Specified by:
        removeAllVertices in interface Graph<V,​E>
        Overrides:
        removeAllVertices in class AbstractGraph<V,​E>
        Parameters:
        arg0 - vertices to be removed from this graph.
        Returns:
        true if this graph changed as a result of the call
        See Also:
        Graph.removeAllVertices(Collection)
      • dfsB

        private void dfsB​(V vertex,
                          java.util.Set<V> db,
                          DirectedAcyclicGraph.Visited visited,
                          DirectedAcyclicGraph.Region affectedRegion)
        Depth first search backward, building up the set (db) of back-connected vertices in the Affected Region
        Parameters:
        vertex - the vertex being visited
        db - the set we are populating with back-connected vertices in the AR
        visited -
      • getAncestors

        public java.util.Set<V> getAncestors​(DirectedAcyclicGraph<V,​E> graph,
                                             V vertex)
        Parameters:
        graph - graph to look for ancestors in.
        vertex - the vertex to get the ancestors of.
        Returns:
        Set of ancestors of the vertex in the given graph.
      • getDescendants

        public java.util.Set<V> getDescendants​(DirectedAcyclicGraph<V,​E> graph,
                                               V vertex)
        Parameters:
        graph - graph to look for descendants in.
        vertex - the vertex to get the descendants of.
        Returns:
        Set of descendants of the vertex in the given graph.