org.jgrapht.experimental.dag

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 type

E - the graph edge type

All Implemented Interfaces:

Serializable, Cloneable, Iterable<V>, DirectedGraph<V,E>, Graph<V,E>

public 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.

Author:

Peter Giles, gilesp@u.washington.edu

See Also:

Serialized Form

Nested Class Summary

Nested Classes

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 Summary

Constructors

Constructor and Description
DirectedAcyclicGraph(Class<? extends E> edgeClass) Construct a directed acyclic graph.
DirectedAcyclicGraph(EdgeFactory<V,E> ef) Construct a directed acyclic graph.

Method Summary

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.

Methods inherited from class org.jgrapht.graph.SimpleDirectedGraph

builder, builder

Methods inherited from class org.jgrapht.graph.AbstractBaseGraph

clone, containsEdge, containsVertex, createDirectedSpecifics, createUndirectedSpecifics, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSetFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, incomingEdgesOf, inDegreeOf, isAllowingLoops, isAllowingMultipleEdges, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, setEdgeSetFactory, 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 java.lang.Iterable

forEach, spliterator

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

Constructor Detail

DirectedAcyclicGraph

public DirectedAcyclicGraph(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

Method Detail

iterator

public 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 interface 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.

Specified by:

addVertex in interface Graph<V,E>

Overrides:

addVertex in class AbstractBaseGraph<V,E>

Parameters:

v - the vertex to add

Returns:

true if this graph did not already contain the specified vertex.

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 add

addToTop - 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 vertex

toVertex - to vertex

Returns:

null if the edge is already in the graph, else the created edge is returned

Throws:

IllegalArgumentException - If either fromVertex or toVertex is not a member of the graph

DirectedAcyclicGraph.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 to addDagEdge(Object, Object), except an unchecked IllegalArgumentException is thrown if a cycle would have been induced by this edge

Specified by:

addEdge in interface Graph<V,E>

Overrides:

addEdge in class AbstractBaseGraph<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 vertex

toVertex - the to vertex

e - 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)

addEdge

public 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

Specified by:

addEdge in interface Graph<V,E>

Overrides:

addEdge in class AbstractBaseGraph<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 vertex 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.

Specified by:

removeVertex in interface Graph<V,E>

Overrides:

removeVertex in class AbstractBaseGraph<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(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 the Graph.removeVertex(Object) method.

Specified by:

removeAllVertices in interface Graph<V,E>

Overrides:

removeAllVertices in class AbstractGraph<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)

getAncestors

public 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 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.