java.lang.Object
org.jgrapht.alg.TransitiveReduction
An implementation of Harry Hsu's
transitive reduction algorithm.
This is a port from a python example by Michael Clerx, posted as an answer to a question about transitive reduction algorithm pseudocode on Stack Overflow
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription<V,
E> void This method will remove all transitive edges from the graph passed as input parameter.(package private) static void
transformToPathMatrix
(BitSet[] matrix) The matrix passed as input parameter will be transformed into a path matrix.(package private) static void
transitiveReduction
(BitSet[] pathMatrix) The path matrix passed as input parameter will be transformed into a transitively reduced matrix.
-
Field Details
-
INSTANCE
Singleton instance.
-
-
Constructor Details
-
TransitiveReduction
private TransitiveReduction()Private Constructor.
-
-
Method Details
-
transformToPathMatrix
The matrix passed as input parameter will be transformed into a path matrix.This method is package visible for unit testing, but it is meant as a private method.
- Parameters:
matrix
- the original matrix to transform into a path matrix
-
transitiveReduction
The path matrix passed as input parameter will be transformed into a transitively reduced matrix.This method is package visible for unit testing, but it is meant as a private method.
- Parameters:
pathMatrix
- the path matrix to reduce
-
reduce
This method will remove all transitive edges from the graph passed as input parameter.You may want to clone the graph before, as transitive edges will be pitilessly removed.
e.g.{ @code DirectedGraph<V, T> soonToBePrunedDirectedGraph; TransitiveReduction.INSTANCE.reduce(soonToBePrunedDirectedGraph); // pruned ! }
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type- Parameters:
directedGraph
- the directed graph that will be reduced transitively
-