Package org.jgrapht.alg
Class TransitiveClosure
- java.lang.Object
-
- org.jgrapht.alg.TransitiveClosure
-
public class TransitiveClosure extends java.lang.Object
Constructs the transitive closure of the input graph.- Since:
- May 5, 2007
-
-
Field Summary
Fields Modifier and Type Field Description static TransitiveClosure
INSTANCE
Singleton instance.
-
Constructor Summary
Constructors Modifier Constructor Description private
TransitiveClosure()
Private Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description <V,E>
voidcloseDirectedAcyclicGraph(DirectedAcyclicGraph<V,E> graph)
Computes the transitive closure of a directed acyclic graph in O(n*m)<V,E>
voidcloseSimpleDirectedGraph(SimpleDirectedGraph<V,E> graph)
Computes the transitive closure of the given graph.private int
computeBinaryLog(int n)
Computes floor(log_2(n)) + 1
-
-
-
Field Detail
-
INSTANCE
public static final TransitiveClosure INSTANCE
Singleton instance.
-
-
Method Detail
-
closeSimpleDirectedGraph
public <V,E> void closeSimpleDirectedGraph(SimpleDirectedGraph<V,E> graph)
Computes the transitive closure of the given graph.- Type Parameters:
V
- the graph vertex typeE
- the graph edge type- Parameters:
graph
- - Graph to compute transitive closure for.
-
computeBinaryLog
private int computeBinaryLog(int n)
Computes floor(log_2(n)) + 1
-
closeDirectedAcyclicGraph
public <V,E> void closeDirectedAcyclicGraph(DirectedAcyclicGraph<V,E> graph)
Computes the transitive closure of a directed acyclic graph in O(n*m)- Type Parameters:
V
- the graph vertex typeE
- the graph edge type- Parameters:
graph
- - Graph to compute transitive closure for.
-
-