D graph library -- update

Joseph Rushton Wakeling joseph.wakeling at webdrake.net
Wed Jul 10 17:10:26 PDT 2013


On 07/11/2013 01:59 AM, Joseph Rushton Wakeling wrote:
> There is also a simple test file that can be used for benchmarking against
> comparable igraph code.  With the current method of adding edges one by one,
> this code already benchmarks as faster than its igraph equivalent, running in
> 2.4s on my machine when compiled with gdmd -O -release -inline and 1.4s when
> compiled with ldmd2 and the same flags -- compared to 3s for the igraph code
> written in C.

Comparable igraph code attached. :-)  You'll need to download and install igraph
0.6.5 if you want to try this out, then compile with

    gcc -O3 -o graph50 graph50.c -ligraph

There's some commented out stuff in the foo() function which implements the
alternative means of adding edges to an igraph_graph_t, namely by adding them
all in a big vector.  This makes igraph's performance _much_ faster than the
current D implementation.

A note on the data model.  The _head and _tail arrays I guess are fairly
self-explanatory, being the start and end vertices of edges in the graph.
_indexHead and _indexTail are edge IDs sorted respectively by head and tail
values.  Finally, _sumHead and _sumTail are vectors whose v'th entry corresponds
to the total number of edges whose head (or tail) vertices have IDs less than v.

In other words, if we want to find out the number of outgoing edges from a
vertex v, we can do so by calculating _sumHead[v + 1] - _sumHead[v].  If we want
the number of incoming edges, we do the same but with _sumTail.

By similar tricks, we can cheaply list the neighbours of a vertex.  I'm
reasonably confident that the D implementation here will allow it to reliably
beat igraph for algorithms that rely on access to this information.

The cost of all this is that it's expensive to add edges, or at least, it's
expensive to add edges one at a time -- but this is arguably a cost worth
bearing for the speed and efficiency gains elsewhere.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graph50.c
Type: text/x-csrc
Size: 1577 bytes
Desc: not available
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20130711/c1ba8af7/attachment.c>


More information about the Digitalmars-d mailing list