Complete graph on 2 vertices doesn't show any edges

[katestange]

g = graphs.CompleteGraph(2)
g.show()

on the sage cell server http://sagecell.sagemath.org/ (running 'SageMath version 7.5.beta1, Release Date: 2016-10-31') 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)

CC: @dcoudert

Component: graph theory

Keywords: graph theory, complete graph

Author: David Coudert

Branch/Commit: 9b3ffc6

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/22050

[0adfa02f-507d-46c6-aa3b-f2437a2a5873]

comment:1

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:

sage: C2 = graphs.CycleGraph(2)
sage: C2.get_pos()
{0: (6.123233995736766e-17, 1.0), 1: (-1.8369701987210297e-16, -1.0)}
C2.show()

If you manually set positions close to zero, the same phenomenon of invisible lines appears:

h = Graph([(0,1)])
h.set_pos({0:(1e-3, 1), 1:(-1e-3,-1)})
h.show()

The same thing happens if the line is very nearly horizontal.

[0adfa02f-507d-46c6-aa3b-f2437a2a5873]

comment:2

This also happens with other graphics, e.g. a simple line:

sage: l = line2d([(1, 1e-6), (-1,-1e-6)])
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.

[dimpase]

comment:3

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.123233995736766e-17, 1.0), 1: (-1.8369701987210297e-16, -1.0)}

so this is basically very similar bug, fixed for CycleGraph(2) in #24512.

[dimpase]

comment:4

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?

[dimpase]

Description changed:

--- 
+++ 
@@ -4,3 +4,7 @@
 g.show()

on the sage cell server http://sagecell.sagemath.org/ (running 'SageMath version 7.5.beta1, Release Date: 2016-10-31') 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)

[dcoudert]

comment:5

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.

[dcoudert]

comment:6

How to know which sin/cos functions are used ? In a sage session sin(pi) gives 0. Inside _circular_embedding, sin(pi) gives 1.2246467991473532e-16, sin(2pi) gives -2.44929359829e-16, sin(3pi) gives 3.67394039744e-16, etc. Similar issues with cos(pi/2).

[dcoudert]

comment:7

well, the problem might be somewhere else...

sage: pi
pi
sage: float(pi)
3.141592653589793
sage: sin(float(pi))
1.2246467991473532e-16

[dcoudert]

Branch: public/22050_use_circle_embedding

[dcoudert]

Commit: 1c4ea29

[dcoudert]

Changed author from katestange to David Coudert

[dcoudert]

comment:8

I did the following:

• add rounding inside _circle_embedding so that sin(pi) is 0 and not 1.2246467991473532e-16.
• 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

[dimpase]

comment:9

While we are at it, why are _circle_embedding and _line_embedding not member functions of the GraphPlot class, but these ugly side-effect beasts? Shouldn't they be moved into GraphPlot ?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a8683bb	trac #22050: Merged with 8.4.beta1
990e39b	trac #22050: fix doctests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1c4ea29 to 990e39b

[dcoudert]

comment:11

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.

[dimpase]

comment:12

one can use set_pos() on a graph, why not _circular_embedding(), if moved to the same class as set_pos() ?

[dcoudert]

comment:13

We can of course make it a method of GenericGraph.

[dimpase]

comment:14

Replying to @dcoudert:

We can of course make it a method of GenericGraph.

perhaps, just add them as options for set_pos() ?

[dimpase]

comment:15

one way or another, these _circular_ and _line_embedding are ugly hacks, done without regard for the pre-existing design.

[jdemeyer]

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 work-around but not a structural fix.

[jdemeyer]

comment:17

It would be cleaner if _circle_embedding would be a method of graphs (as opposed to a stand-alone function). Also conceptually, it feels like it should be method.

[dcoudert]

comment:18

@dimpase: 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.

@jdemeyer: 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.

[dimpase]

comment:19

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 know---too many layers of classes etc for me :-)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

98bacd3

trac #22050: move methods to generic_graph.py and update usage

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 990e39b to 98bacd3

[dcoudert]

comment:21

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).

[dcoudert]

comment:22

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.123233995736766e-17, 1.0), 1: (-1.8369701987210297e-16, -1.0)}, xmax - xmin = 2.4492935982947064e-16 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 ?

[dcoudert]

comment:23

I opened #26106 to remove the duplicated code in tkz_picture.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 98bacd3 to 1f33553

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1f33553

trac #: rebase on 8.4.beta3

[dcoudert]

comment:25

Successfully tested over beta7 (just in case).

[dimpase]

comment:26

We should fix pyflakes warnings (from the patchbot)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1f33553 to 9b3ffc6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1649785	trac #22050: Merged with 8.4.beta7
9b3ffc6	trac #22050: pyflakes in families.py

[dcoudert]

comment:28

I fixed the pyflakes warning in families.py. Warning in generic_graph.py are addressed in #26289.

[dimpase]

Reviewer: Dima Pasechnik

[dimpase]

comment:29

OK, it's certainly a shame we could not get to the bottom of the matter, but it's still an improvement.

[vbraun]

Changed branch from public/22050_use_circle_embedding to 9b3ffc6