A modern(ish) C++ graph representation and manipulation library

Question

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 vague, 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 degrees.
• 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.

Answer 1

Some potential candidates, or close-to-being-candidates:

Might be relevant:

• LEMON , or Library for Efficient Modeling and Optimization in Networks - A "C++ template library providing efficient implementations of common data structures and algorithms with focus on combinatorial optimization tasks connected mainly with graphs and networks." Here's a 2010 presentation describing LEMON.
• GGL, the Graph Grammar Library - . Here's the manual.
• Goblin - "A tool chain for handling graphs", including code for graph-related combinatorial optimization algorithms; laying out graphs in space (e.g. layered, orthogonal), graph composition (?), serialization to/from files, vertex and edge attributes and incidence structures. Probably not C++11ish nor involving templates too much.
• SNAP - The Stanford Network Analysis Platform - on one hand, seems to be pretty focused on a specific application; on the other hand, it might have a pretty-much complete graph representation and manipulation API. There's also a hint it might be based on another, lower-level, graph library.
• NGraph - A super-simple, single 23 KiB .hpp file, graph library.
• digraph - A C++11 library for digraphs, geared for use as part of the Faust audio signal processing compiler.

Not relevant / not quite relevant:

• LEDA - A part of a larger codebase of combinatorial algorithms and data structures of the same name. This is commercial software, and even the free edition is closed-source (you can - gasp - buy the source from them). No thank you.
• OGDF - Open Graph Drawing Framework - Seems to be concerned more with layout, drawing of graphs on a plane. Claims to be an FOSS substitute for LEDA.
• igraph - A C (as in: not C++) graph library created for use in network analysis. Claims to focus on performance for large-but-not-huge graphs; and seems to have seen significant development over more than a decade. GitHub page. It has some unstable-API C++ bindings named igraphpp.
• NoCycle - A library for DAG representation. It uses a compact (?) reprsentation of an adjacency map. Probably too different than what I need, and I don't think I "buy" the hype about its representation.
• libcgraph - Part of the GraphViz graph layout project/toolkit. Note there's also a component named libgraph in there - not sure which uses which.
• GCT - Graph Class Templates - Another one-header-file bare-bones library.

It's not impossible that some of the C libraries are good, but I don't think I'm going to spend time wrapping them in C++, not to mention the paucity of abstractions that would be effectively available with them.

See also the following Stack Overflow questions:

• Use a Graph Library/Node Network Library or Write My Own?
• Which C++ graph library should I use?

Answer 2

There is a very serious project of writing a templatized, range-aware, graph library, as a proposal for addition to the C++ standard. It improves and extends ideas from Boost Graph, utilizing modern C++ facilities and mechanisms (including extensive use of ranges).

It's not in a finalized state, but can be found here: https://github.com/pratzl/graph

And the proposal is P1709R2.

Answer 3

I Suggest you the CXXGraph library. It's a personal work that i start to develop more than 2 years ago with the support of other developers.

It's an open-source library and now enough mature and with good performance ( check also benchmark on your machine ).

The library is header-only and can be used with C++ 17.

The library contains all the most known algorithms.