Opened 4 years ago

Closed 4 years ago

#22424 closed defect (fixed)

graph to_directed can have side effect when plotting

Reported by: kcrisman Owned by:
Priority: major Milestone: sage-7.6
Component: graph theory Keywords:
Cc: Merged in:
Authors: David Coudert Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: 64fc436 (Commits) Commit: 64fc4364ec46e36060597033e27f7e19a006f7e9
Dependencies: Stopgaps:

Description (last modified by dcoudert)

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.

Change History (21)

comment:1 Changed 4 years ago by dcoudert

  • Authors set to David Coudert
  • Branch set to u/dcoudert/22424
  • Commit set to 34abce2d0ea0e270a517d5399308894ace98abac
  • Description modified (diff)
  • Status changed from new to needs_review

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:

34abce2trac #22424: fix reported bug

comment:2 Changed 4 years ago by kcrisman

  • Status changed from needs_review to needs_work

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.

comment:3 Changed 4 years ago by git

  • Commit changed from 34abce2d0ea0e270a517d5399308894ace98abac to 840b584c9f04ab4ccc6f8efae5fdcc3213fe2fd3

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

840b584trac #22424: doctest

comment:4 Changed 4 years ago by dcoudert

  • Status changed from needs_work to needs_review

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.

comment:5 Changed 4 years ago by git

  • Commit changed from 840b584c9f04ab4ccc6f8efae5fdcc3213fe2fd3 to abbd05308299c97c7b0eb272a240b73c537350e2

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

f0af172trac #22424: Merged with 7.6.beta5
abbd053trac #22424: corrected doctest

comment:6 Changed 4 years ago by dcoudert

Ready for review

comment:7 Changed 4 years ago by jdemeyer

  • Status changed from needs_review to needs_work

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

Instead, DiGraph should not modify its input!

comment:8 Changed 4 years ago by jdemeyer

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

comment:9 Changed 4 years ago by git

  • Commit changed from abbd05308299c97c7b0eb272a240b73c537350e2 to 2d49d35b604259da7a9e2d2c660486085d657b0f

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

2d49d35trac #22424: fix the bug

comment:10 Changed 4 years ago by dcoudert

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

comment:11 Changed 4 years ago by dcoudert

  • Status changed from needs_work to needs_review

comment:12 Changed 4 years ago by dcoudert

Anyone to review this patch?

comment:13 Changed 4 years ago by jdemeyer

Two details:

  1. there is some trailing whitespace in this patch.
  1. why did you remove the plotting doctest in the last commit? Even if you changed the fix, you should keep that test.

comment:14 Changed 4 years ago by git

  • Commit changed from 2d49d35b604259da7a9e2d2c660486085d657b0f to f0ebd9ceeec6be2126f65df1c7829c019e709764

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

f0ebd9ctrac #22424: remove trailing white space and and doctest

comment:15 Changed 4 years ago by dcoudert

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

comment:16 Changed 4 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to needs_work

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

comment:17 Changed 4 years ago by git

  • Commit changed from f0ebd9ceeec6be2126f65df1c7829c019e709764 to 64fc4364ec46e36060597033e27f7e19a006f7e9

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

ec12c65trac #22424: Merged with 7.6.beta6
64fc436trac #22424: bloody trailing white space

comment:18 Changed 4 years ago by dcoudert

  • Status changed from needs_work to needs_review

Sorry, removed.

comment:19 Changed 4 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:20 Changed 4 years ago by dcoudert

Thank you.

comment:21 Changed 4 years ago by vbraun

  • Branch changed from u/dcoudert/22424 to 64fc4364ec46e36060597033e27f7e19a006f7e9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.