#4509: doctests for planarity code
----------------------------+-----------------------------------------------
Reporter: jason | Owner: ekirkman
Type: defect | Status: positive_review
Priority: critical | Milestone: sage-4.3.1
Component: graph theory | Keywords:
Author: Jason Grout | Upstream: N/A
Reviewer: Tom Boothby | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Changes (by newvalueoldvalue):
* cc: rlm, rbeezer (added)
* reviewer: => Tom Boothby
* author: => Jason Grout
Comment:
Replying to [comment:6 jason]:
> 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.
>
> 1. insert the lines:
> {{{
> if(Jfirst<0) {
> continue;
> }
> }}}
> 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?
>
>
> 2. Delete any vertices of degree 0 from the graph before calling the
algorithm. Of course, this does not change the planarity of the graph.
However, I couldn't find this limitation documented anywhere, and your
paper says that the algorithm works for disconnected graphs. Am I correct
in assuming that incorrect handling of degree 0 vertices is the problem
here?
>
> 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.
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?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4509#comment:13>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
