LEDA graph v/s Boost Graph library

Question

I want efficiency and I am willing to write code by myself if efficiency (=0.9*speed + 0.1*others) is high. If I were to choose between LEDA graph or Boost graph, which one should I choose?

My algorithms are time-consuming (some are even non-polynomial in time) which works on large graphs.

Answer 1

The Boost is continually refactored so parts of it get moved into the standard, after which vendor's continue to optimize it for the target systems they support. On rare usage scenarios, using inheritance the developer may tweak some part for specific case.

If the work is confined to C++, then as the parts of Boost are aiming to get integrated into the standard, it does have these advantages. There maybe specific reason to use proprietary LEDA, such as being guaranteed error free by testing, then as the decision maker only you have to observe such criteria.

Answer 2

Boost graph algorithms can be made to work on LEDA and even stanford graph base graphs, but not the other way around. http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/leda_conversion.html

I would suggest to use boost graph, it is the state of the art.

mike

Answer 3

Boost is generally a good library but I would not suggest Boost graph for a number of reasons.

The BGL documentation is execrable, with no easy to follow user guide. I have found that trying to define graphs with properties that are relevant to my own problems is very difficult.

You frequently end up with huge compiler errors that show templates within templates within templates ... nigh on impossible to see what is going on.

The only solution I found was to start with a trivial example that comes with Boost Graph, and adapt it until it does what I want.

I know of many bright and capable people that have ditched Boost Graph because of these reasons. Sad since there are very efficient algorithms underneath it all. For me BGL is the textbook example of template overuse. Boost Graph is a great idea that fails by missing the point entirely: code is worthless if it can't be read, maintained, extended, or debugged.

There are alternatives to LEDA/Boost implementation. You could do worse than to investigate this similar-sounding posting: https://stackoverflow.com/questions/510758/can-you-suggest-a-good-book-on-graphs-and-graph-algorithms (link is no longer valid)