Opened 5 months ago

Closed 4 months ago

#28152 closed defect (fixed)

Planar graph layout does not respect clockwise ordering of neighbors in combinatorial embedding

Reported by: rburing Owned by:
Priority: major Milestone: sage-8.9
Component: graph theory Keywords: graph, planar, clockwise, embedding
Cc: Merged in:
Authors: Hendrik Schrezenmaier Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: b941f18 (Commits) Commit: b941f18364f47519b69c490a3de37fc4c30b6724
Dependencies: Stopgaps:

Description

Consider the claw S3:

S3 = Graph([[0,1,2,3],[[0,1],[0,2],[0,3]]])

The following combinatorial embedding is respected in the planar layout (the neighbors are in the given clockwise order):

S3.set_embedding({0: [1,2,3], 1: [0], 2: [0], 3: [0]})
S3.layout('planar', save_pos=True)
S3.show()

While this one isn't:

S3.set_embedding({0: [3,2,1], 1: [0], 2: [0], 3: [0]})
S3.layout('planar', save_pos=True)
S3.show()

In the latter, the neighbors are in the counterclockwise order (in fact the picture is the same as the former).

Strictly speaking, layout_planar (which is called by layout) does not promise to use the combinatorial embedding. But it does provide an option on_embedding which I assume should allow this:

S3.set_pos(S3.layout_planar(on_embedding={0: [3,2,1], 1: [0], 2: [0], 3: [0]}))

Still, the combinatorial embedding is not respected. I think this is because in layout_planar the line G.is_planar(set_embedding=True) executed unconditionally (totally ignoring on_embedding).

Change History (19)

comment:1 Changed 5 months ago by gh-hensc

  • Branch set to u/gh-hensc/planar_graph_layout_does_not_respect_clockwise_ordering_of_neighbors_in_combinatorial_embedding

comment:2 Changed 5 months ago by gh-hensc

  • Authors set to Hendrik Schrezenmaier
  • Commit set to dc578710df7f59c07dd2712615f83cab52e985f1
  • Status changed from new to needs_review

New commits:

13c4252Fixed bug concerning the combinatorial embedding of Schnyder drawings
dc57871Added doctest and fixed bugs to pass doctests

comment:3 Changed 5 months ago by dcoudert

A few stylistic comments. Recall that comments must be in 80 columns mode and that we do our best to follow the pep8 conventions.

-        TESTS::
-
-            Check the dependence of the computed position on the given
-            combinatorial embedding (:trac:`28152`).
+        TESTS:
+
+        Check the dependence of the computed position on the given
+        combinatorial embedding (:trac:`28152`)::
-    all triangles, and return the set of newly created edges. Also comb_emb
+    all triangles, and return the set of newly created edges. Also ``comb_emb``

pep8

-            comb_emb[w].insert(comb_emb[w].index(x),u)
-            comb_emb[u].insert(comb_emb[u].index(v),w)
+            comb_emb[w].insert(comb_emb[w].index(x), u)
+            comb_emb[u].insert(comb_emb[u].index(v), w)

80 columns mode

-    # Up to this point we did not take the order of the external face into account.
-    # Since the combinatorial embedding of a triangulated is only unique up to
-    # the choice of the outer face and reflection, this might lead to a reflection
-    # of the Schnyder drawing resulting from this labeling which is not conformal
-    # with comb_emb any longer. Therefore, we might have to swap the labels 1 and 2.
+    # Up to this point we did not take the order of the external face into
+    # account. Since the combinatorial embedding of a triangulation is unique
+    # up to the choice of the outer face and reflection, this might lead
+    # to a reflection of the Schnyder drawing resulting from this labeling which
+    # is not conformal with comb_emb any longer. Therefore, we might have to
+    # swap the labels 1 and 2.

I also did minor changes in above text. Please check.

Passes all tests with py3. I have not fully tested yet de functionality.

comment:4 Changed 5 months ago by chapoton

one failing doctest in src/sage/graphs/planarity.pyx, see patchbot report

comment:5 Changed 5 months ago by chapoton

  • Status changed from needs_review to needs_work

