Karp's minimum mean cycle algorithm

[ggleizer]

Dear all,

Are there plans to implement Karp's minimum mean cycle algorithm in Boost? If not, I would be willing to contribute (although my C++ is quite rusty).

An example implementation is available here. I would include recovering a minimizing cycle in the function; the added cost is small, because the main algorithm runs in O(mn) time (m edges and n vertices), while recovering the minimizer is O(n). For reference, Karp's original paper has a mistake in what concerns recovering the cycle, which was corrected by Chatuverdi and McConnel.

Thank you,

Gabriel.

[jeremy-murphy]

If there is no existing issue or pull request open for it then presumably no-one else is working on it. Sounds like a good contribution to Boost.Graph. You don't have to be a C++ wizard to contribute, just be prepared for a lot of feedback. :) The only problem is that the library is in a bit of a dormant state -- it's failing the CI and I don't know if any contributions will get merged until it's passing again.

[ggleizer]

Thanks, Jeremy. I will (slowly) give it a try then.

[GYuvanShankar]

Greetings,

I have tried my implementation of this algorithm at https://github.com/GYuvanShankar/boost_graph_algorithm/blob/master/main.cpp. Please do check it out, and let me know if I can continue to open a pull request on this matter.

Thank you. G Yuvan Shankar