At my old workplace I had mixed experience with Boost's graph library; I wasn't the person working with that code mostly, but we experienced brittleness, things changing under our feet, and a need to repeatedly refresh state for not-good-enough reasons. Yeah, I know this sounds a bit vauge, but the point is I want to check out the alternatives.
So, I'm looking for a graph library which:
- Represents undirected and directed graphs.
- Does not depend on Boost at all, or at least not significantly.
- Exhibits good performance both when graphs are static (i.e. searching, looking up, iterating with and without filters, etc.).
- Exhibits good performance when graphs are manipulated - edge and vertex additions, removals, moves and updates.
- Scales well to large, but not necessarily huge graphs which are spare rather than dense - say, tens of thousands of vertices and hundreds of thousands of edges.
- Does not balk on very non-uniform vertex degress.
- Friendly towards enriching edges and vertices with additional semantics (yes, again, being vague here not to rule answers out beforehand).
- Free and Open-Source.
- Is written in C++11 and later ... you know what? ok, not a strict requirement, but I would be very biased towards those.
It would also be nice if it also:
- Scales well to huge graphs.
- Performs well on sparse as well as dense graph.
- Allows you to configure its underlying representation to your performance objectives.
- Is not one of those things which malloc()'s like there's no tomorrow and leaves you trapped in a maze of pesky pointers.
- Has a not-so-viral license.
- Is actively maintained.
- Is well-documented.
- Is in wide use.