org.jgrapht.alg

Class TransitiveReduction

java.lang.Object

org.jgrapht.alg.TransitiveReduction

public class TransitiveReduction
extends Object

An implementation of Harry Hsu's transitive reduction algorithm.

cf. Harry Hsu. "An algorithm for finding a minimal equivalent graph of a digraph.", Journal of the ACM, 22(1):11-16, January 1975.

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

Since:

Aug 13, 2015

Author:

Christophe Thiebaud

Field Summary

Fields

Modifier and Type	Field and Description
static TransitiveReduction	INSTANCE Singleton instance.

Method Summary

Modifier and Type	Method and Description
<V,E> void	reduce(DirectedGraph<V,E> directedGraph) This method will remove all transitive edges from the graph passed as input parameter.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

INSTANCE

public static final TransitiveReduction INSTANCE

Singleton instance.

Method Detail

reduce

public <V,E> void reduce(DirectedGraph<V,E> directedGraph)

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 type

E - the graph edge type

Parameters:

directedGraph - the directed graph that will be reduced transitively