21

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.
3
  • There's also dlib
    – Antony
    Sep 6, 2016 at 10:57
  • @Antony: I don't think that meets all of my crtiera...
    – einpoklum
    Sep 6, 2016 at 15:59
  • Sorry, I feared as much when I posted a comment rather than an answer. I have used the Boost Graph Library a little, so I feel your pain :-(
    – Antony
    Sep 6, 2016 at 17:15

3 Answers 3

14

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:

0
0

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.

-1

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.

2
  • It's your own library, which you have neglected to mention, so -1. Also, I find its design somewhat questionable.
    – einpoklum
    Mar 6, 2023 at 15:55
  • Please declare your affiliation in the answer Mar 6, 2023 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.