src/main/java/org/thegalactic/dgraph/DAGraph.java
public int transitiveClosure() {
        int number = 0;
        // mark each node to false
        TreeMap<Node<N>, Boolean> mark = new TreeMap<Node<N>, Boolean>();
        for (Node<N> node : this.getNodes()) {
            mark.put(node, Boolean.FALSE);
        }
        // treatment of nodes according to a topological sort
        List<Node<N>> sort = this.topologicalSort();
        for (Node<N> x : sort) {
            TreeSet<Node<N>> set = new TreeSet<Node<N>>(this.getSuccessorNodes(x));
            while (!set.isEmpty()) {
                // compute the smallest successor y of x according to the topological sort
                int i = 0;
                do {
                    i++;
                } while (!set.contains(sort.get(i)));
                Node<N> y = sort.get(i);
                for (Node<N> z : this.getSuccessorNodes(y)) {
                    // treatment of z when not marked
                    if (!mark.get(z)) {
                        mark.put(z, Boolean.TRUE);
                        this.addEdge(x, z);
                        number++;
                        set.add(z);
                    }
                }
                set.remove(y);
            }
            for (Node<N> y : this.getSuccessorNodes(x)) {
                mark.put(y, Boolean.FALSE);
            }
        }
        return number;
    }
/**
     * Computes the transitive closure of this component.
     *
     * This method overlaps the computation of the transitive closure for
     * directed graph in class {@link ConcreteDGraph} with an implementation of the
     * Goralcikova-Koubeck algorithm dedicated to acyclic directed graph. This
     * algorithm can also compute the transitive reduction of a directed acyclic
     * graph.
     *
     * This treatment is performed in O(n+nm_r+nm_c), where n corresponds to the
     * number of nodes, m_r to the numer of edges in the transitive closure, and
     * m_r the number of edges in the transitive reduction.
     *
     * @return the number of added edges
     */
Computes the transitive closure of this component.
This method overlaps the computation of the transitive closure for
directed graph in class  ConcreteDGraph with an implementation of the
Goralcikova-Koubeck algorithm dedicated to acyclic directed graph. This
algorithm can also compute the transitive reduction of a directed acyclic
graph.

This treatment is performed in O(n+nm_r+nm_c), where n corresponds to the
number of nodes, m_r to the numer of edges in the transitive closure, and
m_r the number of edges in the transitive reduction.

@return the number of added edges
Computes the transitive closure of this component . This method overlaps the computation of the transitive closure for directed graph in class ConcreteDGraph with an implementation of the Goralcikova - Koubeck algorithm dedicated to acyclic directed graph . This algorithm can also compute the transitive reduction of a directed acyclic graph . This treatment is performed in O ( n + nm_r + nm_c ) where n corresponds to the number of nodes m_r to the numer of edges in the transitive closure and m_r the number of edges in the transitive reduction . @return the number of added edges
public int transitiveClosure() {
        int number = 0;
        TreeMap<Node<N>, Boolean> mark = new TreeMap<Node<N>, Boolean>();
        for (Node<N> node : this.getNodes()) {
            mark.put(node, Boolean.FALSE);
        }
        List<Node<N>> sort = this.topologicalSort();
        for (Node<N> x : sort) {
            TreeSet<Node<N>> set = new TreeSet<Node<N>>(this.getSuccessorNodes(x));
            while (!set.isEmpty()) {
                int i = 0;
                do {
                    i++;
                } while (!set.contains(sort.get(i)));
                Node<N> y = sort.get(i);
                for (Node<N> z : this.getSuccessorNodes(y)) {
                    if (!mark.get(z)) {
                        mark.put(z, Boolean.TRUE);
                        this.addEdge(x, z);
                        number++;
                        set.add(z);
                    }
                }
                set.remove(y);
            }
            for (Node<N> y : this.getSuccessorNodes(x)) {
                mark.put(y, Boolean.FALSE);
            }
        }
        return number;
    }
public int transitiveClosure ( ) { int number = 0 ; TreeMap < Node < N > , Boolean > mark = new TreeMap < Node < N > , Boolean > ( ) ; for ( Node < N > node : this . getNodes ( ) ) { mark . put ( node , Boolean . FALSE ) ; } List < Node < N > > sort = this . topologicalSort ( ) ; for ( Node < N > x : sort ) { TreeSet < Node < N > > set = new TreeSet < Node < N > > ( this . getSuccessorNodes ( x ) ) ; while ( ! set . isEmpty ( ) ) { int i = 0 ; do { i ++ ; } while ( ! set . contains ( sort . get ( i ) ) ) ; Node < N > y = sort . get ( i ) ; for ( Node < N > z : this . getSuccessorNodes ( y ) ) { if ( ! mark . get ( z ) ) { mark . put ( z , Boolean . TRUE ) ; this . addEdge ( x , z ) ; number ++ ; set . add ( z ) ; } } set . remove ( y ) ; } for ( Node < N > y : this . getSuccessorNodes ( x ) ) { mark . put ( y , Boolean . FALSE ) ; } } return number ; }
Computes the transitive closure of this component.
Computes the transitive closure of this component .
// mark each node to false // treatment of nodes according to a topological sort // compute the smallest successor y of x according to the topological sort // treatment of z when not marked