comment:6 Changed 5 months ago by rburing

Thanks for the effort so far. I suggest also to add a line of documentation, at least in layout_planar, explaining which combinatorial embedding is used when, e.g. "If on_embedding is provided then that combinatorial embedding is used for the layout. Otherwise: if a combinatorial embedding is set (e.g. using set_embedding) then that one is used, and if no combinatorial embedding is set then one is computed." (modify it to make it a true statement).

comment:7 Changed 5 months ago by git

  • Commit changed from dc578710df7f59c07dd2712615f83cab52e985f1 to 3c74ff602bbbfd0690fb967400dc1bd8fc513da4

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

2b7870dpep8
3c74ff6Removed special case of path of length 2

comment:8 Changed 5 months ago by git

  • Commit changed from 3c74ff602bbbfd0690fb967400dc1bd8fc513da4 to b3f4308b62f8ea2cb2460e807daeb87ac35a78de

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

b3f4308fixed typo

comment:9 Changed 5 months ago by git

  • Commit changed from b3f4308b62f8ea2cb2460e807daeb87ac35a78de to 2248ce7640f2b9b15638347522780fb697c964bc

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

2248ce7fixed typo

comment:10 Changed 5 months ago by git

  • Commit changed from 2248ce7640f2b9b15638347522780fb697c964bc to ec8e7b518b7c101c32b9e57ea63db8246f28e6ef

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

ec8e7b5edited documentation

comment:11 Changed 5 months ago by gh-hensc

  • Status changed from needs_work to needs_review

comment:12 Changed 5 months ago by gh-hensc

I fixed the pep8 and also fixed the bug that made the doctest fail. Now the patchbot passed all tests.

I also made the documentation more precise about which combinatorial embedding is used. But unfortunately it is not as rburing thought (and I think to be more intuitive, too) that on_embedding is always used if it is given. If set_embedding is set to True, then on_embedding is ignored. So the question is if we could/should/want to change this behavior.

Last edited 5 months ago by gh-hensc (previous) (diff)

comment:13 Changed 5 months ago by git

  • Commit changed from ec8e7b518b7c101c32b9e57ea63db8246f28e6ef to 07c6624b496d4e755ef9638c6c307013044b696c

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

07c6624Merge branch 'develop' of git://github.com/sagemath/sage into t/28152/planar_graph_layout_does_not_respect_clockwise_ordering_of_neighbors_in_combinatorial_embedding

comment:14 Changed 5 months ago by git

  • Commit changed from 07c6624b496d4e755ef9638c6c307013044b696c to da464d2d1893705084c8c70b7fb9ec526bf00a05

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

da464d2Merge branch 'develop' of git://github.com/sagemath/sage into t/28152/planar_graph_layout_does_not_respect_clockwise_ordering_of_neighbors_in_combinatorial_embedding

comment:15 Changed 4 months ago by gh-hensc

please review

comment:16 Changed 4 months ago by dcoudert

I have only a minor comment. Otherwise seems ok.

-            for (v,w) in labels[u]:
-                if labels[u][(v,w)] == 1:
-                    labels[u][(v,w)] = 2
-                elif labels[u][(v,w)] == 2:
-                    labels[u][(v,w)] = 1
+            for v, w in labels[u]:
+                if labels[u][v, w] == 1:
+                    labels[u][v, w] = 2
+                elif labels[u][v, w] == 2:
+                    labels[u][v, w] = 1

comment:17 Changed 4 months ago by git

  • Commit changed from da464d2d1893705084c8c70b7fb9ec526bf00a05 to b941f18364f47519b69c490a3de37fc4c30b6724

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

b828839minor improvement of code style
b941f18Merge branch 'develop'

comment:18 Changed 4 months ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

OK, LGTM.

comment:19 Changed 4 months ago by vbraun

  • Branch changed from u/gh-hensc/planar_graph_layout_does_not_respect_clockwise_ordering_of_neighbors_in_combinatorial_embedding to b941f18364f47519b69c490a3de37fc4c30b6724
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.