/// The same algorithm as `sort`, but for Directed Acyclic Graphs (DAGs),
/// encoded as trees with shared nodes.
///
/// WARNING: To avoid an infinite loop, one must be careful about the order of children.
/// E.g. if `A` has children `C, B` and `B` has child `C`, then the tree is not a DAG.
/// This is because the order of children is preserved after sorting.
The same algorithm as `sort`, but for Directed Acyclic Graphs (DAGs),
encoded as trees with shared nodes.

To avoid an infinite loop, one must be careful about the order of children.
The same algorithm as ` sort ` but for Directed Acyclic Graphs ( DAGs ) encoded as trees with shared nodes . To avoid an infinite loop one must be careful about the order of children .
pub fn sort_dag<T, P, C>(nodes: &mut [T], parents: P, children: C)
    where P: Fn(&mut T) -> &mut [usize],
          C: Fn(&mut T) -> &mut [usize]
{
    let mut gen: Vec<usize> = (0..nodes.len()).collect();
    loop {
        let mut changed = false;
        for i in 0..nodes.len() {
            let children = children(&mut nodes[i]);
            for j in 0..children.len() {
                let a = children[j];
                // Store child after its parent.
                if gen[i] > gen[a] {
                    gen.swap(i, a);
                    changed = true;
                }
                // Check all pairs of children.
                for k in j + 1..children.len() {
                    let b = children[k];
                    // Store children in sorted order.
                    if gen[a] > gen[b] {
                        gen.swap(a, b);
                        changed = true;
                    }
                }
            }
        }
        if !changed {
            break;
        }
    }
    for i in 0..nodes.len() {
        for p in parents(&mut nodes[i]) {
            *p = gen[*p];
        }
        for ch in children(&mut nodes[i]) {
            *ch = gen[*ch]
        }
    }
    for i in 0..nodes.len() {
        while gen[i] != i {
            let j = gen[i];
            nodes.swap(i, j);
            gen.swap(i, j);
        }
    }
}
pub fn sort_dag < T , P , C > ( nodes : & mut [ T ] , parents : P , children : C ) where P : Fn ( & mut T ) -> & mut [ usize ] , C : Fn ( & mut T ) -> & mut [ usize ] { let mut gen : Vec < usize > = ( 0 .. nodes . len ( ) ) . collect ( ) ; loop { let mut changed = false ; for i in 0 .. nodes . len ( ) { let children = children ( & mut nodes [ i ] ) ; for j in 0 .. children . len ( ) { let a = children [ j ] ; // Store child after its parent. if gen [ i ] > gen [ a ] { gen . swap ( i , a ) ; changed = true ; } // Check all pairs of children. for k in j + 1 .. children . len ( ) { let b = children [ k ] ; // Store children in sorted order. if gen [ a ] > gen [ b ] { gen . swap ( a , b ) ; changed = true ; } } } } if ! changed { break ; } } for i in 0 .. nodes . len ( ) { for p in parents ( & mut nodes [ i ] ) { * p = gen [ * p ] ; } for ch in children ( & mut nodes [ i ] ) { * ch = gen [ * ch ] } } for i in 0 .. nodes . len ( ) { while gen [ i ] != i { let j = gen [ i ] ; nodes . swap ( i , j ) ; gen . swap ( i , j ) ; } } }
The same algorithm as `sort`, but for Directed Acyclic Graphs (DAGs),
encoded as trees with shared nodes.
The same algorithm as ` sort ` but for Directed Acyclic Graphs ( DAGs ) encoded as trees with shared nodes .
nodes
&mut [T]
parents
P
children
C