Migrate graph library from NetworkX

[torressa]

Hi David, I wonder if you ever consider to switch the graph package from Networkx to graph-tool or igraph? Based on my personal experience and this article: https://www.timlrx.com/blog/benchmark-of-popular-graph-network-packages-v2 , either one of graph-tool and igraph can be hundred times faster than Networkx. It can significantly improve the algorithms in CSPY. Just a thought to speak out loud since I noticed that you have several issues on enhancing the performance. If it is built on Networkx, it is going to be very hard to do so.

From #61 (comment)

The speed for the heuristics would be pretty significant.
Thoughts?

[torressa]

Would be nice to use a graph library with a good C++ implemenation and Python support (to kill two birds with one stone).

Python / Cpp

Repo with more info:

https://github.com/timlrx/graph-benchmarks

Possible Python candidates (unfortunately not lightgraphs.jl) :

1. graph-tool

+ve	-ve
- Fastest out the comparison (with Python comp)	- PyPI release unmainted
- Nice API	- No windows wheel

2. networkit

+ve	-ve
- MIT License	- Slower than graph-tool
- Can use both Python + Cpp	-

3. igraph

+ve	-ve
- All wheels	- GPL-2.0 License

Cpp only libraries

Would be nice to have a C++/Python but also open to other libraries if performance is significant.
To replace my graph structure (src/cc/digraph.h) and shortest path implementation (src/cc/preprocessing.h).

Options include:

1. Boost
2. ligra
3. LEMON++

[ktnr]

Great library, thanks! Out of curiosity: what made you choose LEMON over boost::graph? The development of LEMON seems to be inactive.

[torressa]

Thanks @ktnr!
I know it's been inactive for a while, but to be honest, the algorithms implemented are still more recent than those in BGL e.g. max flow, min cut, min cost flow (specific paper on this). I seem to recall a performance benefit, see e.g. paper and pres. Benchmarks are old at this point (more than 10 years now, more recent one here) so may have become obsolete if BGL has made significant changes since then, would be interesting to find out.
I also find it easier to use and build as it lightweight compared to boost.

[ktnr]

Yeah, it definitely appears to be easier to use. Thanks for the useful resources! It's a pity that it's not being actively maintained. Hopefully someone will pick it up in the future.

[torressa]

For a different project turns out its pretty handy to benchmark them again.
Hoping to create a separate repo for this.

[torressa]

Networkit for both Python and C++ code.

May change to LEMON for C++ if the performance benefit is significant

[torressa]

Correction, using LEMON as it's more flexible (and I think it's also faster)