Module org.jgrapht.core

Package org.jgrapht.graph

Class DirectedAcyclicGraph<V,E>

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 type

E - the graph edge type

All Implemented Interfaces:

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

public class DirectedAcyclicGraph<V,E>
extends AbstractBaseGraph<V,E>
implements 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.

Author:

Peter Giles

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	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.

Field Summary

Fields inherited from interface org.jgrapht.Graph

DEFAULT_EDGE_WEIGHT

Constructor Summary

Constructors

Modifier	Constructor	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.
	DirectedAcyclicGraph(Supplier<V> vertexSupplier, Supplier<E> edgeSupplier, boolean weighted, boolean allowMultipleEdges, GraphSpecificsStrategy<V,E> graphSpecificsStrategy)	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.
protected	DirectedAcyclicGraph(Supplier<V> vertexSupplier, 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

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

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

DirectedAcyclicGraph

public DirectedAcyclicGraph(Class<? extends E> edgeClass)

Construct a directed acyclic graph.

Parameters:

edgeClass - the edge class

DirectedAcyclicGraph

public DirectedAcyclicGraph(Supplier<V> vertexSupplier,
                            Supplier<E> edgeSupplier,
                            boolean weighted)

Construct a directed acyclic graph.

Parameters:

vertexSupplier - the vertex supplier

edgeSupplier - the edge supplier

weighted - if true the graph will be weighted, otherwise not

DirectedAcyclicGraph

public DirectedAcyclicGraph(Supplier<V> vertexSupplier,
                            Supplier<E> edgeSupplier,
                            boolean weighted,
                            boolean allowMultipleEdges)

Construct a directed acyclic graph.

Parameters:

vertexSupplier - the vertex supplier

edgeSupplier - the edge supplier

weighted - if true the graph will be weighted, otherwise not

allowMultipleEdges - if true the graph will allow multiple edges, otherwise not

DirectedAcyclicGraph

public DirectedAcyclicGraph(Supplier<V> vertexSupplier,
                            Supplier<E> edgeSupplier,
                            boolean weighted,
                            boolean allowMultipleEdges,
                            GraphSpecificsStrategy<V,E> graphSpecificsStrategy)

Construct a directed acyclic graph.

Parameters:

vertexSupplier - the vertex supplier

edgeSupplier - the edge supplier

weighted - if true the graph will be weighted, otherwise not

allowMultipleEdges - if true the graph will allow multiple edges, otherwise not

graphSpecificsStrategy - strategy for constructing low-level graph specifics

DirectedAcyclicGraph

protected DirectedAcyclicGraph(Supplier<V> vertexSupplier,
                               Supplier<E> edgeSupplier,
                               DirectedAcyclicGraph.VisitedStrategyFactory visitedStrategyFactory,
                               DirectedAcyclicGraph.TopoOrderMap<V> topoOrderMap,
                               boolean weighted)

Construct a directed acyclic graph.

Parameters:

vertexSupplier - the vertex supplier

edgeSupplier - the edge supplier

visitedStrategyFactory - 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(Supplier<V> vertexSupplier,
                               Supplier<E> edgeSupplier,
                               DirectedAcyclicGraph.VisitedStrategyFactory visitedStrategyFactory,
                               DirectedAcyclicGraph.TopoOrderMap<V> topoOrderMap,
                               boolean weighted,
                               boolean allowMultipleEdges)

Construct a directed acyclic graph.

Parameters:

vertexSupplier - the vertex supplier

edgeSupplier - the edge supplier

visitedStrategyFactory - 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

allowMultipleEdges - if true the graph will allow multiple edges, otherwise not

DirectedAcyclicGraph

protected DirectedAcyclicGraph(Supplier<V> vertexSupplier,
                               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 supplier

edgeSupplier - the edge supplier

visitedStrategyFactory - 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

allowMultipleEdges - if true the graph will allow multiple edges, otherwise not

graphSpecificsStrategy - strategy for constructing low-level graph specifics

Method Detail

createBuilder

public static <V,E> GraphBuilder<V,E,? extends DirectedAcyclicGraph<V,E>> createBuilder(Class<? extends E> edgeClass)

Create a builder for this kind of graph.

Type Parameters:

V - the graph vertex type

E - 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(Supplier<E> edgeSupplier)

Create a builder for this kind of graph.

Type Parameters:

V - the graph vertex type

E - 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 (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().

Specified by:

addVertex in interface Graph<V,E>

Overrides:

addVertex in class AbstractBaseGraph<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 interface: Graph

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

Specified by:

addVertex in interface Graph<V,E>

Overrides:

addVertex in class AbstractBaseGraph<V,E>

Parameters:

v - vertex to be added to this graph.

Returns:

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

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.

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 returns 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 edge-multiplicity). 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.

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.

Throws:

IllegalArgumentException - if the vertex is not in the graph

GraphCycleProhibitedException - 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 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 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 returns false. If the edge was added to the graph, returns true.

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 interface Graph<V,E>

Overrides:

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

IllegalArgumentException - if the vertex is not in the graph

GraphCycleProhibitedException - if the vertex would induce a cycle in the graph

See Also:

Graph.addEdge(Object, Object), Graph.getEdgeSupplier()

getAncestors

public 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 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 Iterator<V> iterator()

Returns a topological order iterator.

Specified by:

iterator in interface Iterable<V>

Returns:

a topological order iterator