V
 the graph vertex typeE
 the graph edge typepublic class DirectedAcyclicGraph<V,E> extends SimpleDirectedGraph<V,E> implements 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.
Modifier and Type  Class and Description 

static class 
DirectedAcyclicGraph.CycleFoundException
Exception used in dfsF when a cycle is found

static class 
DirectedAcyclicGraph.Region
Region is an *inclusive* range of indices.

static interface 
DirectedAcyclicGraph.TopoOrderMapping<V>
For performance tuning, an interface for storing the topological ordering

static interface 
DirectedAcyclicGraph.TopoOrderMappingFactory<V>
A factory for
DirectedAcyclicGraph.TopoOrderMapping . 
class 
DirectedAcyclicGraph.TopoVertexMap
For performance and flexibility uses an ArrayList for topological index to vertex mapping,
and a HashMap for vertex to topological index mapping.

static interface 
DirectedAcyclicGraph.Visited
This interface allows specification of a strategy for marking vertices as visited (based on
their topological index, so the vertex type isn't part of the interface).

static class 
DirectedAcyclicGraph.VisitedArrayImpl
This implementation, somewhat to my surprise, is slower than the ArrayList version, probably
due to its reallocation of the underlying array for every topology reorder that is required.

static class 
DirectedAcyclicGraph.VisitedArrayListImpl
This implementation seems to offer the best performance in most cases.

static class 
DirectedAcyclicGraph.VisitedBitSetImpl
This implementation is close to the performance of VisitedArrayListImpl, with 1/8 the memory
usage.

static interface 
DirectedAcyclicGraph.VisitedFactory
Interface for a factory that vends visited implementations

static class 
DirectedAcyclicGraph.VisitedHashSetImpl
This implementation doesn't seem to perform as well, though I can imagine circumstances where
it should shine (lots and lots of vertices).

Constructor and Description 

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

DirectedAcyclicGraph(EdgeFactory<V,E> ef)
Construct a directed acyclic graph.

Modifier and Type  Method and Description 

E 
addDagEdge(V fromVertex,
V toVertex)
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

boolean 
addDagEdge(V fromVertex,
V toVertex,
E e)
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

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 
boolean 
addEdge(V sourceVertex,
V targetVertex,
E edge)
identical to
addDagEdge(Object, Object, Object) , except an unchecked
IllegalArgumentException is thrown if a cycle would have been induced by this edge 
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.

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.

Set<V> 
getAncestors(DirectedAcyclicGraph<V,E> graph,
V vertex) 
Set<V> 
getDescendants(DirectedAcyclicGraph<V,E> graph,
V vertex) 
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.

boolean 
removeAllVertices(Collection<? extends V> arg0)
Removes all the vertices in this graph that are also contained in the specified vertex
collection.

boolean 
removeVertex(V v)
Removes the specified vertex from this graph including all its touching edges if present.

builder, builder
clone, containsEdge, containsVertex, createDirectedSpecifics, createSpecifics, createUndirectedSpecifics, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, incomingEdgesOf, inDegreeOf, isAllowingLoops, isAllowingMultipleEdges, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, setEdgeWeight, vertexSet
assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, toString, toStringFromSets
finalize, getClass, notify, notifyAll, wait, wait, wait
forEach, spliterator
incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf
containsEdge, containsEdge, containsVertex, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, removeAllEdges, removeAllEdges, removeEdge, removeEdge, vertexSet
public DirectedAcyclicGraph(Class<? extends E> edgeClass)
edgeClass
 the edge classpublic DirectedAcyclicGraph(EdgeFactory<V,E> ef)
ef
 the edge factorypublic Iterator<V> iterator()
public boolean addVertex(V v)
public boolean addVertex(V v, boolean addToTop)
v
 the vertex to addaddToTop
 if true the vertex is added at the top of the topological ordering, if false
at the bottompublic E addDagEdge(V fromVertex, V toVertex) throws DirectedAcyclicGraph.CycleFoundException
Adds the given edge and updates the internal topological order for consistency IFF
fromVertex
 from vertextoVertex
 to vertexIllegalArgumentException
 If either fromVertex or toVertex is not a member of the
graphDirectedAcyclicGraph.CycleFoundException
 if the edge would induce a cycle in the graphGraph.addEdge(Object, Object, Object)
public E addEdge(V sourceVertex, V targetVertex)
addDagEdge(Object, Object)
, except an unchecked
IllegalArgumentException
is thrown if a cycle would have been induced by this edgeaddEdge
in interface Graph<V,E>
addEdge
in class AbstractBaseGraph<V,E>
sourceVertex
 source vertex of the edge.targetVertex
 target vertex of the edge.
null
.Graph.getEdgeFactory()
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
fromVertex
 the from vertextoVertex
 the to vertexe
 the edgeDirectedAcyclicGraph.CycleFoundException
 if adding an edge (fromVertex, toVertex) to the graph would
induce a cycle.Graph.addEdge(Object, Object, Object)
public boolean addEdge(V sourceVertex, V targetVertex, E edge)
addDagEdge(Object, Object, Object)
, except an unchecked
IllegalArgumentException
is thrown if a cycle would have been induced by this edgeaddEdge
in interface Graph<V,E>
addEdge
in class AbstractBaseGraph<V,E>
sourceVertex
 source vertex of the edge.targetVertex
 target vertex of the edge.edge
 edge to be added to this graph.Graph.addEdge(Object, Object)
,
Graph.getEdgeFactory()
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 boolean removeAllVertices(Collection<? extends V> arg0)
Graph
Graph.removeVertex(Object)
method.removeAllVertices
in interface Graph<V,E>
removeAllVertices
in class AbstractGraph<V,E>
arg0
 vertices to be removed from this graph.Graph.removeAllVertices(Collection)
public Set<V> getAncestors(DirectedAcyclicGraph<V,E> graph, V vertex)
graph
 graph to look for ancestors in.vertex
 the vertex to get the ancestors of.Set
of ancestors of the vertex in the given graph.Copyright © 2017. All rights reserved.