#9073: Handle multigraphs better in planarity
----------------------------+-----------------------------------------------
Reporter: boothby | Owner: jason, ncohen, rlm
Type: defect | Status: new
Priority: minor | Milestone: sage-4.4.3
Component: graph theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Changes (by boothby):
* owner: AlexGhitza => jason, ncohen, rlm
* priority: major => minor
* component: algebra => graph theory
* milestone: => sage-4.4.3
Old description:
> {{{
> sage: G = Graph({0:[1,1]}, multiedges=True)
> sage: G.is_planar()
> ---------------------------------------------------------------------------
> KeyError Traceback (most recent call
> last)
>
> /mnt/usb1/scratch/boothby/sage-4.4.2/<ipython console> in <module>()
>
> /mnt/usb1/scratch/boothby/sage-4.4.2/local/lib/python2.6/site-
> packages/sage/graphs/generic_graph.pyc in is_planar(self, on_embedding,
> kuratowski, set_embedding, set_pos)
> 2217 from sage.graphs.planarity import is_planar
> 2218 G = self.to_undirected()
> -> 2219 planar =
> is_planar(G,kuratowski=kuratowski,set_pos=set_pos,set_embedding=set_embedding)
> 2220 if kuratowski:
> 2221 bool_result = planar[0]
>
> /mnt/usb1/scratch/boothby/sage-4.4.2/local/lib/python2.6/site-
> packages/sage/graphs/planarity.so in sage.graphs.planarity.is_planar
> (sage/graphs/planarity.c:1327)()
>
> KeyError: -1
> sage: G = Graph({0:[1,1,1,1,1,1,1,1,1,1,1,1,1]}, multiedges=True)
> sage: G.is_planar()
> False
> }}}
New description:
This is version 4.4.2 with #8756 applied. Previous versions without #8756
have been observed to segfault.
{{{
sage: G = Graph({0:[1,1]}, multiedges=True)
sage: G.is_planar()
---------------------------------------------------------------------------
KeyError Traceback (most recent call
last)
/mnt/usb1/scratch/boothby/sage-4.4.2/<ipython console> in <module>()
/mnt/usb1/scratch/boothby/sage-4.4.2/local/lib/python2.6/site-
packages/sage/graphs/generic_graph.pyc in is_planar(self, on_embedding,
kuratowski, set_embedding, set_pos)
2217 from sage.graphs.planarity import is_planar
2218 G = self.to_undirected()
-> 2219 planar =
is_planar(G,kuratowski=kuratowski,set_pos=set_pos,set_embedding=set_embedding)
2220 if kuratowski:
2221 bool_result = planar[0]
/mnt/usb1/scratch/boothby/sage-4.4.2/local/lib/python2.6/site-
packages/sage/graphs/planarity.so in sage.graphs.planarity.is_planar
(sage/graphs/planarity.c:1327)()
KeyError: -1
sage: G = Graph({0:[1,1,1,1,1,1,1,1,1,1,1,1,1]}, multiedges=True)
sage: G.is_planar()
False
}}}
Suggested fix: mirror the recent changes to genus. That is, if
{{{set_embedding = False}}}, raise {{{NotImplementedError}}}. Otherwise,
call {{{self.to_simple()}}} and check if that's planar.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9073#comment:1>
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.
