Opened 5 years ago
Closed 3 years ago
#22050 closed defect (fixed)
Complete graph on 2 vertices doesn't show any edges
Reported by:  katestange  Owned by:  

Priority:  minor  Milestone:  sage8.4 
Component:  graph theory  Keywords:  graph theory, complete graph 
Cc:  dcoudert  Merged in:  
Authors:  David Coudert  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  9b3ffc6 (Commits, GitHub, GitLab)  Commit:  9b3ffc60828e3993a2ad286d442916cf6ef68d78 
Dependencies:  Stopgaps: 
Description (last modified by )
g = graphs.CompleteGraph(2) g.show()
on the sage cell server http://sagecell.sagemath.org/ (running 'SageMath version 7.5.beta1, Release Date: 20161031') and on Version 7.3 on my machine, running Ubuntu on X1 Carbon, produces a picture with no edges. Other sizes of complete graphs seem to work fine.
More similar errors are all seemingly related to matplotlib
being unable to draw not quite vertical line: same error in plotting
graphs.PathGraph(2,'circle')
, graphs.StarGraph(1)
, graphs.CircularLadderGraph(2)
,
graphs.StarGraph(2)
Change History (30)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
This also happens with other graphics, e.g. a simple line:
sage: l = line2d([(1, 1e6), (1,1e6)]) sage: l.set_aspect_ratio(1.0) sage: l.axes(False) sage: l
In several of the output formats, e.g. pgf and png, I do not see this line (but I do see it if I save to a postscript file). So I believe this is an issue with the plotting functions and not graph theory.
comment:3 Changed 3 years ago by
In Sage 8.3 I get correct CycleGraph(2)
drawing, but still wrong CompleteGraph(2)
drawing.
And indeed in the latter get_pos()
returns
{0: (6.123233995736766e17, 1.0), 1: (1.8369701987210297e16, 1.0)}
so this is basically very similar bug, fixed for CycleGraph(2)
in #24512.
comment:4 Changed 3 years ago by
 Cc dcoudert added
 Description modified (diff)
Same issue with graphs.PathGraph(2,'circle')
, graphs.StarGraph(1)
, graphs.CircularLadderGraph(2)
and
graphs.StarGraph(2)
 it attempts to plot the vertical,
but not quite, line...
And for some reason graphs.CircularLadderGraph(1)
throws an error, should there be a check?
comment:5 Changed 3 years ago by
These methods should use method _circular_embedding
from file graph_plot.py
, and we should put in it the corrections that we did in #24512 for CycleGraph
.
Note that I have recently corrected method _line_embedding
in #25403.
The embedding of the CircularLadderGraph
could be simplified to:
from sage.graphs.graph_plot import _circle_embedding _circle_embedding(G, list(range(n)), radius=1) _circle_embedding(G, list(range(n, 2*n)), radius=2)
The error in graphs.CircularLadderGraph(1)
is due to methods add_cycle
and add_path
that do not check if the input list of vertices are empty, of length 1, etc.
comment:6 Changed 3 years ago by
How to know which sin/cos functions are used ? In a sage session sin(pi) gives 0. Inside _circular_embedding
, sin(pi) gives 1.2246467991473532e16
, sin(2*pi) gives 2.44929359829e16, sin(3*pi) gives 3.67394039744e16, etc. Similar issues with cos(pi/2).
comment:7 Changed 3 years ago by
well, the problem might be somewhere else...
sage: pi pi sage: float(pi) 3.141592653589793 sage: sin(float(pi)) 1.2246467991473532e16
comment:8 Changed 3 years ago by
 Branch set to public/22050_use_circle_embedding
 Commit set to 1c4ea2904f2b58ef8a5c29d9e9e04d04c5e62ae0
 Status changed from new to needs_review
I did the following:
 add rounding inside
_circle_embedding
so thatsin(pi)
is 0 and not1.2246467991473532e16
.  add a parameter
angle
to_circle_embedding
 patch
add_circle
to avoid adding a loop when the list of vertices has a single node  use
_circle_embedding
in many methods
New commits:
adea1f1  trac #22050: round cos and sin in _circle_embedding

c45f9eb  trac #22050: adds parameter angle to _circle_embedding

