Opened 6 years ago

Closed 5 years ago

#15623 closed enhancement (fixed)

Immutable graph backend for Posets

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.2
Component: combinatorics Keywords:
Cc: SimonKing Merged in:
Authors: Nathann Cohen Reviewers: Simon King
Report Upstream: N/A Work issues:
Branch: u/SimonKing/ticket/15623 (Commits) Commit: c5b6d591982ef3e8d5902ecd9f7bfbd05cbb85a4
Dependencies: #15622 Stopgaps:

Description

At long, long last, it passes all tests :-P

Thank you Simon for your help with all this !!!

Nathann

Change History (26)

comment:1 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 6 years ago by ncohen

  • Branch set to u/ncohen/15623
  • Commit set to b6ed0387bb16a0102cc2792494d120df7b0fe292

Last 10 new commits:

b6ed038trac #15623: Immutable graph backend for Posets
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

comment:3 Changed 6 years ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues set to doctest error related with hash of mutable graphs

Merging all the dependencies (there are review commits that are not part of your branch), I get this error:

sage -t src/sage/combinat/posets/posets.py
**********************************************************************
File "src/sage/combinat/posets/posets.py", line 1488, in sage.combinat.posets.posets.FinitePoset.to_graph
Failed example:
    hash(G) == hash(G)
