Opened 6 years ago

Closed 6 years ago

#15622 closed defect (fixed)

Immutable graphs must not be relabeled

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/ncohen/15622 (Commits) Commit: 6398780eca28da56527b3360d5fd597308517db9
Dependencies: #15619 Stopgaps:

Description

Now

sage: Graph(graphs.PetersenGraph(), immutable=True).relabel({})
...
ValueError: Thou shalt not relabel an immutable graph

Before, the following happened

sage: Graph(graphs.PetersenGraph(), data_structure="static_sparse").relabel({})
...
AttributeError: 'StaticSparseBackend' object has no attribute 'vertex_ints'

This is actually another bug, as there should be a vertex_ints variable in static sparse graphs. But that's another problem to be addressed in another ticket :-P

Nathann

Change History (28)

comment:1 Changed 6 years ago by ncohen

  • Branch set to u/ncohen/15622
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by ncohen

  • Dependencies changed from #15603 to #15619

comment:3 Changed 6 years ago by git

  • Commit set to 0f578050749912c5f5c66824cf50475aa74c0f23

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

0f57805trac #15622: Immutable graphs must not be relabeled
c441178trac #15619: bug in the former definition; exception to avoid it in the future
0229348trac #15619: Pickling of immutable graphs
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

comment:4 Changed 6 years ago by SimonKing

The code looks good. Perhaps the error message should hint at how to create a mutable copy?

comment:5 Changed 6 years ago by ncohen

OKayyyyyyyy.. What about this ?

Nathann

comment:6 Changed 6 years ago by git

  • Commit changed from 0f578050749912c5f5c66824cf50475aa74c0f23 to 529f7850c111c19522a8f18f9ce829e1e3a5b769

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

529f785trac #15622: More informative exception message

comment:7 Changed 6 years ago by SimonKing

  • Status changed from needs_review to needs_work

Oops:

sage -t --long src/sage/graphs/base/static_sparse_backend.pyx
**********************************************************************
File "src/sage/graphs/base/static_sparse_backend.pyx", line 422, in sage.graphs.base.static_sparse_backend.StaticSparseBackend.relabel
Failed example:
    g.relabel([],True)
Expected:
    Traceback (most recent call last):
    ...
    ValueError: Thou shalt not remove a vertex from an immutable graph
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.graphs.base.static_sparse_backend.StaticSparseBackend.relabel[2]>", line 1, in <module>
        g.relabel([],True)
    AttributeError: 'sage.graphs.base.static_sparse_backend.StaticSpars' object has no attribute 'relabel'

That is the only error, and I'll probably fix it in a review commit.

comment:8 Changed 6 years ago by SimonKing

WTF??????

When I do the obvious and change StaticSparseCGraph into StaticSparseBackend, I get

Failed example:
    g.relabel([],True)
Expected:
    Traceback (most recent call last):
    ...
    ValueError: Thou shalt not remove a vertex from an immutable graph
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.graphs.base.static_sparse_backend.StaticSparseBackend.relabel[2]>", line 1, in <module>
        g.relabel([],True)
      File "static_sparse_backend.pyx", line 428, in sage.graphs.base.static_sparse_backend.StaticSparseBackend.relabel (sage/graphs/base/static_sparse_backend.c:4740)
    ValueError: Thou shalt not relabel an immutable graph

Where does the blankline come from? And why is there no blankline when doing the test interactively?

comment:9 Changed 6 years ago by SimonKing

Ahaaa! You had a wrong class and a wrong error message in your test ("remove a vertex" versus "relabel").

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

I don't get what the "obvious change from StaticSparseCGraph into StaticSparseBackend" could be O_o

Nathann

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

Replying to ncohen:

