Are all undirected simple cycles found with this implementation?
Closed this issue · 4 comments
From the documentation, it is shown (albeit not very clearly) that it outputs the cycle basis.
However, for the intermediate output of "step 3 (post process): cleanout the cycles by removing steps that are not part of the cycle and sort", could you clarify what those clean cycles are? Does it comprise all undirected simple cycles?
Thanks!
Hi,
Thanks for your interest in this.
Sorry, code quite messy, havn't got much time to work on this.
Actually, this is some sort of typo. It should be (just corrected it):
"cleanout the cycles by removing the vertices that are not part of the cycle and sort"
(pull latest in master branch).
An example in cleanCycles(): If we have as input
1-2-3-4-5-3, the returned cycle will be: 3-4-5
If I remember, this is needed because the bactracking process will go "all the way", and not stop when cycle found.
Have you tried make runsam ? You should get a file runsam.log showing the returned value of all the samples tried (should be 0, meaning we got the expected number of cycles). You can check the associated log files in out/.
Feel free if any other questions !
Thank you for the prompt reply! Could you also clarify if any part of your implementation supports finding all undirected simple cycles, as opposed to only the cycle basis?
Mmmh. I think I can't guarantee that, but maybe. It's been a while... Maybe backtracking and generating the initial set of cycles will hold these. But the proof would be pretty hard because AFAIK, there is no way to find the number of all undirected cycles in a graph.
No worries, thanks again for making this wrapper!