Package org.jgrapht.graph

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>, Graph<V,​E>
    public class DirectedAcyclicGraph<V,​E>
extends AbstractBaseGraph<V,​E>
implements java.lang.Iterable<V>
    A directed acyclic graph (DAG).

    Implements a DAG that can be modified (vertices & edges added and removed), is guaranteed to remain acyclic, and provides fast topological order iteration. An attempt to add an edge which would induce a cycle throws an IllegalArgumentException.

    This is done using a dynamic topological sort which is based on the algorithm described in "David J. Pearce & Paul H. J. Kelly. A dynamic topological sort algorithm for directed acyclic graphs. Journal of Experimental Algorithmics, 11, 2007." (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 hash maps, which will have some effects on the runtime, but also allow for vertex addition and removal. This storage mechanism can be adjusted by subclasses.

    The complexity of adding a new edge in the graph depends on the number of edges incident to the "affected region", and should in general be faster than recomputing the whole topological ordering from scratch. For details about the complexity parameters and running times, see the previously mentioned paper.

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

    Author:
    Peter Giles
    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​(java.util.function.Supplier<V> vertexSupplier,
                            java.util.function.Supplier<E> edgeSupplier,
                            boolean weighted)
        Construct a directed acyclic graph.
        Parameters:
        vertexSupplier - the vertex supplier
        edgeSupplier - the edge supplier
        weighted - if true the graph will be weighted, otherwise not

      • DirectedAcyclicGraph

        public DirectedAcyclicGraph​(java.util.function.Supplier<V> vertexSupplier,
                            java.util.function.Supplier<E> edgeSupplier,
                            boolean weighted,
                            boolean allowMultipleEdges)
        Construct a directed acyclic graph.
        Parameters:
        vertexSupplier - the vertex supplier
        edgeSupplier - the edge supplier
        weighted - if true the graph will be weighted, otherwise not
        allowMultipleEdges - if true the graph will allow multiple edges, otherwise not

      • DirectedAcyclicGraph

        protected DirectedAcyclicGraph​(java.util.function.Supplier<V> vertexSupplier,
                               java.util.function.Supplier<E> edgeSupplier,
                               DirectedAcyclicGraph.VisitedStrategyFactory visitedStrategyFactory,
                               DirectedAcyclicGraph.TopoOrderMap<V> topoOrderMap,
                               boolean weighted)
        Construct a directed acyclic graph.
        Parameters:
        vertexSupplier - the vertex supplier
        edgeSupplier - the edge supplier
        visitedStrategyFactory - the visited strategy factory. Subclasses can change this implementation to adjust the performance tradeoffs.
        topoOrderMap - the topological order map. For performance reasons, subclasses can change the way this class stores the topological order.
        weighted - if true the graph will be weighted, otherwise not

      • DirectedAcyclicGraph

        protected DirectedAcyclicGraph​(java.util.function.Supplier<V> vertexSupplier,
                               java.util.function.Supplier<E> edgeSupplier,
                               DirectedAcyclicGraph.VisitedStrategyFactory visitedStrategyFactory,
                               DirectedAcyclicGraph.TopoOrderMap<V> topoOrderMap,
                               boolean weighted,
                               boolean allowMultipleEdges)
        Construct a directed acyclic graph.
        Parameters:
        vertexSupplier - the vertex supplier
        edgeSupplier - the edge supplier
        visitedStrategyFactory - the visited strategy factory. Subclasses can change this implementation to adjust the performance tradeoffs.
        topoOrderMap - the topological order map. For performance reasons, subclasses can change the way this class stores the topological order.
        weighted - if true the graph will be weighted, otherwise not
        allowMultipleEdges - if true the graph will allow multiple edges, otherwise not

    • Method Detail

      • createBuilder

        public static <V,​E> GraphBuilder<V,​E,​? extends DirectedAcyclicGraph<V,​E>> createBuilder​(java.lang.Class<? extends E> edgeClass)
        Create a builder for this kind of graph.
        Type Parameters:
        V - the graph vertex type
        E - the graph edge type
        Parameters:
        edgeClass - class on which to base factory for edges
        Returns:
        a builder for this kind of graph

      • createBuilder

        public static <V,​E> GraphBuilder<V,​E,​? extends DirectedAcyclicGraph<V,​E>> createBuilder​(java.util.function.Supplier<E> edgeSupplier)
        Create a builder for this kind of graph.
        Type Parameters:
        V - the graph vertex type
        E - the graph edge type
        Parameters:
        edgeSupplier - edge supplier for the edges
        Returns:
        a builder for this kind of graph

      • addVertex

        public V addVertex()
        Description copied from interface: Graph
        Creates a new vertex in this graph and returns it.

        This method creates the new vertex v using this graph's vertex supplier (see Graph.getVertexSupplier()). For the new vertex to be added v must not be equal to any other vertex in the graph. More formally, the graph must not contain any vertex v2 such that v2.equals(v). If such v2 is found then the newly created vertex v is abandoned, the method leaves this graph unchanged and throws an IllegalArgumentException.

        If the underlying graph implementation's Graph.getVertexSupplier() returns null, then this method cannot create vertices and throws an UnsupportedOperationException.

        Care must also be taken when interchanging calls to methods Graph.addVertex(Object) and Graph.addVertex(). In such a case the user must make sure never to add vertices in the graph using method Graph.addVertex(Object), which are going to be returned in the future by the supplied vertex supplier. Such a sequence will result into an IllegalArgumentException when calling method Graph.addVertex().

        Specified by:
        addVertex in interface Graph<V,​E>
        Overrides:
        addVertex in class AbstractBaseGraph<V,​E>
        Returns:
        The newly created vertex if added to the graph.
        See Also:
        Graph.getVertexSupplier()

      • addVertex

        public boolean addVertex​(V v)
        Description copied from class: AbstractBaseGraph
        Adds the specified vertex to this graph if not already present. More formally, adds the specified vertex, v, to this graph if this graph contains no vertex u such that u.equals(v). If this graph already contains such vertex, the call leaves this graph unchanged and returns false. In combination with the restriction on constructors, this ensures that graphs never contain duplicate vertices.
        Specified by:
        addVertex in interface Graph<V,​E>
        Overrides:
        addVertex in class AbstractBaseGraph<V,​E>
        Parameters:
        v - vertex to be added to this graph.
        Returns:
        true if this graph did not already contain the specified vertex.

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

      • addEdge

        public E addEdge​(V sourceVertex,
                 V targetVertex)
        Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge. Some graphs do not allow edge-multiplicity. In such cases, if the graph already contains an edge from the specified source to the specified target, than this method does not change the graph and returns null.

        The source and target vertices must already be contained in this graph. If they are not found in graph IllegalArgumentException is thrown.

        This method creates the new edge e using this graph's edge supplier (see Graph.getEdgeSupplier()). For the new edge to be added e must not be equal to any other edge the graph (even if the graph allows edge-multiplicity). More formally, the graph must not contain any edge e2 such that e2.equals(e). If such e2 is found then the newly created edge e is abandoned, the method leaves this graph unchanged and returns null.

        If the underlying graph implementation's Graph.getEdgeSupplier() returns null, then this method cannot create edges and throws an UnsupportedOperationException.

        The complexity of adding a new edge in the graph depends on the number of edges incident to the "affected region", and should in general be faster than recomputing the whole topological ordering from scratch.

        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.
        Throws:
        java.lang.IllegalArgumentException - if the edge would induce a cycle in the graph
        See Also:
        Graph.getEdgeSupplier()

      • addEdge

        public boolean addEdge​(V sourceVertex,
                       V targetVertex,
                       E e)
        Adds the specified edge to this graph, going from the source vertex to the target vertex. More formally, adds the specified edge, e, to this graph if this graph contains no edge e2 such that e2.equals(e). If this graph already contains such an edge, the call leaves this graph unchanged and returns false. Some graphs do not allow edge-multiplicity. In such cases, if the graph already contains an edge from the specified source to the specified target, than this method does not change the graph and returns false. If the edge was added to the graph, returns true.

        The source and target vertices must already be contained in this graph. If they are not found in graph IllegalArgumentException is thrown.

        The complexity of adding a new edge in the graph depends on the number of edges incident to the "affected region", and should in general be faster than recomputing the whole topological ordering from scratch.

        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.
        e - edge to be added to this graph.
        Returns:
        true if this graph did not already contain the specified edge.
        Throws:
        java.lang.IllegalArgumentException - if the edge would induce a cycle in the graph
        See Also:
        Graph.addEdge(Object, Object), Graph.getEdgeSupplier()

      • getAncestors

        public java.util.Set<V> getAncestors​(V vertex)
        Get the ancestors of a vertex.
        Parameters:
        vertex - the vertex to get the ancestors of
        Returns:
        Set of ancestors of a vertex

      • getDescendants

        public java.util.Set<V> getDescendants​(V vertex)
        Get the descendants of a vertex.
        Parameters:
        vertex - the vertex to get the descendants of
        Returns:
        Set of descendants of a vertex

      • iterator

        public java.util.Iterator<V> iterator()
        Returns a topological order iterator.
        Specified by:
        iterator in interface java.lang.Iterable<V>
        Returns:
        a topological order iterator