#8756: random segfault in planarity.pyx test
----------------------------+-----------------------------------------------
Reporter: was | Owner: jason, ncohen, rlm
Type: defect | Status: needs_work
Priority: blocker | Milestone: sage-4.4.2
Component: graph theory | Keywords:
Author: Jason Grout | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Comment(by jason):
John Boyer also said this to me about the new planarity code:
"I had to change NONPLANAR to NONEMBEDDABLE due to outerplanarity, but
otherwise there's really only additions to the interface, so you're in
pretty good shape once you can compile. The only other question I would
have is whether you have any code that traversed adjacency lists, or do
you just call my functions. I found I got more speed when I changed from
a circular list that included the vertex. There is a macro you can define
to put the CIRCULAR back in the lists, but the code is faster if you don't
use it. Moreover, if you traverse adjacency lists using my actual
functions, you were good anyway.
"You should also note that my library sets a default graph size capable of
accommodating 3N edges (6N arcs, or half edges), but it is easy in the new
version to override that by calling gp_EnsureArcCapacity(). Of course,
the 3N setting is there because you only need 3N of the edges in any graph
to ensure that it comes to the right conclusion for any of the planarity-
related algorithms in the current package. My code that called nauty
would increase the arc capacity to ensure the whole graph was processed,
but it's your choice whether you want to do that.
"You should also note that the latest copy of the package contains a new
algorithm that is not strictly planarity-related. It creates a correct
coloring of a graph using minimum degree selection. However, it also
implements a special technique that ensures any planar graph will have at
most 5 colors. And linear time in the size of the graph of course. "
The third patch above makes the necessary changes in Sage regarding
NONPLANAR vs. NONEMBEDDABLE. The other issues should be checked, though.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8756#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.
