Hi all, Following earlier discussion about a D graph library <http://forum.dlang.org/thread/5187d514.5070...@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