Opened 16 months ago

Closed 16 months ago

Last modified 15 months ago

#29522 closed defect (fixed)

layout_planar fails on disconnected graphs

Reported by: gh-jfraymond Owned by:
Priority: major Milestone: sage-9.1
Component: graph theory Keywords: layout planar embedding spring connected triangulate
Cc: Merged in:
Authors: Jean-Florent Raymond Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: ba68814 (Commits, GitHub, GitLab) Commit: ba688144e7482475e9239bcb2dc4e539781e500e
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-jfraymond)

layout_planar fails on disconnected graphs

sage: g = Graph(2)
sage: g.layout_planar()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-5-5590605c1dc8> in <module>()
----> 1 g.layout_planar()

/home/jf/sage/local/lib/python3.7/site-packages/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 error-checking

/home/jf/sage/local/lib/python3.7/site-packages/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)
<ipython-input-7-5590605c1dc8> in <module>()
----> 1 g.layout_planar()

/home/jf/sage/local/lib/python3.7/site-packages/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 error-checking

/home/jf/sage/local/lib/python3.7/site-packages/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 non-planar graph,

Change History (17)

comment:1 Changed 16 months ago by dcoudert

  • Authors set to David Coudert
  • Branch set to public/graphs/29522_schnyder
  • Commit set to e688022665ceb0c54f19cc51fbe9da64c1a89c1f
  • Status changed from new to needs_review

I changed the order of the first tests in method _triangulate of schnyder.py.


New commits:

e688022trac #29522: make error messages more consistent

comment:2 Changed 16 months ago by git

  • Commit changed from e688022665ceb0c54f19cc51fbe9da64c1a89c1f to 9917e8c404b9901fbfdb5c90b96f13e7f1d42535

Branch pushed to git repo; I updated commit sha1. New commits:

c6ad503trac #29522: handling disconnected graphs in layout_planar
9facf50trac #29522: doctests
9917e8ctrac #29522: order of arguments of layout_split + documentation

comment:3 Changed 16 months ago by gh-jfraymond

  • Authors changed from David Coudert to David Coudert, Jean-Florent Raymond

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 gh-jfraymond

  • 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 git

  • Commit changed from 9917e8c404b9901fbfdb5c90b96f13e7f1d42535 to 4d6f2c3af6eaa7b7586d9860ae24d7545a164d4d

Branch pushed to git repo; I updated commit sha1. New commits:

374e3bdtrac #29522: fixed bug in layout_split with options `on_embedding` and `set_embedding`
6b882f0trac #29522: in layout_planar, handling of small or disconnected graphs move to the beginning of the function
2566ee8trac #29522: fixed bug when `on_embedding` is given and the input graph has no `_embedding` attribute
4d6f2c3trac #29522: doctests

comment:6 Changed 16 months ago by gh-jfraymond

  • 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)
<ipython-input-1-fa5d8c0766a4> 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/site-packages/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 error-checking

AttributeError: 'Graph' object has no attribute '_embedding'

comment:7 Changed 16 months ago by dcoudert

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 git

  • Commit changed from 4d6f2c3af6eaa7b7586d9860ae24d7545a164d4d to e034cbd904de50c5a633233c2d1053042481ebc3

Branch pushed to git repo; I updated commit sha1. New commits:

e034cbdtrac #29522: fixed failing doctests

comment:9 Changed 16 months ago by gh-jfraymond

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 dcoudert

The patchbot complains because you must add at least one doctest in spring_layout_fast_split.

comment:11 Changed 16 months ago by git

  • Commit changed from e034cbd904de50c5a633233c2d1053042481ebc3 to 9159384a018a1c54bc19b0b41b8f89d35c857e60

Branch pushed to git repo; I updated commit sha1. New commits:

e5ca4f9trac #29522: added an error message when the input G is not planar and set_embedding=None and on_embedding=None and G._embedding is not set
9159384trac #29522: added test in spring_layout_fast_split

comment:12 Changed 16 months ago by gh-jfraymond

  • Description modified (diff)

I added the missing test and also fixed the error message when one asks for a planar layout of a non-planar graph. Previously:

sage: G = graphs.PetersenGraph()
sage: G.layout_planar()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-2-33ae44b2d717> in <module>()
----> 1 G.layout_planar()

/home/jf/recherche/sage/local/lib/python3.7/site-packages/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 error-checking

AttributeError: 'Graph' object has no attribute '_embedding'

Now it raises a ValueError.

comment:13 Changed 16 months ago by git

  • Commit changed from 9159384a018a1c54bc19b0b41b8f89d35c857e60 to ba688144e7482475e9239bcb2dc4e539781e500e

Branch pushed to git repo; I updated commit sha1. New commits:

ba68814pep8 review commit

comment:14 Changed 16 months ago by dcoudert

  • Authors changed from David Coudert, Jean-Florent Raymond to Jean-Florent Raymond
  • 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 gh-jfraymond

Thanks!

comment:16 Changed 16 months ago by vbraun

  • 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 mkoeppe

  • Milestone changed from sage-9.2 to sage-9.1
Note: See TracTickets for help on using tickets.