src/main/java/org/thegalactic/dgraph/DAGraph.java
public int transitiveReduction() {

        // copy this component in a new DAG graph
        DAGraph<N, E> graph = new DAGraph<N, E>(this);
        graph.reflexiveReduction();
        // initalize this component with no edges
        this.setSuccessors(new TreeMap<Node<N>, SortedSet<Edge<N, E>>>());
        for (Node<N> node : this.getNodes()) {
            this.getSuccessors().put(node, new TreeSet<Edge<N, E>>());
        }
        this.setPredecessors(new TreeMap<Node<N>, SortedSet<Edge<N, E>>>());
        for (Node<N> node : this.getNodes()) {
            this.getPredecessors().put(node, new TreeSet<Edge<N, E>>());
        }
        int number = 0;
        // mark each node to false
        TreeMap<Node<N>, Boolean> mark = new TreeMap<Node<N>, Boolean>();
        for (Node<N> node : graph.getNodes()) {
            mark.put(node, Boolean.FALSE);
        }
        // treatment of nodes according to a topological sort
        List<Node<N>> sort = graph.topologicalSort();
        for (Node<N> x : sort) {
            TreeSet<Node<N>> set = new TreeSet<Node<N>>(graph.getSuccessorNodes(x));
            while (!set.isEmpty()) {
                // compute the smallest successor y of x according to the topological sort
                int i = 0;
                while (!set.contains(sort.get(i))) {
                    i++;
                }
                Node<N> y = sort.get(i);
                // when y is not not marked, x->y is a reduced edge
                if (y != null && !mark.get(y)) {
                    this.addEdge(x, y);
                    graph.addEdge(x, y);
                }
                for (Node<N> z : graph.getSuccessorNodes(y)) {
                    // treatment of z when not marked
                    if (!mark.get(z)) {
                        mark.put(z, Boolean.TRUE);
                        graph.addEdge(x, z);
                        number++;
                        set.add(z);
                    }
                }
                set.remove(y);
            }
            for (Node<N> y : graph.getSuccessorNodes(x)) {
                mark.put(y, Boolean.FALSE);
            }
        }
        return number;
    }
/**
     * Computes the transitive reduction of this component.
     *
     * The transitive reduction is not uniquely defined only when the acyclic
     * property is verified. In this case, it corresponds to the Hasse diagram
     * of the DAG.
     *
     * This method is an implementation of the Goralcikova-Koubeck algorithm
     * that can also compute the transitive closure. This tratment 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 reduction of this component.
The transitive reduction is not uniquely defined only when the acyclic
property is verified. In this case, it corresponds to the Hasse diagram
of the DAG.

This method is an implementation of the Goralcikova-Koubeck algorithm
that can also compute the transitive closure. This tratment 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 reduction of this component . The transitive reduction is not uniquely defined only when the acyclic property is verified . In this case it corresponds to the Hasse diagram of the DAG . This method is an implementation of the Goralcikova - Koubeck algorithm that can also compute the transitive closure . This tratment 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 transitiveReduction() {
        DAGraph<N, E> graph = new DAGraph<N, E>(this);
        graph.reflexiveReduction();
        this.setSuccessors(new TreeMap<Node<N>, SortedSet<Edge<N, E>>>());
        for (Node<N> node : this.getNodes()) {
            this.getSuccessors().put(node, new TreeSet<Edge<N, E>>());
        }
        this.setPredecessors(new TreeMap<Node<N>, SortedSet<Edge<N, E>>>());
        for (Node<N> node : this.getNodes()) {
            this.getPredecessors().put(node, new TreeSet<Edge<N, E>>());
        }
        int number = 0;
        TreeMap<Node<N>, Boolean> mark = new TreeMap<Node<N>, Boolean>();
        for (Node<N> node : graph.getNodes()) {
            mark.put(node, Boolean.FALSE);
        }
        List<Node<N>> sort = graph.topologicalSort();
        for (Node<N> x : sort) {
            TreeSet<Node<N>> set = new TreeSet<Node<N>>(graph.getSuccessorNodes(x));
            while (!set.isEmpty()) {
                int i = 0;
                while (!set.contains(sort.get(i))) {
                    i++;
                }
                Node<N> y = sort.get(i);
                if (y != null && !mark.get(y)) {
                    this.addEdge(x, y);
                    graph.addEdge(x, y);
                }
                for (Node<N> z : graph.getSuccessorNodes(y)) {
                    if (!mark.get(z)) {
                        mark.put(z, Boolean.TRUE);
                        graph.addEdge(x, z);
                        number++;
                        set.add(z);
                    }
                }
                set.remove(y);
            }
            for (Node<N> y : graph.getSuccessorNodes(x)) {
                mark.put(y, Boolean.FALSE);
            }
        }
        return number;
    }
public int transitiveReduction ( ) { DAGraph < N , E > graph = new DAGraph < N , E > ( this ) ; graph . reflexiveReduction ( ) ; this . setSuccessors ( new TreeMap < Node < N > , SortedSet < Edge < N , E > > > ( ) ) ; for ( Node < N > node : this . getNodes ( ) ) { this . getSuccessors ( ) . put ( node , new TreeSet < Edge < N , E > > ( ) ) ; } this . setPredecessors ( new TreeMap < Node < N > , SortedSet < Edge < N , E > > > ( ) ) ; for ( Node < N > node : this . getNodes ( ) ) { this . getPredecessors ( ) . put ( node , new TreeSet < Edge < N , E > > ( ) ) ; } int number = 0 ; TreeMap < Node < N > , Boolean > mark = new TreeMap < Node < N > , Boolean > ( ) ; for ( Node < N > node : graph . getNodes ( ) ) { mark . put ( node , Boolean . FALSE ) ; } List < Node < N > > sort = graph . topologicalSort ( ) ; for ( Node < N > x : sort ) { TreeSet < Node < N > > set = new TreeSet < Node < N > > ( graph . getSuccessorNodes ( x ) ) ; while ( ! set . isEmpty ( ) ) { int i = 0 ; while ( ! set . contains ( sort . get ( i ) ) ) { i ++ ; } Node < N > y = sort . get ( i ) ; if ( y != null && ! mark . get ( y ) ) { this . addEdge ( x , y ) ; graph . addEdge ( x , y ) ; } for ( Node < N > z : graph . getSuccessorNodes ( y ) ) { if ( ! mark . get ( z ) ) { mark . put ( z , Boolean . TRUE ) ; graph . addEdge ( x , z ) ; number ++ ; set . add ( z ) ; } } set . remove ( y ) ; } for ( Node < N > y : graph . getSuccessorNodes ( x ) ) { mark . put ( y , Boolean . FALSE ) ; } } return number ; }
Computes the transitive reduction of this component.
Computes the transitive reduction of this component .
// copy this component in a new DAG graph // initalize this component with no edges // 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 // when y is not not marked, x->y is a reduced edge // treatment of z when not marked