259136c  trac #22050: use _circle_embedding for cycle, path, complete and star graphs

f56b3bd  trac #22050: use _circle_embedding for CircularLadderGraph

d0d0637  trac #22050: fix add_path, add_cycle, add_clique

de55548  trac #22050: fix layout when n==2 in CircularLadderGraph

e365a50  trac #22050: use _circle_embedding in FriendshipGraph

58860b0  trac #22050: use _circle_embedding in GeneralizedPetersenGraph

1c4ea29  trac #22050: more use of _circle_embedding

comment:9 Changed 3 years ago by
While we are at it, why are _circle_embedding
and _line_embedding
not member functions of the GraphPlot
class, but these ugly sideeffect beasts?
Shouldn't they be moved into GraphPlot
?
comment:10 Changed 3 years ago by
 Commit changed from 1c4ea2904f2b58ef8a5c29d9e9e04d04c5e62ae0 to 990e39bbaf4f0ab3b12fdf3c665e98a2826c89bc
comment:11 Changed 3 years ago by
If these methods are moved to GraphPlot
, how can we use them to set the embedding of parts of a graph ? For instance for the BarbellGraph
?
I just discovered another method producing a circular embedding: layout_circular
in generic_graph.py
. The difference is that it returns a dictionary, but clearly it should at least use _circular_embedding
or be combined with it.
I could for instance add a return_dict
parameter to _circular_embedding
to return a new dictionary instead of filling _pos
, or add parameters to layout_circular
to get the functionality of _circular_embedding
...
More generally, we could move methods for graph layout and visualization out of generic_graph.py
and gather them in a file for 2d and/or 3d plotting. That could ease our life for maintaining / simplifying / improving the code. For sure in another ticket.
comment:12 Changed 3 years ago by
one can use set_pos() on a graph, why not _circular_embedding(), if moved to the same class as set_pos() ?
comment:13 followup: ↓ 14 Changed 3 years ago by
We can of course make it a method of GenericGraph
.
comment:14 in reply to: ↑ 13 Changed 3 years ago by
Replying to dcoudert:
We can of course make it a method of
GenericGraph
.
perhaps, just add them as options for set_pos() ?
comment:15 followup: ↓ 18 Changed 3 years ago by
one way or another, these _circular_ and _line_embedding are ugly hacks, done without regard for the preexisting design.
comment:16 in reply to: ↑ description Changed 3 years ago by
Replying to katestange:
More similar errors are all seemingly related to
matplotlib
being unable to draw not quite vertical line
Did you ever try to find out why this is the case? It's obvious that matplotlib
is to blame here. Fixing the positions of vertices in Sage is a workaround but not a structural fix.
comment:17 Changed 3 years ago by
It would be cleaner if _circle_embedding
would be a method of graphs (as opposed to a standalone function). Also conceptually, it feels like it should be method.
comment:18 in reply to: ↑ 15 Changed 3 years ago by
@dima: I searched ticket and discovered that _line_embedding
was introduced in #12980 and _circle_embedding
in #12942 while layout_circular
was here before #7004... So you are fully right.
@Jeroen: no, I have not investigated matplotlib yet. We should do it, but I'm no expert in matplotlib. Also, the I have not checked the tikz
part yet, but without this patch you can see that there is a problem with the position of the vertices in _latex_
(values of x and y in \Vertex
lines).
sage: print(graphs.CompleteGraph(2)._latex_()) \begin{tikzpicture} \definecolor{cv0}{rgb}{0.0,0.0,0.0} \definecolor{cfv0}{rgb}{1.0,1.0,1.0} \definecolor{clv0}{rgb}{0.0,0.0,0.0} \definecolor{cv1}{rgb}{0.0,0.0,0.0} \definecolor{cfv1}{rgb}{1.0,1.0,1.0} \definecolor{clv1}{rgb}{0.0,0.0,0.0} \definecolor{cv0v1}{rgb}{0.0,0.0,0.0} % \Vertex[style={minimum size=1.0cm,draw=cv0,fill=cfv0,text=clv0,shape=circle},LabelOut=false,L=\hbox{$0$},x=5.0cm,y=5.0cm]{v0} \Vertex[style={minimum size=1.0cm,draw=cv1,fill=cfv1,text=clv1,shape=circle},LabelOut=false,L=\hbox{$1$},x=0.0cm,y=0.0cm]{v1} % \Edge[lw=0.1cm,style={color=cv0v1,},](v0)(v1) % \end{tikzpicture}
With this patch, the positions are the following, so vertical.
\Vertex[style={minimum size=1.0cm,draw=cv0,fill=cfv0,text=clv0,shape=circle},LabelOut=false,L=\hbox{$0$},x=2.5cm,y=5.0cm]{v0} \Vertex[style={minimum size=1.0cm,draw=cv1,fill=cfv1,text=clv1,shape=circle},LabelOut=false,L=\hbox{$1$},x=2.5cm,y=0.0cm]{v1}
I will try to make _circle_embedding
a method of GenericGraph
and unify with layout_circular
. It's better if such embedding is done in a single place.
comment:19 Changed 3 years ago by
I don't now how tikz pictures are done. I'd be surprised if they are produced via matplotlib. If they are produced in some other way I guess it's not matplotlib's bug, it's Sage one. But where I don't knowtoo many layers of classes etc for me :)
comment:20 Changed 3 years ago by
 Commit changed from 990e39bbaf4f0ab3b12fdf3c665e98a2826c89bc to 98bacd3d4f25b59e4431ae67a42fde84634711dd
