Qiskit
Implement simple_cycles() Johnson Algorithm
What is the expected enhancement?
Networkx has an algorithm for finding all cycles in a directed graph:
it's based on the Research of D. B. Johnson in 1975
Would love to see a rust implementation of that!
@mtreinish I appreciate the fast implementation! I tested your code on my current graph in comparison to networkx. Just want to let you know that there is probably a little bug in the code. On my current graph, networkx returns about 7000 cycle. The retworkx implementation returns only 1.
Maybe just a wrong condition
It's still a work in progress (hence the WIP prefix), it's still failing one of the tests I wrote too. I pushed up the commit to my fork mostly for saving so I had the work backed up. But, yeah the implementation isn't working fully yet, when I finish it then I'll open a pull request.
Hi @mtreinish, I just wanna kindly ask how your current workload is and when we could expect the algorithm to be finished. I know, you are doing that in your free time so absolutely no pressure. I am just curious and looking forward to the implementation because it would fit into my current university project perfectly.
I think I've got it working now, see https://github.com/Qiskit/retworkx/pull/633, let me know if you still have issues with it. I still need to do more testing and add more tests to the PR