#12134: is_planar(set_pos=True) doesn't work with small graphs
-----------------------------+----------------------------------------------
Reporter: brunellus | Owner: jason, ncohen, rlm
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.8
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: Nathann Cohen | Author:
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by ncohen):
* reviewer: => Nathann Cohen
Old description:
> {{{
> sage: graphs.PathGraph(2).is_planar(set_pos=True)
> Traceback (click to the left of this block for traceback)
> ...
> NotImplementedError: _triangulate() only accepts graphs with more than 2
> vertices as input.
> }}}
>
> It is interesting that _triangulate raises NotImplementedError. The usual
> definition of a triangulation says something like "maximal planar graph",
> so it seems like PathGraph(2) is already triangulated, but if you ask
> [http://mathworld.wolfram.com/TriangulatedGraph.html Mathematica] or
> [http://oeis.org/A000109 OEIS], they don't accept this: according to this
> source there aren't any triangulated graphs on two vertices, so
> _triangulate should scream "This can't be done" and is_planar should
> avoid use _triangulate in this scenario, because there is no doubt that
> PathGraph(2) is planar.
>
> The error is only present when set_pos=True. Also, notice that
>
> {{{
> sage: graphs.PathGraph(1).is_planar(set_pos=True)
> True
> }}}
New description:
{{{
sage: graphs.PathGraph(2).is_planar(set_pos=True)
Traceback (click to the left of this block for traceback)
...
NotImplementedError: _triangulate() only accepts graphs with more than 2
vertices as input.
}}}
It is interesting that _triangulate raises NotImplementedError. The usual
definition of a triangulation says something like "maximal planar graph",
so it seems like PathGraph(2) is already triangulated, but if you ask
[http://mathworld.wolfram.com/TriangulatedGraph.html Mathematica] or
[http://oeis.org/A000109 OEIS], they don't accept this: according to this
source there aren't any triangulated graphs on two vertices, so
_triangulate should scream "This can't be done" and is_planar should avoid
use _triangulate in this scenario, because there is no doubt that
PathGraph(2) is planar.
The error is only present when set_pos=True. Also, notice that
{{{
sage: graphs.PathGraph(1).is_planar(set_pos=True)
True
}}}
Apply:
* [attachment:trac_12134_typo_fix.patch]
* [attachment:trac_12134_is_planar_special_cases.patch]
* [attachment:trac_12134_reviewer.patch]
--
Comment:
Helloooooooo !!
A good patch, with a several things to fix:
* There must always be a double semicolumn "::" before any Sage code
in the doctests, so that it appears as code in the documentation.
* The first doctest you add in planarity.pyx is written on one *very
long* linem and is not that easy to read `^^;`. We have ways to write
doctests on several lines when we need it, though ! You have many such
examples in files like graph.py (hint: look for the string "sage: for" to
see how it is done !). Sadly, this also means that the "long" flags have
to be copied on each line.
* There is no need to test connectedness at this moment :
{{{
if len(g) == 2 and g.is_connected():
}}}
There are two graphs on 2 vertices, and if the graph is not
connected it has been detected just previously by g.size() == 0.
* The .vertices() method does a lot of unnecessary stuff (for instance
is *sorts* the vertices before returning them), so it hurts a bit when I
see
{{{
{ g.vertices()[0]: [g.vertices()[1]], g.vertices()[1]: [g.vertices()[0]] }
}}}
I added a reviewer's patch to this ticket that does precisely that, so if
you can agree with its changes you can set this ticket to positively
reviewed ! `:-)`
Thank you for your patch !
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12134#comment:6>
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.
