D graph library -- update

[Joseph Rushton Wakeling]

Hi all,

Following earlier discussion about a D graph library
<http://forum.dlang.org/thread/5187D514.5070109@webdrake.net>, this evening I
sat down and had a go at coming up with some basic code to support such a venture.

You can find it here: https://github.com/WebDrake/Dgraph

This takes the basic data structure from the widely-used igraph library
<http://igraph.sourceforge.net> but builds around it using idiomatic D
structures and algorithms.

The code currently consists of the basic data structure, implemented as a final
class with methods to extract the number of vertices, the list of edges, and the
degree and neighbours of a vertex.

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.

However, when igraph's option to add the edges all in one go in a vector is
enabled, igraph is significantly faster.  This surely reflects a mix of memory
management (how many allocs/appends?) and also the amount of sorting and other
updates that occur when edges are added.  So, I think that igraph can probably
still be beaten here.

The memory usage for the example D code is slightly higher than for its
comparable igraph C code, clocking in at about 2MB as opposed to 1.7.

I've chosen igraph as a point of comparison because it's known for being both
the fastest and most scalable graph library out there.  Many of igraph's design
choices seem focused on minimizing memory usage, sometimes at the expense of
all-out speed: for example, if an algorithm needs an adjacency list
representation of the graph, igraph will generate one at that moment, and
destroy it afterwards.

However, on the basis of the simple work done here, I'm fairly confident that D
can do better.  The code here is _much_ simpler than the equivalent functions in
igraph, and has not yet been optimized in any way either for speed or for memory
management.  Yet it seems to be performing on par with or better than igraph
within the limits of its current design constraints.

I'll be trying to implement a few additional little pieces of functionality in
the next days, perhaps some graph metrics which can give another point of
performance comparison.

Anyway, comments welcome, both positive and negative.

Thanks & best wishes,

    -- Joe