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: |
Description (last modified by )
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)
Change History (20)
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
(cc me)
comment:3 Changed 10 years ago by
- Cc jason added
Changed 10 years ago by
comment:4 Changed 10 years ago by
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
comment:5 Changed 10 years ago by
- 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
- 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
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: ↓ 9 Changed 10 years ago by
- 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
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
- Milestone changed from sage-4.8 to sage-5.0
comment:11 Changed 10 years ago by
My God... I remember when "milestone 5.0" meant "whishlist" :-D
Nathann
comment:12 Changed 10 years ago by
comment:13 Changed 10 years ago by
- 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
comment:14 Changed 10 years ago by
- 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
Sorry, I should have noticed this. :-( Now it seems OK and tests show no error.
comment:16 Changed 10 years ago by
- Status changed from needs_review to positive_review
comment:17 Changed 10 years ago by
- Merged in set to sage-5.0.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
Ufff... For longer paths it seems fine. This error is also dependent on set_pos=True.