Opened 6 years ago

Closed 6 years ago

#15603 closed enhancement (fixed)

"immutable=True" for Graph/Digraph __init__ and copy()

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.1
Component: graph theory Keywords:
Cc: SimonKing Merged in:
Authors: Nathann Cohen Reviewers: Simon King
Report Upstream: N/A Work issues:
Branch: u/SimonKing/ticket/15603 (Commits) Commit: b741bd4dde3167e4ab21e658dcd2f09a251d0337
Dependencies: #15278 Stopgaps:

Description (last modified by ncohen)

As promised on #15278, this ticket adds an 'immutable' keyword to the constructors of Graph/Digraph, and in 'copy()' too.

While I was at it, I tried to clean a bit the 'copy()' method, which now systematically checks its input. It should deal with every situation :-P

And I think I will have to clean the constructors of Graph/Digraph too at some point.

Nathann

Change History (22)

comment:1 Changed 6 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by ncohen

  • Branch changed from #15278 to u/ncohen/15603
  • Dependencies set to #15278

comment:3 Changed 6 years ago by git

  • Commit set to 5a4d6340601daac88c22edb88b03b9136013898b

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

5a4d634trac #15603: "immutable=True" for Graph/Digraph __init__ and copy()
9df004brebasing #15278 on 6.1.beta2
51d6328Trac 15278: Error messages explain how to create (im)mutable graph copy
2fc8a77Make digraphs using the static backend immutable and hashable
07bad46Merge branch 'u/ncohen/15491' of git://trac.sagemath.org/sage into ticket/15278
126b036Merge branch 'master' into ticket/15278
c774057Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.

comment:4 Changed 6 years ago by git

  • Commit changed from 5a4d6340601daac88c22edb88b03b9136013898b to 0dd973a4a048b7175950774d57676d50f56b0676

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

0dd973atrac #15603: "immutable=True" for Graph/Digraph __init__ and copy()
9df004brebasing #15278 on 6.1.beta2
51d6328Trac 15278: Error messages explain how to create (im)mutable graph copy
2fc8a77Make digraphs using the static backend immutable and hashable
07bad46Merge branch 'u/ncohen/15491' of git://trac.sagemath.org/sage into ticket/15278
126b036Merge branch 'master' into ticket/15278
c774057Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.

comment:5 Changed 6 years ago by ncohen

What do you think ? :-)

Nathann

comment:6 Changed 6 years ago by git

  • Commit changed from 0dd973a4a048b7175950774d57676d50f56b0676 to 7860f3997ae9ecd954f0696025fbb63e0219e78b

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

7860f39trac #15603: "immutable=True" for Graph/Digraph __init__ and copy()
2525d22Trac 15278: Fix syntax error in doc test
fcf9e30Trac 15278: Only graphs that use the static backend are identical with their copy
8fc9c94Merge branch 'develop' into ticket/15278
51d6328Trac 15278: Error messages explain how to create (im)mutable graph copy
2fc8a77Make digraphs using the static backend immutable and hashable
07bad46Merge branch 'u/ncohen/15491' of git://trac.sagemath.org/sage into ticket/15278
126b036Merge branch 'master' into ticket/15278
c774057Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.

comment:7 follow-up: Changed 6 years ago by SimonKing

The commit looks good, except for the spaces in front of colons and question marks... Do you add this space in your smileys, too? :- ? ; -)

I think we agreed that we'll use a new ticket to fix sage.combinat's hack with _immutable=True and our counter-hack with type-checking immutability. Of course, I first want to see if the tests pass before giving a positive review.

comment:8 in reply to: ↑ 7 Changed 6 years ago by ncohen

Yoooooo !

The commit looks good, except for the spaces in front of colons and question marks... Do you add this space in your smileys, too? :- ? ; -)

Argggggg T_T

Well right now I'm trying to read a spanish book (even though I don't speak a word of it)... At least I don't put their weird reversed question marks in the code :-PPP

