Opened 10 years ago

Closed 10 years ago

#12134 closed defect (fixed)

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

Reported by: brunellus Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords:
Cc: jason Merged in: sage-5.0.beta2
Authors: Lukáš Lánský Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by ncohen)

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:

Attachments (3)

trac_12134_typo_fix.patch (1.3 KB) - added by brunellus 10 years ago.
trac_12134_is_planar_special_cases.patch (2.4 KB) - added by brunellus 10 years ago.
trac_12134_reviewer.patch (3.1 KB) - added by ncohen 10 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 10 years ago by brunellus

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.

comment:2 Changed 10 years ago by ncohen

(cc me)

comment:3 Changed 10 years ago by jason

  • Cc jason added

Changed 10 years ago by brunellus

comment:4 Changed 10 years ago by brunellus

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.

Changed 10 years ago by brunellus

comment:5 Changed 10 years ago by brunellus

  • Status changed from new to needs_review

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

comment:6 Changed 10 years ago by ncohen

  • Description modified (diff)
  • Reviewers set to Nathann Cohen

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

comment:7 Changed 10 years ago by ncohen

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

comment:8 follow-up: Changed 10 years ago by brunellus

  • Status changed from needs_review to positive_review

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.

comment:9 in reply to: ↑ 8 Changed 10 years ago by ncohen

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

comment:10 Changed 10 years ago by jdemeyer

  • Milestone changed from sage-4.8 to sage-5.0

comment:11 Changed 10 years ago by ncohen

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

Nathann

comment:12 Changed 10 years ago by brunellus

  • Authors set to Lukáš Lánský

comment:13 Changed 10 years ago by jdemeyer

  • Status changed from positive_review to needs_work

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
**********************************************************************

Changed 10 years ago by ncohen

comment:14 Changed 10 years ago by ncohen

  • Status changed from needs_work to needs_review

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

comment:15 Changed 10 years ago by brunellus

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

comment:16 Changed 10 years ago by brunellus

  • Status changed from needs_review to positive_review

comment:17 Changed 10 years ago by jdemeyer

  • Merged in set to sage-5.0.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.