D graph library

[Joseph Rushton Wakeling]

Hello all,

I've recently been having some very tentative thoughts about whether to try and
develop an effective graph/network library in D.  The goal would be to try and
have a library that allows for highly efficient representation of graphs and
multigraphs, both as static and dynamic entities, with very fast retrieval of
graph properties (e.g. the neighbours of a given vertex, the weights of given
links) for use in simulations _on_ the graph, and very fast calculation of graph
metrics of various kinds.

The general field of application would be in various branches of complexity
science with particular attention to those stemming from interdisciplinary physics.

There are a number of existing solutions in other languages.  igraph, written in
C, is probably the most feature-complete solution, with Python and R interfaces
also available; however, it has (to my eyes) a very complex and unfriendly API,
albeit one that improves when the Python or R versions are used.

I haven't personally used the Boost Graph Library, beyond going through some of
the documentation to explore it as an option, but more experienced colleagues
have downplayed it as very complex to use.

Finally, Networkx is a Python library that seems quite friendly to use, but when
exploring it I found some issues that made me reluctant to trust it as a
scientifically reliable solution.  (To be fair to the maintainers, when I raised
those issues with them, they did something about it quite quickly.)

I know that Philippe Sigaud started some work in this direction for D:
http://svn.dsource.org/projects/dranges/trunk/dranges/docs/graph.html

... but I don't know if there is any ongoing status or intent to develop it
further.  I haven't yet gone through the source code with sufficient scrutiny to
decide whether this makes for a good basis for the kind of project I have in mind.

My main reasons for being tentative about moving forward with this are -- well,
first, it's a major undertaking; as my day job is producing research, not code,
there's something of a pressure to just use the tools already available rather
than trying to optimize for my personal language choice, and I don't want to
start something only to drop off because my research activities are taking me in
a different direction.

Second, I don't know how useful it would be to others -- Python and C/C++ are
still definitely the standard (and growing) tools.  So it would be good to know
if anyone else would like to have such a library explicitly in D.

Third, in terms of producing productive code in a short space of time, I don't
know if it's really worth implementing things in D rather than just providing
bindings/wrappers to an existing library, with igraph being the obvious choice
as it is written in C.  The reason for not doing that so far as been a certain
amount of nervousness about trying to provide .di interfaces for a very large
and complex codebase with lots of custom data structures (the default approach
recommended for using igraph is to import the headers for THE ENTIRE LIBRARY, so
it doesn't lend itself to piecewise construction of bindings).

Finally, given that many of my complaints about the existing tools relate to
complex APIs and not-very-user-friendly code, I'm rather worried about my own
ability (as a researcher and not a well-trained developer:-) to do something
better.  My experience of code written by researchers is in general not good,
though the D community has shown there are exceptions!

Now, that said, there is one very big positive motivation -- I think that D
provides a language in which one could create a graph library with a genuinely
friendly and well-designed API and with easily readable code, yet which has all
the efficiency and scalability of igraph.  And I'd much rather work with that
than any of the other solutions out there.

Some goals for a project like this would be something along the following lines:

   * Hyper-efficient performance for storage and manipulation of graphs.
     I'd want to be able to perform analyses of and/or run simulations on
     extremely large graph sizes.  This would include features such as effective
     use of parallelism (when appropriate), dynamic recalculation of various
     network quantities as nodes/edges are added/removed, and so on.

   * Written in idiomatic D style as exemplified by the best of Phobos, making
     best use of D's generics, templates, etc.

   * Easy to hook into other languages -- I think my colleagues would very much
     appreciate a Python interface.

   * Ideally, would rely _only_ on Phobos and not on any 3rd-party libraries.
     It may turn out that some desirable functionality is not yet in Phobos
     (or does not yet perform adequately), in which case those features should
     be implemented or improved in Phobos rather than this library.

Anyway, for a very tentative proposal (and I have to say, I'm really not sure
whether I will commit to this), I think that's a long enough email for now --
I'd really welcome people's thoughts on these ideas and to get a feel of whether
there's interest in seeing something like this implemented in D.

Thanks & best wishes,

     -- Joe