10

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.
  • There's also dlib – Antony Sep 6 '16 at 10:57
  • @Antony: I don't think that meets all of my crtiera... – einpoklum Sep 6 '16 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 '16 at 17:15
6

Nobody's answered so far... it looks like not many people frequent the C++-library-request pages on this site. Anyway, I'll add some potential candidates, or close-to-being-candidates, in this answer for now:

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.

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 barebones 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 StackOverflow questions:

  • "not many people frequent this site"?? – Mawg Mar 22 '16 at 8:43
  • @Mawg: I could argue that was true in general, certainly relative to SO, but instead I edited. – einpoklum Mar 22 '16 at 8:46
  • 1
    @Mawg: Just look at the most active questions and how many votes/visitors they have. – einpoklum Mar 22 '16 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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