Add ``squash_edges`` function about tskit HOT 7 CLOSED

I'll attempt to take this on! Btw, there is a Python squash_edges function in test_topology.py over here.

from tskit.

Hmm, yes, you're right @gtsambos, the function is assuming that there's only one parent in the list of edges. It's easy enough to generalise to handle more than one though. Here's what I'd suggest:

1. Generalise the squash_edges function to take lists that have more than one distinct parent value. This would require (a) adding parent as the first key in the comparison function (there should be lots of other comparison functions around to use as an example); (b) changing the for loop logic to deal with changing from one parent to another; (c) writing a couple of (very) simple test cases to cover this functionality (manually creating a few unsorted small lists of edges and testing the output is squashed appropriately).

2. Add a a new method tsk_edge_table_squash that mallocs a list of edges, copies its contents into this list, calls squash_edges, calls tsk_edge_table_clear() and then runs tsk_edge_table_add_row for each of the new squashed edges.

3. Set up the plumbing between tsk_edge_table_squash and EdgeTable_squash in _tskitmodule.c.

Does this seem like a good approach @gtsambos? Sorry about the misinformation on what the current function does.

from tskit.

Cool - the python version will be handy to write a few quick tests to compare with.

from tskit.

Hmmm, I'm wondering whether the existing squash_edges function in C was made for some slightly different purpose to what we need it for here (link to code is here)?

• I think the first argument should be of type tsk_edge_table_t *? I've assumed this is a typo and fixed it
• Assuming that edges has type edge_table_t *, then all the things like edges[k].parent should actually be edges->parent[k] (I think?)
• This assertion assert(edges[k - 1].parent == edges[k].parent) suggests that the input into this function isn't a normal edge table but some truncated one, as most edge tables would have more than one distinct parent in them. The comparison function cmp_edge_cl that you defined here also looks like it's been designed for this purpose.

Btw I know you're very busy @jeromekelleher! Just flagging these to indicate that this task won't just be setting up plumbing, so might take a bit longer than we first thought

tsk_squash_edges(tsk_edge_t *edges, size_t num_edges, size_t *num_output_edges)
{
    int ret = 0;
    size_t j, k, l;
    tsk_edge_t e;


    qsort(edges, num_edges, sizeof(tsk_edge_t), cmp_edge_cl);
    j = 0;
    l = 0;
    for (k = 1; k < num_edges; k++) {
        assert(edges[k - 1].parent == edges[k].parent);
        if (edges[k - 1].right != edges[k].left || edges[j].child != edges[k].child) {
            e = edges[j];
            e.right = edges[k - 1].right;
            edges[l] = e;
            j = k;
            l++;
        }
    }
    e = edges[j];
    e.right = edges[k - 1].right;
    edges[l] = e;
    *num_output_edges = l + 1;
    return ret;
}

from tskit.

Hi @jeromekelleher, let's continue the conversation over here.

from tskit.

Presumably this can now be closed?

from tskit.

Yes, closed in #285.

from tskit.