V
 the graph vertex typeE
 the graph edge typepublic class DirectedAcyclicGraph<V,E> extends AbstractBaseGraph<V,E> implements Iterable<V>
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.
Modifier and Type  Class and 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 an
ArrayList . 
protected static class 
DirectedAcyclicGraph.VisitedBitSetImpl
A visited strategy which uses a
BitSet . 
protected static class 
DirectedAcyclicGraph.VisitedHashSetImpl
A visited strategy using a
HashSet . 
protected static interface 
DirectedAcyclicGraph.VisitedStrategy
A strategy for marking vertices as visited.

protected static interface 
DirectedAcyclicGraph.VisitedStrategyFactory
A visited strategy factory.

DEFAULT_EDGE_WEIGHT
Modifier  Constructor and Description 


DirectedAcyclicGraph(Class<? extends E> edgeClass)
Construct a directed acyclic graph.


DirectedAcyclicGraph(Supplier<V> vertexSupplier,
Supplier<E> edgeSupplier,
boolean weighted)
Construct a directed acyclic graph.


DirectedAcyclicGraph(Supplier<V> vertexSupplier,
Supplier<E> edgeSupplier,
boolean weighted,
boolean allowMultipleEdges)
Construct a directed acyclic graph.

protected 
DirectedAcyclicGraph(Supplier<V> vertexSupplier,
Supplier<E> edgeSupplier,
DirectedAcyclicGraph.VisitedStrategyFactory visitedStrategyFactory,
DirectedAcyclicGraph.TopoOrderMap<V> topoOrderMap,
boolean weighted)
Construct a directed acyclic graph.

protected 
DirectedAcyclicGraph(Supplier<V> vertexSupplier,
Supplier<E> edgeSupplier,
DirectedAcyclicGraph.VisitedStrategyFactory visitedStrategyFactory,
DirectedAcyclicGraph.TopoOrderMap<V> topoOrderMap,
boolean weighted,
boolean allowMultipleEdges)
Construct a directed acyclic graph.

Modifier and Type  Method and 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(Class<? extends E> edgeClass)
Create a builder for this kind of graph.

static <V,E> GraphBuilder<V,E,? extends DirectedAcyclicGraph<V,E>> 
createBuilder(Supplier<E> edgeSupplier)
Create a builder for this kind of graph.

Set<V> 
getAncestors(V vertex)
Get the ancestors of a vertex.

Set<V> 
getDescendants(V vertex)
Get the descendants of a vertex.

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.

clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getEdgeWeight, getType, getVertexSupplier, incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, setEdgeSupplier, setEdgeWeight, setVertexSupplier, vertexSet
assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets
finalize, getClass, notify, notifyAll, wait, wait, wait
forEach, spliterator
containsEdge, removeAllEdges, removeAllEdges, removeAllVertices, setEdgeWeight
public DirectedAcyclicGraph(Class<? extends E> edgeClass)
edgeClass
 the edge classpublic DirectedAcyclicGraph(Supplier<V> vertexSupplier, Supplier<E> edgeSupplier, boolean weighted)
vertexSupplier
 the vertex supplieredgeSupplier
 the edge supplierweighted
 if true the graph will be weighted, otherwise notpublic DirectedAcyclicGraph(Supplier<V> vertexSupplier, Supplier<E> edgeSupplier, boolean weighted, boolean allowMultipleEdges)
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 notprotected DirectedAcyclicGraph(Supplier<V> vertexSupplier, Supplier<E> edgeSupplier, DirectedAcyclicGraph.VisitedStrategyFactory visitedStrategyFactory, DirectedAcyclicGraph.TopoOrderMap<V> topoOrderMap, boolean weighted)
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 notprotected DirectedAcyclicGraph(Supplier<V> vertexSupplier, Supplier<E> edgeSupplier, DirectedAcyclicGraph.VisitedStrategyFactory visitedStrategyFactory, DirectedAcyclicGraph.TopoOrderMap<V> topoOrderMap, boolean weighted, boolean allowMultipleEdges)
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 notpublic static <V,E> GraphBuilder<V,E,? extends DirectedAcyclicGraph<V,E>> createBuilder(Class<? extends E> edgeClass)
V
 the graph vertex typeE
 the graph edge typeedgeClass
 class on which to base factory for edgespublic static <V,E> GraphBuilder<V,E,? extends DirectedAcyclicGraph<V,E>> createBuilder(Supplier<E> edgeSupplier)
V
 the graph vertex typeE
 the graph edge typeedgeSupplier
 edge supplier for the edgespublic V addVertex()
Graph
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()
.
addVertex
in interface Graph<V,E>
addVertex
in class AbstractBaseGraph<V,E>
Graph.getVertexSupplier()
public boolean addVertex(V v)
AbstractBaseGraph
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.public boolean removeVertex(V v)
AbstractBaseGraph
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
.
removeVertex
in interface Graph<V,E>
removeVertex
in class AbstractBaseGraph<V,E>
v
 vertex to be removed from this graph, if present.true
if the graph contained the specified vertex; false
otherwise.public E addEdge(V sourceVertex, V targetVertex)
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 edgemultiplicity). 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.
addEdge
in interface Graph<V,E>
addEdge
in class AbstractBaseGraph<V,E>
sourceVertex
 source vertex of the edge.targetVertex
 target vertex of the edge.
null
.IllegalArgumentException
 if the edge would induce a cycle in the graphGraph.getEdgeSupplier()
public boolean addEdge(V sourceVertex, V targetVertex, E e)
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 edgemultiplicity. 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.
addEdge
in interface Graph<V,E>
addEdge
in class AbstractBaseGraph<V,E>
sourceVertex
 source vertex of the edge.targetVertex
 target vertex of the edge.e
 edge to be added to this graph.IllegalArgumentException
 if the edge would induce a cycle in the graphGraph.addEdge(Object, Object)
,
Graph.getEdgeSupplier()
public Set<V> getAncestors(V vertex)
vertex
 the vertex to get the ancestors ofSet
of ancestors of a vertexpublic Set<V> getDescendants(V vertex)
vertex
 the vertex to get the descendants ofSet
of descendants of a vertexCopyright © 2020. All rights reserved.