Exception raised:
    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.combinat.posets.posets.FinitePoset.to_graph[4]>", line 1, in <module>
        hash(G) == hash(G)
      File "cachefunc.pyx", line 1790, in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (sage/misc/cachefunc.c:9772)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 496, in __hash__
        raise TypeError("This graph is mutable, and thus not hashable. "
    TypeError: This graph is mutable, and thus not hashable. Create an immutable copy by `g.copy(data_structure='static_sparse')`
**********************************************************************
1 item had failures:
   1 of   6 in sage.combinat.posets.posets.FinitePoset.to_graph
    [837 tests, 1 failure, 11.73 s]

I am wondering: Shouldn't the error message say g.copy(immutable=False)? What thing did I forgot to merge?

But in any case, this error needs fixing. I'll see what I can do about it.

comment:4 Changed 6 years ago by SimonKing

Aha. This is about a function that returns

        from sage.graphs.graph import Graph
        G = Graph(self.hasse_diagram())
        return G

I suppose this should be

        from sage.graphs.graph import Graph
        return Graph(self.hasse_diagram(), immutable=True)

instead. The fact that the doctest is about hash shows that we want an immutable graph.

comment:5 Changed 6 years ago by SimonKing

  • Branch changed from u/ncohen/15623 to u/SimonKing/ticket/15623
  • Created changed from 01/02/14 21:36:09 to 01/02/14 21:36:09
  • Modified changed from 01/03/14 23:25:19 to 01/03/14 23:25:19

comment:6 Changed 6 years ago by SimonKing

  • Commit changed from b6ed0387bb16a0102cc2792494d120df7b0fe292 to ee8c39521a203a53876e435e271e59c38a4ca429
  • Status changed from needs_work to needs_review

With the review commit I just added, all tests should pass. "Should". I'll hopefully finish review tomorrow. PS: Again I had to change the commit field manually.

comment:7 Changed 6 years ago by SimonKing

  • Status changed from needs_review to needs_work

Please resolve the conflict with your new commit in #15622.

comment:8 Changed 6 years ago by ncohen

  • Branch changed from u/SimonKing/ticket/15623 to public/15623
  • Commit ee8c39521a203a53876e435e271e59c38a4ca429 deleted
  • Status changed from needs_work to needs_review

Done !

Nathann

comment:9 Changed 6 years ago by git

  • Commit set to 95cecd153d53a0666a3f1814831efc5cb15cb516

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

0f57805trac #15622: Immutable graphs must not be relabeled
b6ed038trac #15623: Immutable graph backend for Posets
ee8c395Trac 15623: Let to_graph return an immutable graph
dcb8a0btrac #15623: rebase on 6.1.beta4
529f785trac #15622: More informative exception message
2245c02Trac 15622: Review commit, fixing a misspelled doctest
60ad575trac #15622: Rebase on 6.1.beta3
6398780trac #15622: bugfix before #15623 gets merged
3531566trac #15623: Rebase on updated #15622
95cecd1trac #15623: Removing the hack from #15622, update a variable's name

comment:10 Changed 6 years ago by ncohen

I don't know how THIS could be read without the ticket numbers :-P

comment:11 Changed 6 years ago by SimonKing

  • Reviewers set to Simon King
  • Status changed from needs_review to positive_review

The merge was successful (looking at the code), and all tests pass.

comment:12 Changed 6 years ago by ncohen

Wow. Done :-P

Thaaaaaaaaaaank you very much Simon for all these reviews !

Nathann

Last edited 6 years ago by ncohen (previous) (diff)

comment:13 Changed 6 years ago by ncohen

Arggggggg !! Simon !! Simon !! :-P

It's because of these comments on the Tutte thread :-P

Nathann

comment:14 Changed 6 years ago by ncohen

  • Work issues doctest error related with hash of mutable graphs deleted

comment:15 Changed 5 years ago by tscrim

  • Status changed from positive_review to needs_work

This doesn't merge with the latest develop branch I'm afraid.

comment:16 Changed 5 years ago by SimonKing

  • Branch changed from public/15623 to u/SimonKing/ticket/15623
  • Modified changed from 01/27/14 07:20:18 to 01/27/14 07:20:18

comment:17 Changed 5 years ago by SimonKing

  • Commit changed from 95cecd153d53a0666a3f1814831efc5cb15cb516 to dae53af8e9fbc5b8cbf7da3de2eae92e2e9c0d56
  • Status changed from needs_work to needs_review

I attempted to merge the develop branch into the ticket branch. Nathann, could you check whether you think the merge was successful? I am running tests now. If it works, then I think it can be back to positive review


New commits:

dae53afMerge branch 'develop' into ticket/15623

comment:18 Changed 5 years ago by SimonKing

Arrgh. It seems I did wrong.

File "src/sage/graphs/generic_graph.py", line 845, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    hash(H)   # random
Exception raised:
    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.generic_graph.GenericGraph.?[32]>", line 1, in <module>
        hash(H)   # random
      File "cachefunc.pyx", line 1790, in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (sage/misc/cachefunc.c:9772)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 495, in __hash__
        return hash((tuple(self.vertices()), tuple(self.edges())))
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 8770, in vertices
        return sorted(list(self.vertex_iterator()), key=key)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/combinat/posets/elements.py", line 222, in __lt__
        return self._cmp(other) == -1 or False
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/combinat/posets/elements.py", line 155, in _cmp
        return self.parent().compare_elements(self,other)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/combinat/posets/posets.py", line 1851, in compare_elements
        elif self._hasse_diagram.is_less_than(j, i):
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/combinat/posets/hasse_diagram.py", line 245, in is_less_than
        return self.is_lequal(x,y)
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/combinat/posets/hasse_diagram.py", line 219, in is_lequal
        (i < j and j in self.breadth_first_search(i))
      File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 13335, in breadth_first_search
        for v in self._backend.breadth_first_search(start, ignore_direction = ignore_direction):
      File "c_graph.pyx", line 2636, in sage.graphs.base.c_graph.CGraphBackend.breadth_first_search (sage/graphs/base/c_graph.c:18478)
      File "c_graph.pyx", line 3039, in sage.graphs.base.c_graph.Search_iterator.__init__ (sage/graphs/base/c_graph.c:20167)
    AttributeError: 'StaticSparseBackend' object has no attribute 'vertex_ints'
**********************************************************************
1 item had failures:
   1 of 307 in sage.graphs.generic_graph.GenericGraph.?
    [2519 tests, 1 failure, 50.35 s]

comment:19 Changed 5 years ago by SimonKing

There are more errors concerning the missing attribute 'vertex_ints'.

Nathann, do you have an idea what went wrong?

comment:20 Changed 5 years ago by SimonKing

  • Status changed from needs_review to needs_work

comment:21 Changed 5 years ago by git

  • Commit changed from dae53af8e9fbc5b8cbf7da3de2eae92e2e9c0d56 to c5b6d591982ef3e8d5902ecd9f7bfbd05cbb85a4

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

c5b6d59Re-insert a bit of code that had been erroneously deleted in the previous merge commit

comment:22 Changed 5 years ago by SimonKing

  • Status changed from needs_work to needs_review

Ahaaaa! It seems that I did wrong when merging! Namely, I have removed the vertex_ints attribute.

In a second commit, I re-introduced it. Well, the joy of git. I don't dare to amend the merge commit and rather add an ugly second commit on top of a wrong first commit :-P

At least one of the failing doctests is now working. So, needs review again, and since I am the reviewer, I suppose I can revert to positive review as soon as make ptest passes for me!

comment:23 Changed 5 years ago by SimonKing

  • Status changed from needs_review to positive_review

make ptest does pass, hence, the merge seems to be successful, and hopefully I am entitled to revert to positive review.

comment:24 Changed 5 years ago by ncohen

Looks good to me, but I wasn't able to see directly from git how the conflicts were manually solved. So it works, but it's a bit scary that there does not seem to be a way to see that O_o

Thank you Simon for doing this ! I was away for 4 days, and rather unreachable in cold cold Hungary. I was there because I had promised a pretty girl a braid of dried chili, and a friend told me they had nice ones in Hungary :-P

Nathann

comment:25 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:26 Changed 5 years ago by vbraun

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