Class DirectedAcyclicGraph<V,E>
- java.lang.Object
-
- org.jgrapht.graph.AbstractGraph<V,E>
-
- org.jgrapht.graph.AbstractBaseGraph<V,E>
-
- org.jgrapht.graph.SimpleDirectedGraph<V,E>
-
- org.jgrapht.experimental.dag.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>
,DirectedGraph<V,E>
,Graph<V,E>
public class DirectedAcyclicGraph<V,E> extends SimpleDirectedGraph<V,E> implements java.lang.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.
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
DirectedAcyclicGraph.CycleFoundException
Exception used in dfsF when a cycle is foundstatic class
DirectedAcyclicGraph.Region
Region is an *inclusive* range of indices.private static class
DirectedAcyclicGraph.TopoComparator<V>
Note, this is a lazy and incomplete implementation, with assumptions that inputs are in the given topoIndexMapprivate class
DirectedAcyclicGraph.TopoIterator
iterator which follows topological orderstatic interface
DirectedAcyclicGraph.TopoOrderMapping<V>
For performance tuning, an interface for storing the topological orderingstatic interface
DirectedAcyclicGraph.TopoOrderMappingFactory<V>
A factory forDirectedAcyclicGraph.TopoOrderMapping
.private class
DirectedAcyclicGraph.TopoVertexBiMap
a dual HashMap implementationclass
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 implementationsstatic 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).
-
Field Summary
Fields Modifier and Type Field Description private int
maxTopoIndex
private int
minTopoIndex
private static long
serialVersionUID
private DirectedAcyclicGraph.TopoComparator<V>
topoComparator
private long
topologyUpdateCount
private DirectedAcyclicGraph.TopoOrderMappingFactory<V>
topoOrderFactory
Pluggable TopoOrderMappingFactory implementationprivate DirectedAcyclicGraph.TopoOrderMapping<V>
topoOrderMap
private DirectedAcyclicGraph.VisitedFactory
visitedFactory
Pluggable VisitedFactory implementation
-
Constructor Summary
Constructors Constructor Description DirectedAcyclicGraph(java.lang.Class<? extends E> edgeClass)
Construct a directed acyclic graph.DirectedAcyclicGraph(java.lang.Class<? extends E> arg0, DirectedAcyclicGraph.VisitedFactory visitedFactory, DirectedAcyclicGraph.TopoOrderMappingFactory<V> topoOrderFactory)
DirectedAcyclicGraph(EdgeFactory<V,E> ef)
Construct a directed acyclic graph.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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 graphboolean
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 graphE
addEdge(V sourceVertex, V targetVertex)
identical toaddDagEdge(Object, Object)
, except an uncheckedIllegalArgumentException
is thrown if a cycle would have been induced by this edgeboolean
addEdge(V sourceVertex, V targetVertex, E edge)
identical toaddDagEdge(Object, Object, Object)
, except an uncheckedIllegalArgumentException
is thrown if a cycle would have been induced by this edgeboolean
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.private void
dfsB(V vertex, java.util.Set<V> db, DirectedAcyclicGraph.Visited visited, DirectedAcyclicGraph.Region affectedRegion)
Depth first search backward, building up the set (db) of back-connected vertices in the Affected Regionprivate void
dfsF(V vertex, java.util.Set<V> df, DirectedAcyclicGraph.Visited 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(DirectedAcyclicGraph<V,E> graph, V vertex)
java.util.Set<V>
getDescendants(DirectedAcyclicGraph<V,E> graph, V vertex)
private void
initialize()
set the topoOrderMap based on the current factory, and create the comparator;java.util.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(java.util.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.private void
reorder(java.util.Set<V> df, java.util.Set<V> db, DirectedAcyclicGraph.Visited visited)
private void
updateDag(V fromVertex, V toVertex)
-
Methods inherited from class org.jgrapht.graph.SimpleDirectedGraph
builder, builder
-
Methods inherited from class org.jgrapht.graph.AbstractBaseGraph
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
-
Methods inherited from class org.jgrapht.graph.AbstractGraph
assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, toString, toStringFromSets
-
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface org.jgrapht.DirectedGraph
incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf
-
Methods inherited from interface org.jgrapht.Graph
containsEdge, containsEdge, containsVertex, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, removeAllEdges, removeAllEdges, removeEdge, removeEdge, vertexSet
-
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
topoComparator
private DirectedAcyclicGraph.TopoComparator<V> topoComparator
-
topoOrderMap
private DirectedAcyclicGraph.TopoOrderMapping<V> topoOrderMap
-
maxTopoIndex
private int maxTopoIndex
-
minTopoIndex
private int minTopoIndex
-
topologyUpdateCount
private long topologyUpdateCount
-
visitedFactory
private DirectedAcyclicGraph.VisitedFactory visitedFactory
Pluggable VisitedFactory implementation
-
topoOrderFactory
private DirectedAcyclicGraph.TopoOrderMappingFactory<V> topoOrderFactory
Pluggable TopoOrderMappingFactory implementation
-
-
Constructor Detail
-
DirectedAcyclicGraph
public DirectedAcyclicGraph(java.lang.Class<? extends E> edgeClass)
Construct a directed acyclic graph.- Parameters:
edgeClass
- the edge class
-
DirectedAcyclicGraph
public DirectedAcyclicGraph(EdgeFactory<V,E> ef)
Construct a directed acyclic graph.- Parameters:
ef
- the edge factory
-
DirectedAcyclicGraph
DirectedAcyclicGraph(java.lang.Class<? extends E> arg0, DirectedAcyclicGraph.VisitedFactory visitedFactory, DirectedAcyclicGraph.TopoOrderMappingFactory<V> topoOrderFactory)
-
-
Method Detail
-
initialize
private void initialize()
set the topoOrderMap based on the current factory, and create the comparator;
-
iterator
public java.util.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.- Specified by:
iterator
in interfacejava.lang.Iterable<V>
- Returns:
- an iterator that will traverse the graph in topological order
-
addVertex
public 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.
-
addVertex
public 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. This may provide useful optimizations for merging DirectedAcyclicGraphs that become connected.- Parameters:
v
- the vertex to addaddToTop
- if true the vertex is added at the top of the topological ordering, if false at the bottom- Returns:
- whether new vertex was added
-
addDagEdge
public E addDagEdge(V fromVertex, V toVertex) throws DirectedAcyclicGraph.CycleFoundException
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
- Parameters:
fromVertex
- from vertextoVertex
- to vertex- Returns:
- null if the edge is already in the graph, else the created edge is returned
- Throws:
java.lang.IllegalArgumentException
- If either fromVertex or toVertex is not a member of the graphDirectedAcyclicGraph.CycleFoundException
- if the edge would induce a cycle in the graph- See Also:
Graph.addEdge(Object, Object, Object)
-
addEdge
public E addEdge(V sourceVertex, V targetVertex)
identical toaddDagEdge(Object, Object)
, except an uncheckedIllegalArgumentException
is thrown if a cycle would have been induced by this edge- 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
. - See Also:
Graph.getEdgeFactory()
-
addDagEdge
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
- 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
- Parameters:
fromVertex
- the from vertextoVertex
- the to vertexe
- the edge- Returns:
- true if the edge was added to the graph
- Throws:
DirectedAcyclicGraph.CycleFoundException
- if adding an edge (fromVertex, toVertex) to the graph would induce a cycle.- See Also:
Graph.addEdge(Object, Object, Object)
-
updateDag
private void updateDag(V fromVertex, V toVertex) throws DirectedAcyclicGraph.CycleFoundException
-
addEdge
public boolean addEdge(V sourceVertex, V targetVertex, E edge)
identical toaddDagEdge(Object, Object, Object)
, except an uncheckedIllegalArgumentException
is thrown if a cycle would have been induced by this edge- 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.edge
- edge to be added to this graph.- Returns:
- true if this graph did not already contain the specified edge.
- See Also:
Graph.addEdge(Object, Object)
,Graph.getEdgeFactory()
-
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. 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
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.
-
removeAllVertices
public boolean removeAllVertices(java.util.Collection<? extends V> arg0)
Description copied from interface:Graph
Removes all the vertices in this graph that are also contained in the specified vertex collection. After this call returns, this graph will contain no vertices in common with the specified vertices. This method will invoke theGraph.removeVertex(Object)
method.- Specified by:
removeAllVertices
in interfaceGraph<V,E>
- Overrides:
removeAllVertices
in classAbstractGraph<V,E>
- Parameters:
arg0
- vertices to be removed from this graph.- Returns:
- true if this graph changed as a result of the call
- See Also:
Graph.removeAllVertices(Collection)
-
dfsF
private void dfsF(V vertex, java.util.Set<V> df, DirectedAcyclicGraph.Visited 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:
vertex
- 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 vertex, java.util.Set<V> db, DirectedAcyclicGraph.Visited visited, DirectedAcyclicGraph.Region affectedRegion)
Depth first search backward, building up the set (db) of back-connected vertices in the Affected Region- Parameters:
vertex
- 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.Visited visited)
-
getAncestors
public java.util.Set<V> getAncestors(DirectedAcyclicGraph<V,E> graph, V vertex)
- Parameters:
graph
- graph to look for ancestors in.vertex
- the vertex to get the ancestors of.- Returns:
Set
of ancestors of the vertex in the given graph.
-
getDescendants
public java.util.Set<V> getDescendants(DirectedAcyclicGraph<V,E> graph, V vertex)
- Parameters:
graph
- graph to look for descendants in.vertex
- the vertex to get the descendants of.- Returns:
Set
of descendants of the vertex in the given graph.
-
-