[Edmonds-alg-users] More efficient implementation of Edmonds' algorithm

[Vladimir Y. <vol...@cs...>]

Hello,
I'm currently working on making the implementation more efficient,
particularly for sparse graphs.

I modified pending/disjoint_sets.hpp to have fast and dirty
implementation of "disjoint sets with weights" which are used by
Tarjan's implementation to update edge weights when collapsing cycles.
Currently the implementation updates every incoming edge to every
strongly connected component vertex on a cycle being collapsed (this
particularly inefficient when the graph becomes dense and, I think,
leads to Omega(VE) complexity).

Another thing that should be done is to use Boost's Fibonacci or
Relaxed heaps as a container for edges so that we have O(E log V)
time. Finally Fibonacci heaps implementation of O(E log V) algorithm
can be later modified into O (V log V).

Any comments, help, especially on correct declaration/interfacing with
Boost is greatly appreciated - my Boost experience is tiny and writing
function bodies is much easier for me than the headers.

One question about the current implementation. Why are all data
structures initialized with (max_vertex_idx +1) elements and Union
Finds with  2*(max_vertex_idx +1)? What are these x2 and "+1" needed
for? Should not  max_vertex_idx be enough?


Thanks,
Vladimir