#4509: doctests for planarity code
--------------------------+-------------------------------------------------
Reporter: jason | Owner: rlm
Type: defect | Status: new
Priority: blocker | Milestone: sage-3.2
Component: graph theory | Resolution:
Keywords: |
--------------------------+-------------------------------------------------
Comment (by 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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4509#comment:6>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
