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: sage-8.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:

Status badges

Description (last modified by dimpase)

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)

Change History (30)

comment:1 Changed 5 years ago by msaaltink

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.

comment:2 Changed 5 years ago by msaaltink

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.

comment:3 Changed 3 years ago by dimpase

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.

comment:4 Changed 3 years ago by dimpase

  • 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 dcoudert

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 dcoudert

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(2*pi) gives -2.44929359829e-16, sin(3*pi) gives 3.67394039744e-16, etc. Similar issues with cos(pi/2).

comment:7 Changed 3 years ago by dcoudert

well, the problem might be somewhere else...

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

comment:8 Changed 3 years ago by dcoudert

  • Authors changed from katestange to David Coudert
  • 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 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:

adea1f1trac #22050: round cos and sin in _circle_embedding
c45f9ebtrac #22050: adds parameter angle to _circle_embedding
259136ctrac #22050: use _circle_embedding for cycle, path, complete and star graphs
f56b3bdtrac #22050: use _circle_embedding for CircularLadderGraph
d0d0637trac #22050: fix add_path, add_cycle, add_clique
de55548trac #22050: fix layout when n==2 in CircularLadderGraph
e365a50trac #22050: use _circle_embedding in FriendshipGraph
58860b0trac #22050: use _circle_embedding in GeneralizedPetersenGraph
1c4ea29trac #22050: more use of _circle_embedding

comment:9 Changed 3 years ago by dimpase

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 ?

comment:10 Changed 3 years ago by git

  • Commit changed from 1c4ea2904f2b58ef8a5c29d9e9e04d04c5e62ae0 to 990e39bbaf4f0ab3b12fdf3c665e98a2826c89bc

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

a8683bbtrac #22050: Merged with 8.4.beta1
990e39btrac #22050: fix doctests

comment:11 Changed 3 years ago by dcoudert

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 dimpase

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

Last edited 3 years ago by dimpase (previous) (diff)

comment:13 follow-up: Changed 3 years ago by dcoudert

We can of course make it a method of GenericGraph.

comment:14 in reply to: ↑ 13 Changed 3 years ago by dimpase

Replying to dcoudert:

We can of course make it a method of GenericGraph.

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

comment:15 follow-up: Changed 3 years ago by dimpase

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

comment:16 in reply to: ↑ description Changed 3 years ago by 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.

comment:17 Changed 3 years ago by jdemeyer

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.

Last edited 3 years ago by jdemeyer (previous) (diff)

comment:18 in reply to: ↑ 15 Changed 3 years ago by dcoudert

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

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

comment:20 Changed 3 years ago by git

  • Commit changed from 990e39bbaf4f0ab3b12fdf3c665e98a2826c89bc to 98bacd3d4f25b59e4431ae67a42fde84634711dd

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

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

comment:21 Changed 3 years ago by dcoudert

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 dcoudert

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 ?

comment:23 Changed 3 years ago by dcoudert

  • Milestone set to sage-8.4

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

comment:24 Changed 3 years ago by git

  • Commit changed from 98bacd3d4f25b59e4431ae67a42fde84634711dd to 1f33553e55ea8acedfd5ea836735abc33accf7de

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

1f33553trac #: rebase on 8.4.beta3

comment:25 Changed 3 years ago by dcoudert

Successfully tested over beta7 (just in case).

comment:26 Changed 3 years ago by dimpase

We should fix pyflakes warnings (from the patchbot)

comment:27 Changed 3 years ago by git

  • Commit changed from 1f33553e55ea8acedfd5ea836735abc33accf7de to 9b3ffc60828e3993a2ad286d442916cf6ef68d78

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

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

comment:28 Changed 3 years ago by dcoudert

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

comment:29 Changed 3 years ago by dimpase

  • 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 vbraun

  • Branch changed from public/22050_use_circle_embedding to 9b3ffc60828e3993a2ad286d442916cf6ef68d78
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.