Branch pushed to git repo; I updated commit sha1. New commits:
98bacd3  trac #22050: move methods to generic_graph.py and update usage

comment:21 Changed 3 years ago by
I have moved the methods to generic_graph.py
and update usage everywhere. It was used many many times...
I will check if I can understand the issue with tikz / matplotlib when we don't round sin(pi)
.
comment:22 Changed 3 years ago by
I'm also unable to guess what's going on with plot
/show
. Way to complicated for me.
In GraphLatex
, the method tkz_picture
computes xmin
, xmax
, ymin
, ymax
positions, and then the positions of the vertices are scaled to fill the specified image size (5*5 by default).
When xmin == xmax
, then vertices are placed at the middle of the x range, so by default 2.5.
But when we have G._pos = {0: (6.123233995736766e17, 1.0), 1: (1.8369701987210297e16, 1.0)}
, xmax  xmin = 2.4492935982947064e16
and so the vertices are spread in the x axis. Vertex 0 will be at (5.0, 1.0)
and vertex 1 at (0.0, 1.0)
.
So I think that the round(cos(...), 10)
is needed.
Question: some code is duplicated in tkz_picture
(certainly a copy/paste error). Should I open a new ticket to remove it or can I do it here ?
comment:23 Changed 3 years ago by
 Milestone set to sage8.4
I opened #26106 to remove the duplicated code in tkz_picture
.
comment:24 Changed 3 years ago by
 Commit changed from 98bacd3d4f25b59e4431ae67a42fde84634711dd to 1f33553e55ea8acedfd5ea836735abc33accf7de
Branch pushed to git repo; I updated commit sha1. New commits:
1f33553  trac #: rebase on 8.4.beta3

comment:25 Changed 3 years ago by
Successfully tested over beta7 (just in case).
comment:26 Changed 3 years ago by
We should fix pyflakes warnings (from the patchbot)
comment:27 Changed 3 years ago by
 Commit changed from 1f33553e55ea8acedfd5ea836735abc33accf7de to 9b3ffc60828e3993a2ad286d442916cf6ef68d78
comment:28 Changed 3 years ago by
I fixed the pyflakes warning in families.py
.
Warning in generic_graph.py
are addressed in #26289.
comment:29 Changed 3 years ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
OK, it's certainly a shame we could not get to the bottom of the matter, but it's still an improvement.
comment:30 Changed 3 years ago by
 Branch changed from public/22050_use_circle_embedding to 9b3ffc60828e3993a2ad286d442916cf6ef68d78
 Resolution set to fixed
 Status changed from positive_review to closed
This happens with some other graphs, too, for example
graphs.CycleGraph(2)
. In these cases, the layout is specified in the constructor and has positions extremely close to 0:If you manually set positions close to zero, the same phenomenon of invisible lines appears:
The same thing happens if the line is very nearly horizontal.