I think we agreed that we'll use a new ticket to fix sage.combinat's hack with _immutable=True and our counter-hack with type-checking immutability. Of course, I first want to see if the tests pass before giving a positive review.

Yepyepyep, sounds right.

Nathann

comment:9 Changed 6 years ago by SimonKing

All tests pass, but I think I'll add a review commit, a bit later.

comment:10 Changed 6 years ago by SimonKing

Things that need to be done (in a review commit): In some place you explain the immutable=... optional argument, but in the example you use data_structure=... only. In some other place, you do this change:

     If the ``data_structure`` is equal to ``"static_sparse"``, then an
     immutable graph results. Note that this does not use the NetworkX data
     structure::
 
-          sage: G_imm = Graph(g, data_structure="static_sparse")
-          sage: H_imm = Graph(g, data_structure="static_sparse")
+          sage: G_imm = Graph(g, immutable=True)
+          sage: H_imm = Graph(g, immutable=True)
           sage: G_imm == H_imm == G == H
           True

Hence, the text is about data_structure, but you remove it from the test.

comment:11 follow-up: Changed 6 years ago by ncohen

"that need to be done" : will that be your review commit, or do you want me to do that ?

Nathann

comment:12 in reply to: ↑ 11 Changed 6 years ago by SimonKing

Replying to ncohen:

"that need to be done" : will that be your review commit, or do you want me to do that ?

I wrote "that need to be done (in a review commit)". Hence, I'll do it.

comment:13 Changed 6 years ago by ncohen

Oops sorry. I missed that, in my eagerness to see these patches in Sage ^^;

Nathann

comment:14 Changed 6 years ago by SimonKing

There is a naked NotImplementedError:

            sage: g = DiGraph(graphs.PetersenGraph(), immutable=True)
            sage: g.add_edge("Hey", "Heyyyyyyy")
            Traceback (most recent call last):
            ...
            NotImplementedError:

Should we care?

comment:15 Changed 6 years ago by SimonKing

            sage: g = graphs.PetersenGraph()
            sage: g = DiGraph(g.edges(),immutable=False)
            sage: g.add_edge("Hey", "Heyyyyyyy")
            sage: {g:1}[g]
            TypeError: This graph is mutable, and thus not hashable. Create an immutable copy by `g.copy(data_structure='static_sparse')`

Should the error message mention the other (more intuitive) possibility g.copy(immutable=True)?

comment:16 Changed 6 years ago by ncohen

Hmmmm... We could add an empty function for add_edge in the backend indeed. Depending on where the immutable graph comes from, the user may not have any idea of why this function is not implemented. Something like what add_vertex does.

Yes to your other comment about the exception raised by __hash__.

Nathann

comment:17 Changed 6 years ago by SimonKing

Since I want this to get over with and since my family plans to have an excursion today, I prefer to only fix the error message raised by __hash__, but leave the NotImplementedError as it is.

comment:18 Changed 6 years ago by ncohen

Ahahahah. Okay no prob. I'll fix that later in another patch ;-)

Nathann

comment:19 Changed 6 years ago by SimonKing

  • Branch changed from u/ncohen/15603 to u/SimonKing/ticket/15603
  • Created changed from 12/28/13 23:54:32 to 12/28/13 23:54:32
  • Modified changed from 01/03/14 10:41:31 to 01/03/14 10:41:31

comment:20 Changed 6 years ago by SimonKing

  • Commit changed from 7860f3997ae9ecd954f0696025fbb63e0219e78b to b741bd4dde3167e4ab21e658dcd2f09a251d0337
  • Reviewers set to Simon King
  • Status changed from needs_review to positive_review

I have added a review commit and run all tests in src/sage/graphs without error. Positive review (unless your aren't happy with my review commit or find that surprisingly the new error message appears in other parts of Sage too).


New commits:

b741bd4Trac 15603: More doctests, nicer error message

comment:21 Changed 6 years ago by ncohen

NOnono that' s great ! Thanks :-)

Nathann

comment:22 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.