graph to_directed can have side effect when plotting

[kcrisman]

According to this ask.sagemath question, we have a very bizarre behavior for certain graphs:

G1=graphs.RandomGNP(5,0.5)
G1.plot(save_pos=True)
G2=G1.to_directed()
G2.delete_vertex(0)
G2.add_vertex(5)
G2.plot()
G1.plot()

gives

    485                 self._plot_components['vertex_labels'].append(text(str(v),
--> 486                     self._pos[v], rgbcolor=(0,0,0), zorder=8))

KeyError: 0

As if the zero vertex had been removed from G1. Plotting only one of them does NOT cause the error, and doing anything else seems fine. Reversing the order of the plotting gives KeyError: 5 as if the 5 vertex had never been added - in both cases it is the second plot which gives fits.

See comments below.

Component: graph theory

Author: David Coudert

Branch/Commit: 64fc436

Reviewer: Jeroen Demeyer

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

[dcoudert]

Commit: 34abce2

[dcoudert]

Author: David Coudert

[dcoudert]

comment:1

In the to_directedmethod, we have:

        D = DiGraph(name           = self.name(),
                    pos            = self._pos,
                    multiedges     = self.allows_multiple_edges(),
                    loops          = self.allows_loops(),
                    implementation = implementation,
                    data_structure = (data_structure if data_structure!="static_sparse"
                                      else "sparse")) # we need a mutable copy

Hence, the dictionary _pos storing the positions of the vertices is the same.

This patch solves this issue passing a copy of the position dictionary.

---

New commits:

34abce2

trac #22424: fix reported bug

[dcoudert]

Branch: u/dcoudert/22424

[kcrisman]

comment:2

Nice quick find. This makes perfect sense - and I see why it didn't show up before! Thanks.

You'll want to add some sort of doctest to verify that this is fixed.

[sagetrac-git]

Changed commit from 34abce2 to 840b584

[sagetrac-git]

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

840b584

trac #22424: doctest

[dcoudert]

comment:4

The problem reported in this patch is reproducible as:

sage: G1=graphs.Grid2RandomGNP(5,0.5)
sage: gp1 = G1.graphplot(save_pos=True)
sage: G2=G1.to_directed()
sage: G2.delete_vertex(0)
sage: G2.add_vertex(5)
sage: gp2 = G2.graphplot()
sage: gp1 = G1.graphplot()

So I added this test to the ticket rather than a show or plot call.

[sagetrac-git]

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

f0af172	trac #22424: Merged with 7.6.beta5
abbd053	trac #22424: corrected doctest

[sagetrac-git]

Changed commit from 840b584 to abbd053

[dcoudert]

comment:6

Ready for review

[jdemeyer]

comment:7

Passing a copy to the DiGraph constructor is not the right fix.

Instead, DiGraph should not modify its input!

[jdemeyer]

comment:8

In other words: do not work around the bug but fix the bug instead.

[sagetrac-git]

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

2d49d35

trac #22424: fix the bug

[sagetrac-git]

Changed commit from abbd053 to 2d49d35

[dcoudert]

comment:10

This should be a better way for both graphs and digraphs.

[dcoudert]

comment:12

Anyone to review this patch?

[jdemeyer]

comment:13

Two details:

1. there is some trailing whitespace in this patch.

2. why did you remove the plotting doctest in the last commit? Even if you changed the fix, you should keep that test.

[sagetrac-git]

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

f0ebd9c

trac #22424: remove trailing white space and and doctest

[sagetrac-git]

Changed commit from 2d49d35 to f0ebd9c

[dcoudert]

comment:15

I have put back the plotting doctest and removed the trailing white space (always hard to find).

[jdemeyer]

comment:16

There is still trailing whitespace here:

+        The position dictionary is not the input one (:trac:`22424`)::
+
+            sage: my_pos = {0:(0,0), 1:(1,1)} <-----------------------------
+            sage: G = Graph([[0,1], [(0,1)]], pos=my_pos)
+            sage: my_pos == G._pos
+            True
+            sage: my_pos is G._pos
+            False

[jdemeyer]

Reviewer: Jeroen Demeyer

[sagetrac-git]

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

ec12c65	trac #22424: Merged with 7.6.beta6
64fc436	trac #22424: bloody trailing white space

[sagetrac-git]

Changed commit from f0ebd9c to 64fc436

[dcoudert]

comment:18

Sorry, removed.

[dcoudert]

comment:20

Thank you.

[vbraun]

Changed branch from u/dcoudert/22424 to 64fc436