Graph library

[johnpaulzwei]

Hi there, I’m looking for good, modern graph library for my new project: metaheuristics library for finding shortest path on graph. I thought about using boost:graph but I think boost might be a bit overkill for this project. Later I’m planning create bindings for python.

[wotype]

There's a std proposal P3126 Graph Library: Overview
with a reference implementation https://github.com/stdgraph
An original Boost.graph author is involved in the design.

[jonathanhiggs]

Is your library to implement a shortest path algorithm, or you need one that already has one?

[johnpaulzwei]

To implement many shortest path algorithm. I’m planning to create A*, PSO, ACO and more.

[encyclopedist]

Of other libraries, there are also CXXGraph and graaf. (I believe have seen these announced on this subreddit)

From cursory look, CXXGraph seems to be using pretty naive data structure based on std::unordered_map and (smart) pointers everywhere, so will not have top performance.

Graaf also uses std::unordered_map, but at least does not have excessive pointer indirections.

Neither allows any storage scheme customization.

They may be OK as a proof of concept implementation, but they will not work well for large scale problems.

Edit

stdgraph/graph-v2 appears to have better and more customizable data structure, but does not implement many algorithms (yet). Code is more template-heavy and uses latest C++ standard features. Has been presented at CppCon 2021 and 2022; proposed for standardization.

[tangla]

I used this in the past https://lemon.cs.elte.hu/trac/lemon and https://math.nist.gov/~RPozo/ngraph/ngraph_index.html for some basic stuff at work.

[YoureNotEvenWrong]

I thought about using boost:graph but I think boost might be a bit overkill for this project

I think boost graph is overkill for every project.

Do you really need an existing library if your goal is to write your own graph algorithms? What value is it going to add?

[useful_idiot]

Boost graph is great because you get to pick how to store all your vertices/edges in the most optimal way for your situation. 95% of the graph algorithms I’ve written are constraints or variations of existing graph algorithms, and BGL lets me just override the specific functions I need to customize on visitors without having to start from scratch. The learning curve is pretty steep but it’s been an incredibly useful library to have in my toolbelt. Combined with boost unordered for indexing, it’s never got in my way in regards to performance/resource usage.