 java.lang.Object

 org.jgrapht.graph.AbstractGraph<V,E>

 org.jgrapht.graph.AbstractBaseGraph<V,E>

 org.jgrapht.graph.DirectedAcyclicGraph<V,E>

 Type Parameters:
V
 the graph vertex typeE
 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


Nested Class Summary
Nested Classes Modifier and Type Class Description protected static class
DirectedAcyclicGraph.Region
An inclusive range of indices: [start, finish].protected static interface
DirectedAcyclicGraph.TopoOrderMap<V>
An interface for storing the topological ordering.protected static class
DirectedAcyclicGraph.TopoVertexBiMap<V>
A dual map implementation of the topological order map.protected class
DirectedAcyclicGraph.TopoVertexMap
An implementation of the topological order map which for performance and flexibility uses an ArrayList for topological index to vertex mapping, and a HashMap for vertex to topological index mapping.protected static class
DirectedAcyclicGraph.VisitedArrayImpl
A visited strategy using an array.protected static class
DirectedAcyclicGraph.VisitedArrayListImpl
A visited strategy using anArrayList
.protected static class
DirectedAcyclicGraph.VisitedBitSetImpl
A visited strategy which uses aBitSet
.protected static class
DirectedAcyclicGraph.VisitedHashSetImpl
A visited strategy using aHashSet
.protected static interface
DirectedAcyclicGraph.VisitedStrategy
A strategy for marking vertices as visited.protected static interface
DirectedAcyclicGraph.VisitedStrategyFactory
A visited strategy factory.

Field Summary

Fields inherited from interface org.jgrapht.Graph
DEFAULT_EDGE_WEIGHT


Constructor Summary
Constructors Modifier Constructor Description DirectedAcyclicGraph(java.lang.Class<? extends E> edgeClass)
Construct a directed acyclic graph.DirectedAcyclicGraph(java.util.function.Supplier<V> vertexSupplier, java.util.function.Supplier<E> edgeSupplier, boolean weighted)
Construct a directed acyclic graph.DirectedAcyclicGraph(java.util.function.Supplier<V> vertexSupplier, java.util.function.Supplier<E> edgeSupplier, boolean weighted, boolean allowMultipleEdges)
Construct a directed acyclic graph.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.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.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.boolean
addEdge(V sourceVertex, V targetVertex, E e)
Adds the specified edge to this graph, going from the source vertex to the target vertex.V
addVertex()
Creates a new vertex in this graph and returns it.boolean
addVertex(V v)
Adds the specified vertex to this graph if not already present.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.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.java.util.Set<V>
getAncestors(V vertex)
Get the ancestors of a vertex.java.util.Set<V>
getDescendants(V vertex)
Get the descendants of a vertex.java.util.Iterator<V>
iterator()
Returns a topological order iterator.boolean
removeVertex(V v)
Removes the specified vertex from this graph including all its touching edges if present.
Methods inherited from class org.jgrapht.graph.AbstractBaseGraph
clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getEdgeWeight, getType, getVertexSupplier, incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, setEdgeSupplier, setEdgeWeight, setVertexSupplier, vertexSet

Methods inherited from class org.jgrapht.graph.AbstractGraph
assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.jgrapht.Graph
containsEdge, removeAllEdges, removeAllEdges, removeAllVertices, setEdgeWeight




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 supplieredgeSupplier
 the edge supplierweighted
 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 supplieredgeSupplier
 the edge supplierweighted
 if true the graph will be weighted, otherwise notallowMultipleEdges
 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 supplieredgeSupplier
 the edge suppliervisitedStrategyFactory
 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 supplieredgeSupplier
 the edge suppliervisitedStrategyFactory
 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 notallowMultipleEdges
 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 typeE
 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 typeE
 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 (seeGraph.getVertexSupplier()
). For the new vertex to be addedv
must not be equal to any other vertex in the graph. More formally, the graph must not contain any vertexv2
such thatv2.equals(v)
. If suchv2
is found then the newly created vertexv
is abandoned, the method leaves this graph unchanged and throws anIllegalArgumentException
.If the underlying graph implementation's
Graph.getVertexSupplier()
returnsnull
, then this method cannot create vertices and throws anUnsupportedOperationException
.Care must also be taken when interchanging calls to methods
Graph.addVertex(Object)
andGraph.addVertex()
. In such a case the user must make sure never to add vertices in the graph using methodGraph.addVertex(Object)
, which are going to be returned in the future by the supplied vertex supplier. Such a sequence will result into anIllegalArgumentException
when calling methodGraph.addVertex()
. Specified by:
addVertex
in interfaceGraph<V,E>
 Overrides:
addVertex
in classAbstractBaseGraph<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 vertexu
such thatu.equals(v)
. If this graph already contains such vertex, the call leaves this graph unchanged and returnsfalse
. In combination with the restriction on constructors, this ensures that graphs never contain duplicate vertices.

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 vertexu
such thatu.equals(v)
, the call removes all edges that touchu
and then removesu
itself. If no suchu
is found, the call leaves the graph unchanged. Returnstrue
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
returnsfalse
. Specified by:
removeVertex
in interfaceGraph<V,E>
 Overrides:
removeVertex
in classAbstractBaseGraph<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 edgemultiplicity. In such cases, if the graph already contains an edge from the specified source to the specified target, then this method does not change the graph and returnsnull
.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 (seeGraph.getEdgeSupplier()
). For the new edge to be addede
must not be equal to any other edge the graph (even if the graph allows edgemultiplicity). More formally, the graph must not contain any edgee2
such thate2.equals(e)
. If suche2
is found then the newly created edgee
is abandoned, the method leaves this graph unchanged and returnsnull
.If the underlying graph implementation's
Graph.getEdgeSupplier()
returnsnull
, then this method cannot create edges and throws anUnsupportedOperationException
.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 interfaceGraph<V,E>
 Overrides:
addEdge
in classAbstractBaseGraph<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 edgee2
such thate2.equals(e)
. If this graph already contains such an edge, the call leaves this graph unchanged and returnsfalse
. Some graphs do not allow edgemultiplicity. In such cases, if the graph already contains an edge from the specified source to the specified target, then this method does not change the graph and returnsfalse
. If the edge was added to the graph, returnstrue
.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 interfaceGraph<V,E>
 Overrides:
addEdge
in classAbstractBaseGraph<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

