Tutorial on edge_diffs / incremental algorithms #233

Activity

1. hyanwong commented on Mar 1, 2023

   

   hyanwong

   on Mar 1, 2023

   MemberAuthor

   More actions

   Ah yes, I remember, this sort of tallying of nodes when passing over edge_diffs (and in this case, counting sample numbers under them), was what I did when implementing the spans_by_samples function in tsdate.
2. hyanwong commented on May 28, 2026

   

   hyanwong

   on May 28, 2026

   Last edited by hyanwong

   MemberAuthor

   More actions

   A good example for a simple incremental algorithm is to keep track of the number of descendants of every node in the trees:

   import numpy as np
   import tskit
   
   ts = ...
   
   # Subtree size including the node itself.
   num_descendants = np.ones(ts.num_nodes, dtype=ts.edges_child.dtype)
   # Can't use tree.parent_array as we need this for the previous and this tree
   parent = np.full( ts.num_nodes, tskit.NULL, dtype=ts.edges_child.dtype)
   
   def update_ancestors(total_nodes, parent, u, delta):
       while u != tskit.NULL:
           total_nodes[u] += delta
           u = parent[u]
   
   for interval, edges_out, edges_in in ts.edge_diffs():
       # edge_diffs() ordering guarantees that total_nodes[e.child]
       # is already correct when each edge is processed, i.e.
       #   edges_out: descending parent time (i.e. postorder)
       #   edges_in:  ascending parent time (i.e. preorder)
       # so whole child subtrees can be moved as a single block.
       for e in edges_out:
           delta = -num_descendants[e.child]
           update_ancestors(num_descendants, parent, e.parent, delta)
           parent[e.child] = tskit.NULL
   
       for e in edges_in:
           parent[e.child] = e.parent
           delta = num_descendants[e.child]
           update_ancestors(num_descendants, parent, e.parent, delta)

   This can be compared against calculating the num_descendants every time, e.g. via tskit-dev/tskit#2525