I don't get what the "obvious change from StaticSparseCGraph into StaticSparseBackend" could be O_o

  • src/sage/graphs/base/static_sparse_backend.pyx

    diff --git a/src/sage/graphs/base/static_sparse_backend.pyx b/src/sage/graphs/base/static_sparse_backend.pyx
    index 9b5a8fe..e5b889e 100644
    a b class StaticSparseBackend(CGraphBackend): 
    417417
    418418        TEST::
    419419
    420             sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph
    421             sage: g = StaticSparseCGraph(graphs.PetersenGraph())
     420            sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend
     421            sage: g = StaticSparseBackend(graphs.PetersenGraph())
    422422            sage: g.relabel([],True)
    423423            Traceback (most recent call last):
    424424            ...
    425             ValueError: Thou shalt not remove a vertex from an immutable graph
     425            ValueError: Thou shalt not relabel an immutable graph
    426426
    427427        """
    428428        raise ValueError("Thou shalt not relabel an immutable graph")

StaticSparceCGraph simply is the wrong class.

comment:12 Changed 6 years ago by SimonKing

For the record: It already takes 5 minutes to push my review commit.

comment:13 Changed 6 years ago by SimonKing

  • Branch changed from u/ncohen/15622 to u/SimonKing/ticket/15622
  • Created changed from 01/02/14 21:20:19 to 01/02/14 21:20:19
  • Modified changed from 01/03/14 13:20:36 to 01/03/14 13:20:36

comment:14 Changed 6 years ago by ncohen

  • Branch changed from u/SimonKing/ticket/15622 to u/ncohen/15622

Oh. Ahem. Right O_O;;;;;;

Sorryyyyyyyyyyyyyyyyyyyyyyyyyyy O_O;;;;;

Nathann

Review commit : I often Ctrl+C it before it ends. Trac sends the mails almost instantaneously, the trac ticket is updated at the same time. I just have no idea what it does afterwards.

comment:15 Changed 6 years ago by SimonKing

  • Branch changed from u/ncohen/15622 to u/SimonKing/ticket/15622
  • Commit changed from 529f7850c111c19522a8f18f9ce829e1e3a5b769 to 2245c020cd80a1d248cf0a453270f4dbd9d12f36
  • Status changed from needs_work to positive_review

It seems that once more I have to manually upload the commit.

comment:16 Changed 6 years ago by ncohen

I think it's because you should set the branch name *before* pushing the commit. Otherwise nothing is triggered on the trac server's side.

Nathann

comment:17 Changed 6 years ago by ncohen

Okay. We are now in the Volker-Feared situation of a ticket which has a positive review, with a dependency which is still in needs_review :-P

Thanks for this commit !

Nathann

comment:18 Changed 6 years ago by ncohen

By the way, isn't the trac server 99999x times faster than yesterday ? Andrew said he would do something about it and it looks like he did O_O

Nathann

comment:19 Changed 6 years ago by vbraun

  • Milestone changed from sage-6.1 to sage-pending

comment:20 Changed 6 years ago by vbraun

  • Milestone changed from sage-pending to sage-6.1

comment:21 Changed 6 years ago by vbraun

  • Reviewers set to Simon King

comment:22 follow-up: Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

Various doctests fail (see also patchbot)

comment:23 Changed 6 years ago by ncohen

Gloops. Right.

comment:24 Changed 6 years ago by ncohen

  • Branch changed from u/SimonKing/ticket/15622 to u/ncohen/15622
  • Commit changed from 2245c020cd80a1d248cf0a453270f4dbd9d12f36 to 529f7850c111c19522a8f18f9ce829e1e3a5b769
  • Status changed from needs_work to needs_review

That's the only way I found to make this work before #15623 is merged T_T

Nathann

comment:25 Changed 6 years ago by ncohen

  • Commit changed from 529f7850c111c19522a8f18f9ce829e1e3a5b769 to 6398780eca28da56527b3360d5fd597308517db9

Okay, it looks like the automatic message does not work, but the branch is updated !

Nathann

comment:26 in reply to: ↑ 22 Changed 6 years ago by SimonKing

Replying to vbraun:

Various doctests fail (see also patchbot)

WTF? When I reviewed it, things worked. Or did I accidentally merge other tickets that aren't dependencies for this?

comment:27 Changed 6 years ago by SimonKing

  • Status changed from needs_review to positive_review

Hooray. After pulling from the ticket branch and merging with the current develop branch, make ptest results in

All tests passed!
----------------------------------------------------------------------
Total time for all tests: 3791.7 seconds
    cpu time: 6340.1 seconds
    cumulative wall time: 7304.6 seconds

Nathann's last commit looks like the right thing to do. Hence, I hope this time my positive review will persist...

comment:28 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.