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

Closed. This question is seeking recommendations for books, tools, software libraries, and more. It does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

We don’t allow questions seeking recommendations for books, tools, software libraries, and more. You can edit the question so it can be answered with facts and citations.

Closed 5 years ago.

Improve this 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 alm开发者_如何学Goost 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.

---

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.

---

I know this late, but have you looked at LEMON?

---

Have you looked at Boost Graph Library

I haven't used it myself, but as part of Boost you can expect it to be very high quality, but it will demand a measure of C++ expertise.