- 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.
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
DirectedAcyclicGraph.CycleFoundException
Exception used in dfsF when a cycle is foundprotected static class
DirectedAcyclicGraph.Region
An inclusive range of indices: [start, finish].private class
DirectedAcyclicGraph.TopoComparator
Comparator for vertices based on their topological orderingprivate class
DirectedAcyclicGraph.TopoIterator
An iterator which follows topological orderprotected 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 Modifier and Type Field Description private int
maxTopoIndex
private int
minTopoIndex
private static long
serialVersionUID
private java.util.Comparator<V>
topoComparator
private long
topoModCount
private DirectedAcyclicGraph.TopoOrderMap<V>
topoOrderMap
private DirectedAcyclicGraph.VisitedStrategyFactory
visitedStrategyFactory
The visited strategy factory to use.-
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.DirectedAcyclicGraph(java.util.function.Supplier<V> vertexSupplier, java.util.function.Supplier<E> edgeSupplier, boolean weighted, boolean allowMultipleEdges, GraphSpecificsStrategy<V,E> graphSpecificsStrategy)
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.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, GraphSpecificsStrategy<V,E> graphSpecificsStrategy)
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.private void
dfsB(V initialVertex, java.util.Set<V> db, DirectedAcyclicGraph.VisitedStrategy visited, DirectedAcyclicGraph.Region affectedRegion)
Depth first search backward, building up the set (db) of back-connected vertices in the Affected Regionprivate void
dfsF(V initialVertex, java.util.Set<V> df, DirectedAcyclicGraph.VisitedStrategy visited, DirectedAcyclicGraph.Region affectedRegion)
Depth first search forward, building up the set (df) of forward-connected vertices in the Affected Regionjava.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.private void
reorder(java.util.Set<V> df, java.util.Set<V> db, DirectedAcyclicGraph.VisitedStrategy visited)
private void
updateDag(V sourceVertex, V targetVertex)
Update as if a new edge is added.-
Methods inherited from class org.jgrapht.graph.AbstractBaseGraph
clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getEdgeWeight, getType, getVertexSupplier, incomingEdgesOf, inDegreeOf, iterables, 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
-
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
topoComparator
private final java.util.Comparator<V> topoComparator
-
topoOrderMap
private final DirectedAcyclicGraph.TopoOrderMap<V> topoOrderMap
-
maxTopoIndex
private int maxTopoIndex
-
minTopoIndex
private int minTopoIndex
-
topoModCount
private transient long topoModCount
-
visitedStrategyFactory
private final DirectedAcyclicGraph.VisitedStrategyFactory visitedStrategyFactory
The visited strategy factory to use. Subclasses can change this.
-
-
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
public DirectedAcyclicGraph(java.util.function.Supplier<V> vertexSupplier, java.util.function.Supplier<E> edgeSupplier, boolean weighted, boolean allowMultipleEdges, GraphSpecificsStrategy<V,E> graphSpecificsStrategy)
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 notgraphSpecificsStrategy
- strategy for constructing low-level graph specifics
-
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
-
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, GraphSpecificsStrategy<V,E> graphSpecificsStrategy)
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 notgraphSpecificsStrategy
- strategy for constructing low-level graph specifics
-
-
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 edge-multiplicity. 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 edge-multiplicity). 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 vertex is not in the graphGraphCycleProhibitedException
- if the vertex 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 edge-multiplicity. 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 vertex is not in the graphGraphCycleProhibitedException
- if the vertex 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 interfacejava.lang.Iterable<V>
- Returns:
- a topological order iterator
-
updateDag
private void updateDag(V sourceVertex, V targetVertex) throws DirectedAcyclicGraph.CycleFoundException
Update as if a new edge is added.- Parameters:
sourceVertex
- the source vertextargetVertex
- the target vertex- Throws:
DirectedAcyclicGraph.CycleFoundException
-
dfsF
private void dfsF(V initialVertex, java.util.Set<V> df, DirectedAcyclicGraph.VisitedStrategy visited, DirectedAcyclicGraph.Region affectedRegion) throws DirectedAcyclicGraph.CycleFoundException
Depth first search forward, building up the set (df) of forward-connected vertices in the Affected Region- Parameters:
initialVertex
- the vertex being visiteddf
- the set we are populating with forward connected vertices in the Affected Regionvisited
- a simple data structure that lets us know if we already visited a node with a given topo index- Throws:
DirectedAcyclicGraph.CycleFoundException
- if a cycle is discovered
-
dfsB
private void dfsB(V initialVertex, java.util.Set<V> db, DirectedAcyclicGraph.VisitedStrategy visited, DirectedAcyclicGraph.Region affectedRegion)
Depth first search backward, building up the set (db) of back-connected vertices in the Affected Region- Parameters:
initialVertex
- the vertex being visiteddb
- the set we are populating with back-connected vertices in the ARvisited
-
-
reorder
private void reorder(java.util.Set<V> df, java.util.Set<V> db, DirectedAcyclicGraph.VisitedStrategy visited)
-
-