C/C++ Library for dynamic graphs? [closed]

Question

I'm looking for a library to operate on dynamical graphs. I have a simulation where I must repeatedly calculate the average geodesic length for a graph after doing some changes in its structure (adding and deleting edges, on an undirected graph, all edges have the same weights).

I was using a quick C++ wrap over igraph that I made. igraph is for static graphs, so I was recalculating the geodesic distances from scratch every time I changed the graph. It's a monte carlo simulation, so I must do this millions of times to recover some statistics. It's starting to get real slow.

So I looked for libraries with algorithms for dynamical graphs, that could recalculate just update the average length after I delete or add an edge. I found some papers on the subject, but I'm really no specialist (I'm just a physicist, I'm just incidentally using graphs on a problem... I have almost no knowledge of data structures and algorithms) so I can't even read the papers, let alone implement the algorithms.

I found this library LEDA (http://www.algorithmic-solutions.com/leda/) which seems to have a dynamic graph extension, but it seems to be unmaintained (the links to download the free version are broken) and it's proprietary.

Are there any alternatives? I'm looking for C/C++ libraries. Maybe Haskell if I must, and I'm absolutely desperate.

Answer 1

Since you're doing Monte Carlo anyway, I assume that it would be acceptable to approximate the average shortest-path length. At each step, you could sample a handful of nodes and report the average shortest-path length for paths starting at one of those nodes, which has the same expectation and hopefully reasonable variance.

Alternatively, reference [3] of the JACM paper you mentioned on dynamic shortest-paths is an experimental study from 2004; perhaps the authors would let you use their code.