is_planar(set_pos=True) doesn't work with small graphs

[15606e31-f165-4fa5-94d5-bd9bfb0e1636]

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 Mathematica or 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

CC: @jasongrout

Component: graph theory

Author: Lukáš Lánský

Reviewer: Nathann Cohen

Merged: sage-5.0.beta2

Issue created by migration from https://trac.sagemath.org/ticket/12134

[15606e31-f165-4fa5-94d5-bd9bfb0e1636]

comment:1

sage: graphs.PathGraph(3).is_planar(set_pos=True)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_30.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("Z3JhcGhzLlBhdGhHcmFwaCgzKS5pc19wbGFuYXIoc2V0X3Bvcz1UcnVlKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>

  File "/tmp/tmpcidEK0/___code___.py", line 3, in <module>
    exec compile(u'graphs.PathGraph(_sage_const_3 ).is_planar(set_pos=True)
  File "", line 1, in <module>

  File "/sagenb/sage_install/sage-4.7.2/local/lib/python2.6/site-packages/sage/graphs/generic_graph.py", line 2572, in is_planar
    planar = is_planar(G,kuratowski=kuratowski,set_pos=set_pos,set_embedding=set_embedding)
  File "planarity.pyx", line 143, in sage.graphs.planarity.is_planar (sage/graphs/planarity.c:1574)
  File "/sagenb/sage_install/sage-4.7.2/local/lib/python2.6/site-packages/sage/graphs/generic_graph.py", line 2760, in set_planar_positions
    self.layout(layout = "planar", save_pos = True, test = test, **layout_options)
  File "/sagenb/sage_install/sage-4.7.2/local/lib/python2.6/site-packages/sage/graphs/generic_graph.py", line 12753, in layout
    pos = getattr(self, "layout_%s"%layout)(dim = dim, **options)
  File "/sagenb/sage_install/sage-4.7.2/local/lib/python2.6/site-packages/sage/graphs/generic_graph.py", line 2859, in layout_planar
    extra_edges = _triangulate( G, G._embedding)
  File "/sagenb/sage_install/sage-4.7.2/local/lib/python2.6/site-packages/sage/graphs/schnyder.py", line 67, in _triangulate
    if len(g.neighbors(vertex_list[0]) == 2):          # figure our which of the vertices already has two neighbors
TypeError: object of type 'bool' has no len()

Ufff... For longer paths it seems fine. This error is also dependent on set_pos=True.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:2

(cc me)

[15606e31-f165-4fa5-94d5-bd9bfb0e1636]

Attachment: trac_12134_typo_fix.patch.gz

[15606e31-f165-4fa5-94d5-bd9bfb0e1636]

comment:4

The patch resolves P_3 error -- it was merely a typo. The main problem is independent of this and I'll try to fix it later this week.

[15606e31-f165-4fa5-94d5-bd9bfb0e1636]

comment:5

Attachment: trac_12134_is_planar_special_cases.patch.gz

OK, that should be it. Please apply both patches. This should also solve #10139.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Reviewer: Nathann Cohen

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Description changed:

--- 
+++ 
@@ -15,3 +15,8 @@
 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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:6

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:7

Arg... I forgot about those %#$)@#(*%&& loops on edges. Sorry about my remark on your second call to is_connected, I updated my patch so that it sticks to your version on this point... Anyway, it's only a graph on 2 nodes :-p

Nathann

[15606e31-f165-4fa5-94d5-bd9bfb0e1636]

comment:8

Thanks for these remarks. I'll look into the other patches I sent and correct similar errors. :-)

If we suppose that the function planarity.is_planar is only accessed by generic_graph.is_planar, then there shouldn't be any loops at this moment, because the generic_graph function makes a graph simple first. I'm not sure if that's true, but I must admit I didn't wrote the code with this in mind -- I just didn't notice that disconected case was handled by previous change. :-)

I plan to work with this more. For example, it seems to me that teaching _triangulate how to handle disconnected cases shouldn't be very hard, as allowing embedding of multigraphs. I guess this can be usefull for #6236.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:9

If we suppose that the function planarity.is_planar is only accessed by generic_graph.is_planar, then there shouldn't be any loops at this moment, because the generic_graph function makes a graph simple first. I'm not sure if that's true, but I must admit I didn't wrote the code with this in mind -- I just didn't notice that disconected case was handled by previous change. :-)

Hmmmm... Well, anyway that's not such a horrible problem :-)`

I plan to work with this more. For example, it seems to me that teaching _triangulate how to handle disconnected cases shouldn't be very hard, as allowing embedding of multigraphs. I guess this can be usefull for #6236.

+1 for the idea, and +1 for your relationship with Sage's source code. The lad knows a lot of stuff I do not know myself, but its education is still lacking on many points.

By the way, you should add your name to the "Authors" field of the ticket, lest the guy above (the release manager) .set the ticket back to "needs_work"

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:11

My God... I remember when "milestone 5.0" meant "whishlist" :-D

Nathann

[15606e31-f165-4fa5-94d5-bd9bfb0e1636]

Author: Lukáš Lánský

[jdemeyer]

comment:13

I get a doctest error:

sage -t  -force_lib devel/sage/sage/graphs/planarity.pyx
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta1/devel/sage-main/sage/graphs/planarity.pyx", line 68:
    sage: for i,g in enumerate(atlas_graphs):
          if (not g.is_connected() or i==Integer(0)):
              continue
          try:
              _ = g.is_planar(set_embedding=True, set_pos=True)
          except:
              print "There is something wrong here !"
              break
Exception raised:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_1[6]>", line 1, in <module>
        for i,g in enumerate(atlas_graphs):###line 68:
    sage: for i,g in enumerate(atlas_graphs):
    NameError: name 'atlas_graphs' is not defined
**********************************************************************

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:14

Attachment: trac_12134_reviewer.patch.gz

Arggggggg.... Patch updated :-/

The missing variable was declared with a "# long time" flag, so the doctest was running with the -long flag and we missed it O_o

I set the whole thing to "long" in the end.

Lukasz can you give it another look ?

Nathann

[15606e31-f165-4fa5-94d5-bd9bfb0e1636]

comment:15

Sorry, I should have noticed this. :-( Now it seems OK and tests show no error.

[jdemeyer]

Merged: sage-5.0.beta2