Class TransitiveClosure

java.lang.Object
org.jgrapht.alg.TransitiveClosure

public class TransitiveClosure extends Object
Constructs the transitive closure of the input graph.
  • Field Details

  • Constructor Details

    • TransitiveClosure

      private TransitiveClosure()
      Private Constructor.
  • Method Details

    • closeSimpleDirectedGraph

      public <V, E> void closeSimpleDirectedGraph(SimpleDirectedGraph<V,E> graph)
      Computes the transitive closure of the given graph.
      Type Parameters:
      V - the graph vertex type
      E - 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(nm)$
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - - Graph to compute transitive closure for.