graph
graph copied to clipboard
boostorg
Added Karps Minimum Cycle Algorithm
Thanks for taking the time to implement this. It looks good, but as I said earlier it will take a few rounds of feedback to get it to be consistent with existing BGL code.
Please take a look at an existing similar algorithm such as Howard's cycle ratio algorithm and imitate what is there. There is a lot more to an algorithm than just the implementation, namely:
- Documentation
- Examples
- Unit tests
PS. One thing that I do not expect anyone to imitate from the existing code are named parameters.
I marked this as a draft for now in the hope that it won't trigger the CI every time you push -- I'm still learning how this CI system works. When you have completed everything then mark it ready for review again.
Thanks for looking into this. I will start the documentation, was just waiting for someone to approve of the code.
Hi @GYuvanShankar , thanks, it's looking good! I'll start a review, in which I'll make some (or many) small comments in the code itself.
When implementing algorithms, of any kind, it's important to be really familiar with the literature on them. In this case there is at least one paper that demonstrates a defect with Karp's algorithm and an alternative solution: https://www.cs.colostate.edu/~rmm/minCycleMean.pdf
I recommend that you read widely on MCM and then come back with a discussion on which algorithm(s) you propose to implement and why. This is an interesting overview, although I have only glanced at it: https://www.researchgate.net/profile/Rajesh-Gupta-10/publication/2689582_An_Experimental_Study_of_Minimum_Mean_Cycle_Algorithms/links/546e071f0cf29806ec2e6dba/An-Experimental-Study-of-Minimum-Mean-Cycle-Algorithms.pdf
PS. One thing that I do not expect anyone to imitate from the existing code are named parameters. Why not? Are named parameters being deprecated or something?
PS. One thing that I do not expect anyone to imitate from the existing code are named parameters. Why not? Are named parameters being deprecated or something?
It was a courageous and ambitious experiment at the time (20 something years ago) but it adds an awful lot of complexity and maintenance burden to the code for questionable benefit. In the long run, I would like to strip them out. I think we could achieve similar benefits, if wanted, from much simpler overloads and stronger types.