missing cycles in graphs

[alvaro562003]

Hello Seb,
Thank you for your codes. I hope i will be able to used it.
In sample 4, when i use this graph:
add_edge(0, 1, g);
add_edge(0, 2, g);
add_edge(0, 3, g);
add_edge(1, 2, g);
add_edge(2, 3, g);
add_edge(1, 5, g);
add_edge(3, 5, g);
add_edge(6, 7, g);
add_edge(7, 8, g);
add_edge(8, 6, g);
I expect to find 8 cycles.
Your code find only 5:
0,2, 1
0,3,5,1
0,3,2
1,5,3,2
6,7,8

Missing cycles:
0,3,2,1
0,2,3,5,1
0,3,5,1,3

Do you think it is a bug ?

[skramm]

Hi alvaro562003, Thanks for your interest in that code. 1 - I confirm that my code only computes the 5 cycles you mention, given the graph you describe. 2 - In the 3 that you describe as missing, 1 is actually false 0,3,5,1,3 (there is no connection between 1 and 3) See attached figure. Unless you meant 0,3,5,1,2 ? That would indeed be a cycle 3- ok, lets consider these 3 cycles: 0,3,2,1 0,2,3,5,1 0,3,5,1,2 These are actually cycles that can be computed from the 5 original cycles, by combining them. So it this a bug ? It is true that this code does not compute all cycles, but only the ones that can not be split into sub-cycles. By checking for common edges in the original set, you can computes the 3 additional. IMHO, this doesn't qualify as a bug, call that a feature ;-) But if you have any idea on improving the code, feel free to contribute ! Regards,

…

On 03/12/2016 12:47, alvaro562003 wrote: Hello Seb, Thank you for your codes. I hope i will be able to used it. In sample 4, when i use this graph: add_edge(0, 1, g); add_edge(0, 2, g); add_edge(0, 3, g); add_edge(1, 2, g); add_edge(2, 3, g); add_edge(1, 5, g); add_edge(3, 5, g); add_edge(6, 7, g); add_edge(7, 8, g); add_edge(8, 6, g); I expect to find 8 cycles. Your code find only 5: 0,2, 1 0,3,5,1 0,3,2 1,5,3,2 6,7,8 Missing cycles: 0,3,2,1 0,2,3,5,1 0,3,5,1,3 Do you think it is a bug ? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AF6H6g2Kwb7cp6J2A-SoNOJqzlC7FwkHks5rEVbagaJpZM4LDRdu>.

-- ----------------------------------------------- Sebastien Kramm - Enseignant chercheur IUT Rouen - Dép. RT & GEII Responsable pédagogique RT1 76500 - Elbeuf sur Seine Laboratoire d'Informatique, du Traitement de l'Information et des Systèmes (LITIS) http://www.litislab.fr/ INSA Rouen - AR108, Bougainville BP 08 - 76801 St Etienne du Rouvray Tel: 06.76.30.75.78 / 02.32.95.66.05 mailto:sebastien.kramm@univ-rouen.fr -----------------------------------------------

[schrottulk]

Hi skramm,

First of all, thanks a lot for your work!
I have a question regarding this example:
Why does your code output the cycle 1,5,3,2?
All edges of this cycle are already defined in the cycles 021, 023 and 5301.
Also the equation for the amount of cycles in a cycle basis e-v+c gives 10 - 8 + 2 = 4
(stated on page 4 here: https://www.geometrictools.com/Documentation/MinimalCycleBasis.pdf you marked this as a reference for your work)
Or did I get this wrong, shouldn't your code output the cycle basis of a planar graph?

Thanks in advance!

[skramm]

Hi schrottulk,
Thanks for you interest in this, I welcome all feedback.

I confirm your issue, you are right, this cycle (actually, it's 1-2-3-5) should not be present in output. I need some time to investigate, I'll let you know.
Regards,

[skramm]

Hi schrottulk,

Been working on that issue quite a lot these past hours... It was indeed a bug. I identified the problem and found a fix by adding a fourth post-process step. I also greatly simplified testing by adding two apps, one that generates a random graph and one that reads a graph from a textfile. All of this is in branch issue1 (not merged yet). More checking is needed, but I think I'm on the right track. More news to come.

[skramm]

Issue FIXED! I added a binary Gaussian Elimination step, thus the code now produces the correct number of cycles. Furthemore, the provided app makes sure that the computed cycles are all correct. "Official" 1.0 release planned in a couple of days (some cleaning left).