Class TransitiveClosure


  • public class TransitiveClosure
    extends java.lang.Object
    Constructs the transitive closure of the input graph.
    • 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(nm)$
        Type Parameters:
        V - the graph vertex type
        E - the graph edge type
        Parameters:
        graph - - Graph to compute transitive closure for.