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:  sage8.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 S_{3}:
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
 Branch set to u/ghhensc/planar_graph_layout_does_not_respect_clockwise_ordering_of_neighbors_in_combinatorial_embedding
comment:2 Changed 5 months ago by
 Commit set to dc578710df7f59c07dd2712615f83cab52e985f1
 Status changed from new to needs_review
comment:3 Changed 5 months ago by
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
one failing doctest in src/sage/graphs/planarity.pyx, see patchbot report
comment:5 Changed 5 months ago by
 Status changed from needs_review to needs_work
comment:6 Changed 5 months ago by
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
 Commit changed from dc578710df7f59c07dd2712615f83cab52e985f1 to 3c74ff602bbbfd0690fb967400dc1bd8fc513da4
comment:8 Changed 5 months ago by
 Commit changed from 3c74ff602bbbfd0690fb967400dc1bd8fc513da4 to b3f4308b62f8ea2cb2460e807daeb87ac35a78de
Branch pushed to git repo; I updated commit sha1. New commits:
b3f4308  fixed typo

comment:9 Changed 5 months ago by
 Commit changed from b3f4308b62f8ea2cb2460e807daeb87ac35a78de to 2248ce7640f2b9b15638347522780fb697c964bc
Branch pushed to git repo; I updated commit sha1. New commits:
2248ce7  fixed typo

comment:10 Changed 5 months ago by
 Commit changed from 2248ce7640f2b9b15638347522780fb697c964bc to ec8e7b518b7c101c32b9e57ea63db8246f28e6ef
Branch pushed to git repo; I updated commit sha1. New commits:
ec8e7b5  edited documentation

comment:11 Changed 5 months ago by
 Status changed from needs_work to needs_review
comment:12 Changed 5 months ago by
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.
comment:13 Changed 5 months ago by
 Commit changed from ec8e7b518b7c101c32b9e57ea63db8246f28e6ef to 07c6624b496d4e755ef9638c6c307013044b696c
Branch pushed to git repo; I updated commit sha1. New commits:
07c6624  Merge 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
 Commit changed from 07c6624b496d4e755ef9638c6c307013044b696c to da464d2d1893705084c8c70b7fb9ec526bf00a05
Branch pushed to git repo; I updated commit sha1. New commits:
da464d2  Merge 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
please review
comment:16 Changed 4 months ago by
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
 Commit changed from da464d2d1893705084c8c70b7fb9ec526bf00a05 to b941f18364f47519b69c490a3de37fc4c30b6724
comment:18 Changed 4 months ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
OK, LGTM.
comment:19 Changed 4 months ago by
 Branch changed from u/ghhensc/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
New commits:
Fixed bug concerning the combinatorial embedding of Schnyder drawings
Added doctest and fixed bugs to pass doctests