Simple C/C++ library for network graph manipulation

Question

I'm currently working on a research project that makes use of proprietary software. I'm trying to replace the proprietary C libraries for graph representation. Doing this will make it easier to migrate our project to an open platform and make it available to everyone for free.

The project mixes C with C++, so if it's a C library we are going to adopt, it needs to play along nicely with C++.

The current libraries use pointers for everything and casts to and from void* in order to store and retrieve stuff.

It makes it fairly easy to:

• add and remove vertices
• add and remove edges
• get a list with the edges of a vertex
• get a list with the neighbors of a node
• calculate connected components
• calculate shortest paths (using Dijkstra)

Vertices have type PrgT_Graph_Vertex* and can have an associated void* pointer to store related information. A similar logic is used with respect to edges. Here's a concrete example.

The replacement needs to have a license that does not enforce copyleft, so it can't be GPL. BSD-style licenses are fine.

Boost Graph Library, BGL from now on, has an OK license and is part of a well-known suite. However, its documentation is fragmentary and looks like it was "patched up" together rather than thoughtfully "built". Removing vertices does not seem to be easy as it can mess with vertex indexes.

Lemon Graph Library has the same license as the BGL, looks easier, but is not as actively maintained (see roadmap).

Stanford SNAP has an OK license is the one with the nicest website, but the documentation appears very lacking.

iGraph is not an option because it's GPL licensed. Also, from what I understand, it would require a wrapper to be used in C++.

Network Graph Toolkit, developed by the NIST, is released in the public domain but does not look like it's documented at all (aside from code comments).

BGL seems to be the one with the best guarantees it will remain actively developed. But it's also quite far from my current implementation logic and will take a lot of time just to get started with.

Any suggestion?

Answer 1

I expect it is too late to help the original poster, but as this question came up in the 'Hot Network Questions' list, here is a recommendation.

The STLPlus library is actively maintained and has a nice directed graph implementation. It is available under the BSD licence. There is a forum, the maintainer usually replies within a couple of days and is open to suggestions / improvements.

Answer 2

The answer seems so obvious that I am afraid that I have misunderstood the question.

Surely, nothing beats Graphviz? It's been around forever, is actively maintained and has great support.

I love it because it takes plain text input, which I can generate from my data of many diverse formats.

This

graph { 
    a -- b; 
    b -- c; 
    a -- c; 
    d -- c; 
    e -- c; 
    e -- a; 
} 

produces this

No need to link it to your program, just run it as a shell command from within your app.

Is this what you mean by a network graph?

See many more here and here.

Or did I misunderstand?