hyanwong
commented
8 months ago Once we start trying longer-running forward simulations then simplifying the intervals and (especially) removing intermediate nodes should considerably speed up the find_mrca_regions process, as there will be fewer hops before we reach the MRCAs.
For this reason, it seems likely that simplifying every generation will be worth it even though it will mean rewriting the edges and nodes tables. It could well be the case that we don't need to touch the upper parts of the edges table, and can simply truncate back to the earliest row ID which has a child corresponding to the oldest removed node (i.e. iedges.id_range_for_child[oldest_removed_node][0])
To remove unreferenced nodes should be fairly easy, and can be based on the existing
sample_resolve()function. All we need to do is to eithersample_resolveto output a list of nodes that no longer have edges in or edges out, or0..n) and save a mapping (a numpy array of lengthlen(graph.nodes)initially filled with NULL) of old sample node ids to the new0..nIDs. Every time we pop a child off the stack add to the new node table by copying that node from the old one and add to the mapping. When sample_resolve is done, simply remap the node IDs in the edges table (we would also need to remap mutation node IDs, when we implement a mutations table).This will save space, but not time. To reduce simulation time, a more elaborate
simplify()would also (optionally) remove pass-though nodes, but we would need to think carefully about this and what would happen to the edge column (which is not a feature implemented in tskit). In particular, I'm keen to preserve diamonds by letting the two paths around the diamond retain different edge IDs. I think new edge IDs would be created from each unique combination of edge paths (so that an edge ID represents a unique transmission path)