search

hagberg / planarity

Planar graph algorithms
Other
38 stars 11 forks source link

Planarity is_planar hangs and never returns. #6

Closed agoldin closed 8 years ago

agoldin commented 8 years ago

This graph:

[(25, 28), (47, 29), (34, 36), (31, 13), (31, 14), (36, 34), (29, 47), (34, 39), (31, 55), (55, 2), (36, 39), (34, 51), (31, 2), (34, 15), (53, 4), (36, 51), (36, 15), (51, 39), (31, 20), (39, 51), (31, 44), (14, 13), (47, 36), (47, 34), (31, 41), (31, 3), (31, 40), (47, 39), (3, 41), (47, 15), (14, 20), (29, 36), (31, 7), (3, 56), (14, 44)] is planar and passes checks OK

Add one edge and it fails. is_planar never finishes on this:

[(25, 28), (47, 29), (34, 36), (31, 13), (31, 14), (36, 34), (29, 47), (34, 39), (31, 55), (55, 2), (36, 39), (34, 51), (31, 2), (34, 15), (53, 4), (36, 51), (36, 15), (51, 39), (31, 20), (39, 51), (31, 44), (14, 13), (47, 36), (47, 34), (31, 41), (31, 3), (31, 40), (47, 39), (3, 41), (47, 15), (14, 20), (29, 36), (31, 7), (3, 56), (14, 44),(14, 31)](few hours at least)

Version 0.3.1, installed via pip install planarity, python Python 2.7.11 |Anaconda custom (x86_64)| (default, Dec 6 2015, 18:57:58)

Mac OS Yosemite.

Thx! I will try to dig, but I am not sure where to start.

hagberg commented 8 years ago

Yes, I can verify that on my system too (python 2.7.6). I'm not sure where the issue is. It could be in the planarity C code. We could figure that out by writing a short C code. That would eliminate issues with the python interface.

There have been updates to the C code https://code.google.com/archive/p/planarity/ since I incorporated it here. Actually it looks like the code has moved here https://github.com/john-boyer-phd

hagberg commented 8 years ago

This was caused by adding parallel edges. You can cause @john-boyer-phd's C code to hang by adding parallel edges as you found out. The previous commit checks for and removes parallel edges before adding.

agoldin commented 8 years ago

Arggg! This probably makes sense. Thanks a lot for the pointer, I can get it working now!

john-boyer-phd commented 8 years ago

Hi guys, I wanted to take a moment to thank you for using my code in your projects, directly or indirectly, and also to reassure you regarding the extreme amount of testing that I've applied to the planarity code. Aside from billions of randomly generated graphs, the code has been tested on all 100+ billion graphs on 12 or fewer vertices (given a code tweak to allow for more than 3n edges, which is not necessary for determining planarity, but is helpful for inputting the denser graphs). None of these graphs have loops or duplicate edges, though. The "hang" you experienced is due to an optimization design point, rather than a bug. For planarity, loops and parallel edges do not affect whether or not the graph is planar, and many applications simply don't have them to begin with. So, the core algorithm implementation doesn't use up time checking whether those exist. Instead, the implementation assumes they are removed in preprocessing, for those who do have loops or duplicate edges. In my reference implementation, the code that reads graphs removes loops and duplicates, and the graph generators just don't generate them in the first place. One additional reason I am mentioning all of this is that, in the thread above, it is mentioned that there have been code updates since the code moved from Google Code to Github. However, as this behavior is in accord with design, no code changes were made related to this issue. Finally, the public new home is not under my github name but rather is under https://github.com/graph-algorithms/edge-addition-planarity-suite.
Thank you, John Boyer

hagberg commented 8 years ago

Hi @john-boyer-phd - Thanks for your note. This bug was completely my fault for not checking parallel edges on input. I did that now through the python interface and it works as expected. I also did update your code I distribute with this to the latest version in #3 and it works fine too.

john-boyer-phd commented 8 years ago

Hi Aric, The way you fixed it makes great sense (of course). Also, I added a link to your project onto the wiki page of mine so that anyone wanting to work in Python would know to use your work. Thanks for making it available to Python developers, Aric. Best regards, John Boyer

On Tue, May 17, 2016 at 2:53 PM, Aric Hagberg notifications@github.com wrote:

Hi @john-boyer-phd https://github.com/john-boyer-phd - Thanks for your note. This bug was completely my fault for not checking parallel edges on input. I did that now through the python interface and it works as expected. I also did update your code I distribute with this to the latest version in #3 https://github.com/hagberg/planarity/pull/3 and it works fine too.

— You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub https://github.com/hagberg/planarity/issues/6#issuecomment-219865798