Implement a basic simplify()

[hyanwong]

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 either

• adjust sample_resolve to output a list of nodes that no longer have edges in or edges out, or
• copy and paste the sample_resolve code into a new function that uses a dynamic stack. Fill a new node table with the sample nodes from (0..n) and save a mapping (a numpy array of length len(graph.nodes) initially filled with NULL) of old sample node ids to the new 0..n IDs. 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)

[hyanwong]

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])

[hyanwong]

A more basic simplify would not change the node IDs, but simply remove intermediate nodes from a chain of unary nodes. We could have a separate routine to re-order / remove redundant nodes