#29522 closed defect (fixed)
layout_planar fails on disconnected graphs
Reported by:  ghjfraymond  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  graph theory  Keywords:  layout planar embedding spring connected triangulate 
Cc:  Merged in:  
Authors:  JeanFlorent Raymond  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  ba68814 (Commits, GitHub, GitLab)  Commit:  ba688144e7482475e9239bcb2dc4e539781e500e 
Dependencies:  Stopgaps: 
Description (last modified by )
layout_planar
fails on disconnected graphs
sage: g = Graph(2) sage: g.layout_planar()  ValueError Traceback (most recent call last) <ipythoninput55590605c1dc8> in <module>() > 1 g.layout_planar() /home/jf/sage/local/lib/python3.7/sitepackages/sage/graphs/generic_graph.py in layout_planar(self, set_embedding, on_embedding, external_face, test, circular, **options) 5355 ''.format(external_face, self)) 5356 > 5357 _triangulate(G, G._embedding) 5358 5359 # Optional errorchecking /home/jf/sage/local/lib/python3.7/sitepackages/sage/graphs/schnyder.py in _triangulate(g, comb_emb) 68 # first make sure that the graph has at least 3 vertices, and that it is connected 69 if g.order() < 3: > 70 raise ValueError("A Graph with less than 3 vertices doesn't have any triangulation.") 71 if not g.is_connected(): 72 raise NotImplementedError("_triangulate() only knows how to handle connected graphs.") ValueError: A Graph with less than 3 vertices doesn't have any triangulation.
The error message is different when the graph has more vertices:
sage: g = Graph(3) sage: g.layout_planar()  NotImplementedError Traceback (most recent call last) <ipythoninput75590605c1dc8> in <module>() > 1 g.layout_planar() /home/jf/sage/local/lib/python3.7/sitepackages/sage/graphs/generic_graph.py in layout_planar(self, set_embedding, on_embedding, external_face, test, circular, **options) 5355 ''.format(external_face, self)) 5356 > 5357 _triangulate(G, G._embedding) 5358 5359 # Optional errorchecking /home/jf/sage/local/lib/python3.7/sitepackages/sage/graphs/schnyder.py in _triangulate(g, comb_emb) 70 raise ValueError("A Graph with less than 3 vertices doesn't have any triangulation.") 71 if not g.is_connected(): > 72 raise NotImplementedError("_triangulate() only knows how to handle connected graphs.") 73 74 # At this point we know that the graph is connected, has at least 3 NotImplementedError: _triangulate() only knows how to handle connected graphs.
With this ticket the function layout_planar
handles small graphs and graphs that are not connected. This is done by modifying the spring_layout_fast_split
function used for the spring layout so that it can work with any layout function.
The ticket also fixes bugs of layout_planar
 when called with
on_embedding
and an input graph that does not have an_embedding
attribute,  when called on a nonplanar graph,
Change History (17)
comment:1 Changed 16 months ago by
 Branch set to public/graphs/29522_schnyder
 Commit set to e688022665ceb0c54f19cc51fbe9da64c1a89c1f
 Status changed from new to needs_review
comment:2 Changed 16 months ago by
 Commit changed from e688022665ceb0c54f19cc51fbe9da64c1a89c1f to 9917e8c404b9901fbfdb5c90b96f13e7f1d42535
comment:3 Changed 16 months ago by
I changed the code of the function dealing with disconnected graphs for the spring layout (spring_layout_fast_split
) so that it can work with any layout function.
The new function dealing with disconnected graphs and arbitrary layout functions is layout_split
.
The layout_planar
function now calls it when the graph is not connected.
comment:4 Changed 16 months ago by
 Status changed from needs_review to needs_work
There are still some issues with my code. Working on it.
comment:5 Changed 16 months ago by
 Commit changed from 9917e8c404b9901fbfdb5c90b96f13e7f1d42535 to 4d6f2c3af6eaa7b7586d9860ae24d7545a164d4d
Branch pushed to git repo; I updated commit sha1. New commits:
374e3bd  trac #29522: fixed bug in layout_split with options `on_embedding` and `set_embedding`

6b882f0  trac #29522: in layout_planar, handling of small or disconnected graphs move to the beginning of the function

2566ee8  trac #29522: fixed bug when `on_embedding` is given and the input graph has no `_embedding` attribute

4d6f2c3  trac #29522: doctests

comment:6 Changed 16 months ago by
 Description modified (diff)
 Keywords spring added
 Status changed from needs_work to needs_review
