7

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?

migrated from cs.stackexchange.com Mar 17 '15 at 19:44

This question came from our site for students, researchers and practitioners of computer science.

  • In BGL You can "remove" vertices more cheaply using this filtering adapter that they apparently have - vertices are just marked deleted (and occasionally you have to re-consolidate the graph). – einpoklum - reinstate Monica Mar 24 '16 at 13:30
  • If you know BGL and want some rep, check out this question of mine on SO. – Agostino Mar 24 '16 at 20:19
  • I actually don't know BGL well; I've worked in a group in which someone else was the graph representation guy and he used to complain about how BGL was this and BGL was that... – einpoklum - reinstate Monica Mar 24 '16 at 21:30
  • 1
    LEMON graph is maintained, even if it does not have a recent release. I find it to be a very nice and modern C++ library which is designed to be easy to use and understand (unlike the BGL which is a frustrating over-engineered mess that I always waste too much time on). – Szabolcs Nov 22 '18 at 22:35
  • 1
    igraph is the easiest to use. It has a C interface, which means that it does not need any sort of wrapper to use from C++. But yes, it is GPL. – Szabolcs Nov 22 '18 at 22:36
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.

0

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

enter image description here

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?

enter image description here

See many more here and here.

Or did I misunderstand?

  • 1
    I suspect GraphViz is about drawing network graphs, rather than building them and applying algorithms to analyze their properties, right? – Agostino Mar 16 '17 at 9:25
  • Yes it is. Did I misundertsand? Is that not what you are looking for? – Mawg Mar 16 '17 at 9:27
  • 1
    Yes, by "graph representation" I meant "building the internal structure". I understand how that can be misleading. I need libraries for graph analysis and manipulation. Think about calculating centrality metrics and shortest paths. Still, your answer provides a great tool for graph visualization. – Agostino Mar 16 '17 at 10:07
  • D'oh! Silly me. But, I am glad that you (and others) might have learned of a very useful tool. Take alook at the gallery to see just how much it can do. Hope you get a real answer, though ;-) – Mawg Mar 16 '17 at 10:10

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.