org.jgrapht.experimental.dag
Class DirectedAcyclicGraph<V,E>

java.lang.Object
  extended by org.jgrapht.graph.AbstractGraph<V,E>
      extended by org.jgrapht.graph.AbstractBaseGraph<V,E>
          extended by org.jgrapht.graph.SimpleDirectedGraph<V,E>
              extended by org.jgrapht.experimental.dag.DirectedAcyclicGraph<V,E>
All Implemented Interfaces:
Serializable, Cloneable, DirectedGraph<V,E>, Graph<V,E>

public class DirectedAcyclicGraph<V,E>
extends SimpleDirectedGraph<V,E>

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
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>
           
 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
DirectedAcyclicGraph(Class<? extends E> arg0)
           
 
Method Summary
 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.
 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.AbstractBaseGraph
clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, 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 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> arg0)
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.

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 - vertex to be added to this graph.
Returns:
true if this graph did not already contain the specified vertex.
See Also:
Graph.addVertex(Object)

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

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.addEdge(Object, Object)

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

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, Object)

removeVertex

public boolean removeVertex(V v)
Description copied from interface: Graph
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.
See Also:
Graph.removeVertex(Object)

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)


Copyright © 2013. All rights reserved.