Module org.jgrapht.core
Package org.jgrapht.alg

Class TransitiveReduction

java.lang.Object
org.jgrapht.alg.TransitiveReduction
public class TransitiveReduction
extends java.lang.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

Author:
Christophe Thiebaud

  • Field Summary

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

  • Method Summary

    Modifier and Type Method Description
    <V,​ E> void reduce​(Graph<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 Details

  • Method Details

    • reduce

      public <V,​ E> void reduce​(Graph<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