It should be good now. I also fixed the following bug of layout_planar
:
H = graphs.LadderGraph(4) em = {0:[1,4], 4:[0,5], 1:[5,2,0], 5:[4,6,1], 2:[1,3,6], 6:[7,5,2], 3:[7,2], 7:[3,6]} H.layout_planar(on_embedding=em)  AttributeError Traceback (most recent call last) <ipythoninput1fa5d8c0766a4> in <module>() 1 H = graphs.LadderGraph(Integer(4)) 2 em = {Integer(0):[Integer(1),Integer(4)], Integer(4):[Integer(0),Integer(5)], Integer(1):[Integer(5),Integer(2),Integer(0)], Integer(5):[Integer(4),Integer(6),Integer(1)], Integer(2):[Integer(1),Integer(3),Integer(6)], Integer(6):[Integer(7),Integer(5),Integer(2)], Integer(3):[Integer(7),Integer(2)], Integer(7):[Integer(3),Integer(6)]} > 3 H.layout_planar(on_embedding=em) /home/jf/recherche/sage/local/lib/python3.7/sitepackages/sage/graphs/generic_graph.py in layout_planar(self, set_embedding, on_embedding, external_face, test, circular, **options) 5355 ''.format(external_face, self)) 5356 > 5357 _triangulate(G, G._embedding) 5358 5359 # Optional errorchecking AttributeError: 'Graph' object has no attribute '_embedding'
comment:7 Changed 16 months ago by
I have 3 failing doctests
sage t src/sage/graphs/schnyder.py ********************************************************************** File "src/sage/graphs/schnyder.py", line 73, in sage.graphs.schnyder._triangulate Failed example: g.layout_planar() Expected: Traceback (most recent call last): ... NotImplementedError: _triangulate() only knows how to handle connected graphs Got: {0: [0, 0], 1: [0, 1]} ********************************************************************** File "src/sage/graphs/schnyder.py", line 78, in sage.graphs.schnyder._triangulate Failed example: g.layout_planar() Expected: Traceback (most recent call last): ... ValueError: a Graph with less than 3 vertices doesn't have any triangulation Got: {0: [0, 0], 1: [0, 1]} ********************************************************************** File "src/sage/graphs/schnyder.py", line 83, in sage.graphs.schnyder._triangulate Failed example: g.layout_planar() Expected: Traceback (most recent call last): ... NotImplementedError: _triangulate() only knows how to handle connected graphs Got: {0: [0.5773502691896258, 0], 1: [1.1547005383792517, 0], 2: [1.7320508075688776, 0]}
comment:8 Changed 16 months ago by
 Commit changed from 4d6f2c3af6eaa7b7586d9860ae24d7545a164d4d to e034cbd904de50c5a633233c2d1053042481ebc3
Branch pushed to git repo; I updated commit sha1. New commits:
e034cbd  trac #29522: fixed failing doctests

comment:9 Changed 16 months ago by
My bad, I only ran tests for generic_graph.py
.
Tests now pass on the whole graphs
folder.
comment:10 Changed 16 months ago by
The patchbot complains because you must add at least one doctest in spring_layout_fast_split
.
comment:11 Changed 16 months ago by
 Commit changed from e034cbd904de50c5a633233c2d1053042481ebc3 to 9159384a018a1c54bc19b0b41b8f89d35c857e60
comment:12 Changed 16 months ago by
 Description modified (diff)
I added the missing test and also fixed the error message when one asks for a planar layout of a nonplanar graph. Previously:
sage: G = graphs.PetersenGraph() sage: G.layout_planar()  AttributeError Traceback (most recent call last) <ipythoninput233ae44b2d717> in <module>() > 1 G.layout_planar() /home/jf/recherche/sage/local/lib/python3.7/sitepackages/sage/graphs/generic_graph.py in layout_planar(self, set_embedding, on_embedding, external_face, test, circular, **options) 5355 ''.format(external_face, self)) 5356 > 5357 _triangulate(G, G._embedding) 5358 5359 # Optional errorchecking AttributeError: 'Graph' object has no attribute '_embedding'
Now it raises a ValueError
.
comment:13 Changed 16 months ago by
 Commit changed from 9159384a018a1c54bc19b0b41b8f89d35c857e60 to ba688144e7482475e9239bcb2dc4e539781e500e
Branch pushed to git repo; I updated commit sha1. New commits:
ba68814  pep8 review commit

comment:14 Changed 16 months ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
I did a small pep8 commit.
For me this patch is good.
comment:15 Changed 16 months ago by
Thanks!
comment:16 Changed 16 months ago by
 Branch changed from public/graphs/29522_schnyder to ba688144e7482475e9239bcb2dc4e539781e500e
 Resolution set to fixed
 Status changed from positive_review to closed
comment:17 Changed 15 months ago by
 Milestone changed from sage9.2 to sage9.1
I changed the order of the first tests in method
_triangulate
ofschnyder.py
.New commits:
trac #29522: make error messages more consistent