D graph library -- update

[Joseph Rushton Wakeling]

On 07/12/2013 12:37 AM, Dmitry Olshansky wrote:
> Append new value to values.
> 
> Then use 'values.length-1' (new length - 1 i.e. the old length) as an item to
> insert into sortedIndices.
> 
> The last step is to figure out what range to call lowerBound on - I'd say
> something like:
> 
> assumeSorted(sortedIndices.map!(x => values[x]))
> 
> then use that to find a suitable place to insert in sortedIndices.

So, just to report back -- this is the code I came up with based on your suggestion:

    void indexEdges()
    {
        immutable size_t l = _indexHead.length;
        foreach(e; iota(l, _head.length))
        {
            size_t i = _indexHead.map!(a =>
_head[a]).assumeSorted.lowerBound(_head[e]).length;
            insertInPlace(_indexHead, i, e);
            i = _indexTail.map!(a =>
_tail[a]).assumeSorted.lowerBound(_tail[e]).length;
            insertInPlace(_indexTail, i, e);
        }
    }

This is _much_ faster than the previous code (although still not as fast as
igraph when adding multiple edges in one go), and also more memory efficient.

I'm a little bothered that the insertion implies potentially many re-allocs, and
I wonder if it might be even better if the length of _indexHead and _indexTail
can be increased in one go, and the "insertion" of the new edge index happen
without risking a reallocation.

Anyway, thanks very much for the useful idea!

igraph is still ultimately faster in the case where multiple edges are added in
a single go, but that's an issue we can confront later.