Use a Graph Library/Node Network Library or Write My Own?

Question

I'm trying to decide between going with a pre-made graph/node network library or to roll my own.

I'm implementing some graph search algorithms which might require some significant customization to the class structure of the node and/or edges.

The reason I'm not sure what to do is that I'm unsure if customization of a pre-made might be more expensive/trouble than making my own in the first place. I'm also curious, but less so, of the performance trade-offs.

Is there anyone out there have direct experience with using one of the libraries out there and have advice based on a success or failure story? I want to hear the worst so that whatever I chose, I know what I'm getting into.

There are only two that I've found in my search so far: The Boost Graph Library (BGL) and GOBLIN. Specific advice on either of these, or suggestions for others is greatly appreciated as well. BGL seems pretty damn arcane. Is it worth struggling through?

Answer 1

“require some significant customization to the class structure of the node and/or edges.”

Have you looked at the “bundled properties” feature of the BGL?

http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/bundles.html

This is both powerful and not the least bit acrcane.

You define a classes for your edges and your vertices

class cMyVertex
{
…
};
class cMyEdge
{
…
};

Now you define a graph type which will use your classes

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    cMyVertex, cMyEdge > graph_t;

Now you can create graphs of this type that will use your classes, whatever they are, for the vertices and edges.

You can access the attributes and methods of your classes in a perfectly natural way

Graph_t g(10)       // create a graph with 10 vertices
g[1].setA1( “alpha” );  // invoke an accessor on node #1

Answer 2

I recently gave the boost graph library a trial for Dijkstras shortest path problem. Results:

• Very High performance

• Very little code needed

• Very flexible and extensible

• Hard to understand or debug

Advice: Use it but before you do so read The Boost Graph Library: User Guide and Reference Manual

Answer 3

I think if you can leverage the graph traversal algorithms, it is worth using the Boost Graph. Creating and using custom vertices is pretty easy. The examples included with BGL were useful for learning how to use it.

I agree with Clifford, I've used GraphViz to help visualize the graph during development and found it very useful.

Answer 4

You may also take a try with LEMON graph library.

I could use it to perform Dijsktra shortest path search after reading the graph from a configuration file.

A new version has just come out.

Answer 5

This really isn't a concise answer, its more of adding to what has already been said.

The solution to this problem depends on the context of the problem. If you wish to get a great understanding how graph algorithms, and software works. Write your own. If you want to get an advanced knowledge of graph algorithms and structures or to implement them into your own program then learn a standard graph library. (See the reasons for using reusable code)

The best of both worlds. Do both. If you are stretched for time, get a book on this or follow tutorials and the examples.

Another suggestion: Ask a new pointed question about what is the {best, most reliable, easiest to learn} graph library for {describe a very general problem}? This will help you choose what to learn, rather than trying at random to find the best one that suits your needs. Someone has already seen this problem, ask for advice.

Using Reusable Code:

1. Code that someone else has written including test cases will generally be more reliable than your own.
2. Fixes are easer to implement (with updates to the component you are reusing), this is true in Boost (since they do frequent updates, and that Boost is peer reviewed).
3. Once you learn one framework you can apply that to other applications... who knows you might get a job later in life using the framework. Companies like reusing rather than reinventing the wheel.