layout_planar fails on disconnected graphs #29522
Description
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_embeddingand an input graph that does not have an_embeddingattribute, - when called on a non-planar graph,
Component: graph theory
Keywords: layout planar embedding spring connected triangulate
Author: Jean-Florent Raymond
Branch/Commit: ba68814
Reviewer: David Coudert
Issue created by migration from https://trac.sagemath.org/ticket/29522