The tskit (rust) book

Iterating over edge differences

The API provides an iterator over edge differences. Each step of the iterator advances to the next tree in the tree sequence. For each tree, a standard Iterator over removals and insertions is available:

    for diffs in treeseq.edge_differences_iter() {
        for edge_removal in diffs.removals() {
            println!("edge removal: {}", edge_removal);
        }
        for edge_insertion in diffs.insertions() {
            println!("edge insertion: {}", edge_insertion);
        }
    }

Edge differences are the basis of efficient algorithms based on the incremental updating of summaries of trees. The following example co-iterates over edge differences and trees. The edge differences are used to calculate the parent array for each tree:

    let num_nodes = treeseq.nodes().num_rows().as_usize();
    // num_nodes + 1 to reflect a "virtual root" present in
    // the tree arrays
    let mut parents = vec![NodeId::NULL; num_nodes + 1];
    let mut tree_iter = treeseq.tree_iterator(0).unwrap();
    for diffs in treeseq.edge_differences_iter() {
        let tree = tree_iter.next().unwrap();
        for edge_out in diffs.removals() {
            let c = edge_out.child();
            parents[c.as_usize()] = NodeId::NULL;
        }
        for edge_in in diffs.insertions() {
            let c = edge_in.child();
            parents[c.as_usize()] = edge_in.parent();
        }
        assert_eq!(tree.parent_array(), &parents);
    }