Class TransitiveClosure


  • public class TransitiveClosure
    extends java.lang.Object
    Constructs the transitive closure of the input graph.
    Since:
    May 5, 2007
    • Constructor Detail

      • TransitiveClosure

        private TransitiveClosure()
        Private Constructor.
    • 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 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(n*m)
        Type Parameters:
        V - the graph vertex type
        E - the graph edge type
        Parameters:
        graph - - Graph to compute transitive closure for.