doctests for planarity code #4509
Comments
|
comment:1
Attachment: long-doctest-segfault.patch.gz |
|
comment:2
With #4505, #4506 and #4507 applied I get the following for the first run only, i.e. no need to run the doctests twice: I am now digging into which graphs cause the trouble. Cheers, Michael |
|
comment:3
Attachment: planarity-segfault-trip-gdb.patch.gz planarity-segfault-trip-gdb.patch is a patch which supplies a poor man's assert: we see the problem when Jfirst is -1 and when the random memory location happens to be 2. The patch causes a segfault whenever Jfirst is -1. |
|
comment:4
|
|
comment:5
The issue pops up seemingly randomly, i.e. under valgrind there are complete runs that are ok while with others some tests cause the problem, but seemingly never the same test, i.e. the order is seemingly random. Jason has a theory what needs to happen for the issue to be triggered. Cheers, Michael |
|
comment:6
From an email to John Boyer: Going back to the graphEmbed.c file, the _CreateFwdArcLists function, it seems that theGraph->G[I].link[1] is -1 (i.e., is NIL) exactly when the vertex I has degree 0. Do you assume that the input graph does not have any isolated vertices? I think the reason we get random segfaults is because when Jfirst is -1, the if statement in this function is true depending on values associated with G[-1], which is a random value outside of our array. I see two possible fixes. If you have a different fix, we would love to hear it.
right after Jfirst is assigned (i.e., Jfirst = theGraph->G[I].link[1];) I believe this skips vertices that have degree 0. Will the algorithm work correctly with this modification?
Do you have any suggestions for which fix would be better? If fix #1 works, I prefer that one, as it is less preparation work before calling your code. |
|
comment:7
Hi. I just responded to Jason's email, but I'll post here too. The Boyer/Myrvold algorithm requires the graph be connected so for the workaround we need to look at each of the connected components of the graph. I can make a patch on Sunday, but I'd be happy to review anything you guys come up with before then. |
|
comment:9
If we've released for months and months without fixing this, it doesn't make sense to keep it as a blocker. |
|
comment:10
Works for me and valgrinds clean: I recommend we add the first patch and not the second, because it is unnecessary. |
|
comment:12
there we go. I repeat, only apply the first patch. |
|
comment:13
Replying to @jasongrout:
Here is the email I got in reply from John Boyer on 08 Dec 2008: I'll say up front that you're absolutely right that my reference implementation does not pay any real attention to isolated vertices as they have nothing really to do with the correctness of the algorithm. As you mentioned, it is trivial to filter out degree 0 vertices. For the same reason, anything short of a biconnected graph is really not important to correctness from the theoretic perspective. However, from the perspective of efficient implementation, it is advantageous that a graph doesn't have to be preprocessed to boil it down to biconnected components, and I paid a lot of attention to seamless handling of separable and indeed disconnected graphs, but the random graph generators (my own and from nauty) draw the line at zero degree vertices. Still, we may as well handle the disconnected graph "edge case" of a singleton vertex (wow, two graph theoretic puns in the same paragraph). So, I'll try to have a look at the fix you propose in the next short while and get back to you. That being said, from the lack of follow-on mail, I assume the fix you created is working out for you. But please do let me know if any other issues have arisen, and again my apologies for my delayed response. And here's another email I received from John on 25 May 2009: I know you haven't heard from me in a little while, but I have actually been hard at work on my planarity code (in my spare time of course). I looked into whether there would need to be any other changes needed to the core planar graph embedding code beyond what you proposed, and nothing jumped out at me. Unfortunately, that's not the same thing as making sure. Well, turns out that for a few years now I have been developing other algorithm extensions, such as outerplanar graph embedding, outerplanar obstruction isolation, search for subgraphs homeomorphic to K{2,3} and K{3,3}, and even graph drawing by visibility representation. Problem was, I would always take the "greedy" approach of augmenting a copy of the core planarity code. It seemed about time to pull all of this work together into one package and at the same time resurrect the connection to McKay's nauty "makeg" program so I could ensure that none of the work I was doing to pull all these things together was actually breaking anything. And of course, the bit you're interested in is that doing this also made it reasonable to see what I could do about removing the "-c" from the call to makeg, thereby ensuring proper operation on disconnected graphs, esp. those with isolated vertices. I also did lots of internal maintenance work to characterize certain code patterns with macros to further enhance knowledge of what is going on under the hood, so to speak. Unfortunately (or perhaps fortunately), I can no longer recall whether any other changes were actually required of the code you adopted into Sage in order to serve disconnected graphs. I don't think so, but the only code on which I am comfortable with claiming support for disconnected graphs is the new "version 2.0" code. The reason I say it is possibly fortunate is that it should be precious little effort for you to consider adopting this new code since I kept backwards compatibility at a high priority. You are quite unlikely to have done anything that is not supported under the new code, though I can help you if there are any issues. Best of all, you can actually get the code because I've made it publicly available from a Google Code project. http://code.google.com/p/planarity Now that I've completed the work of pulling together the algorithms I've created to date and ensuring they are well behaved on all graphs with fewer than 12 vertices, I've created a tag for version 2.0.0, so you can grab that rather than grabbing the trunk. Let me know if this is something you are interested in pursuing. So it sounds like we can maybe look at adding the new planarity code to Sage too? |
|
Author: Jason Grout |
|
Reviewer: Tom Boothby |
|
Changed reviewer from Tom Boothby to Tom Boothby, Minh Van Nguyen |
|
comment:14
I got a hunk failure when applying long-doctest-segfault.patch to Sage 4.3.1: I have rebased long-doctest-segfault.patch against Sage 4.3.1. Only apply trac_4509-doctest-rebase.patch, which needs some reviewing to make sure I didn't mess anything during the rebase. The docstring needs some adjusting, i.e. proper formatting to conform with Sphinx, but that belongs to another ticket. |
|
rebased vs. Sage 4.3.4.alpha1; apply on this |
|
comment:16
Attachment: trac_4509-doctest-rebase.patch.gz Looks good and applies cleanly to 4.3.5. Let's put it out of its misery. |
|
Merged: sage-4.4.alpha0 |
|
comment:17
Merged trac_4509-doctest-rebase.patch in 4.4.alpha0 |
I'm still seeing the same segfault that I worked around in the patch on #4505. Here is code that triggers it for me.
I've added that as a doctest to the planarity code.
For me, the segfault usually happens on the second run (the "b =" line), but occasionally happens on the first run.
CC: @rlmill @rbeezer
Component: graph theory
Author: Jason Grout
Reviewer: Tom Boothby, Minh Van Nguyen
Merged: sage-4.4.alpha0
Issue created by migration from https://trac.sagemath.org/ticket/4509
The text was updated successfully, but these errors were encountered: