[igraph] Performance issue on dymanic networks

[Hadidi, Lars]

I am using the igraph_maximum_bipartite_matching function to implement a multi particle tracking algorithm.

I already have been informed that thelibrary is optimized for graphs that do not change a lot.

As I create a new graph for every new frame, this isn't the optimal use case for the library, but a profiling session showed that it doesn't appear to be a performance drop at all, as the removing of all vertices and using add_edges are still pretty fast, only the index rebuild invoked by add_vertices cosumes some time.

Most of the time is spent on the bipartite matching, and I'd like to know if there is any way to increase performance ?

The optimized push-relabel method used by igraph is theoretically one of the fastest methods out there, but the more nodes the graph has, the slower the code works, seemingly exponentially slower. (processing 5GB of data takes about 12 hours, 30GB won't finish after 60 hours)