Opened 9 years ago
Closed 9 years ago
#15623 closed enhancement (fixed)
Immutable graph backend for Posets
Reported by:  Nathann Cohen  Owned by:  

Priority:  major  Milestone:  sage6.2 
Component:  combinatorics  Keywords:  
Cc:  Simon King  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Simon King 
Report Upstream:  N/A  Work issues:  
Branch:  u/SimonKing/ticket/15623 (Commits, GitHub, GitLab)  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 9 years ago by
Status:  new → needs_review 

comment:2 Changed 9 years ago by
Branch:  → u/ncohen/15623 

Commit:  → b6ed0387bb16a0102cc2792494d120df7b0fe292 
comment:3 Changed 9 years ago by
Status:  needs_review → needs_work 

Work issues:  → 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/sitepackages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/king/Sage/git/sage/local/lib/python2.7/sitepackages/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/sitepackages/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 9 years ago by
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 9 years ago by
Branch:  u/ncohen/15623 → u/SimonKing/ticket/15623 

Created:  Jan 2, 2014, 9:36:09 PM → Jan 2, 2014, 9:36:09 PM 
Modified:  Jan 3, 2014, 11:25:19 PM → Jan 3, 2014, 11:25:19 PM 
comment:6 Changed 9 years ago by
Commit:  b6ed0387bb16a0102cc2792494d120df7b0fe292 → ee8c39521a203a53876e435e271e59c38a4ca429 

Status:  needs_work → 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 9 years ago by
Status:  needs_review → needs_work 

Please resolve the conflict with your new commit in #15622.
comment:8 Changed 9 years ago by
Branch:  u/SimonKing/ticket/15623 → public/15623 

Commit:  ee8c39521a203a53876e435e271e59c38a4ca429 
Status:  needs_work → needs_review 
Done !
Nathann
comment:9 Changed 9 years ago by
Commit:  → 95cecd153d53a0666a3f1814831efc5cb15cb516 

Branch pushed to git repo; I updated commit sha1. New commits:
0f57805  trac #15622: Immutable graphs must not be relabeled

b6ed038  trac #15623: Immutable graph backend for Posets

ee8c395  Trac 15623: Let to_graph return an immutable graph

dcb8a0b  trac #15623: rebase on 6.1.beta4

529f785  trac #15622: More informative exception message

2245c02  Trac 15622: Review commit, fixing a misspelled doctest

60ad575  trac #15622: Rebase on 6.1.beta3

6398780  trac #15622: bugfix before #15623 gets merged

3531566  trac #15623: Rebase on updated #15622

95cecd1  trac #15623: Removing the hack from #15622, update a variable's name

comment:10 Changed 9 years ago by
I don't know how THIS could be read without the ticket numbers :P
comment:11 Changed 9 years ago by
Reviewers:  → Simon King 

Status:  needs_review → positive_review 
The merge was successful (looking at the code), and all tests pass.
comment:12 Changed 9 years ago by
Wow. Done :P
Thaaaaaaaaaaank you very much Travis for all these reviews !
Nathann
comment:13 Changed 9 years ago by
Arggggggg !! Simon !! Simon !! :P
It's because of these comments on the Tutte thread :P
Nathann
comment:14 Changed 9 years ago by
Work issues:  doctest error related with hash of mutable graphs 

comment:15 Changed 9 years ago by
Status:  positive_review → needs_work 

This doesn't merge with the latest develop
branch I'm afraid.
comment:16 Changed 9 years ago by
Branch:  public/15623 → u/SimonKing/ticket/15623 

Modified:  Jan 27, 2014, 7:20:18 AM → Jan 27, 2014, 7:20:18 AM 
comment:17 Changed 9 years ago by
Commit:  95cecd153d53a0666a3f1814831efc5cb15cb516 → dae53af8e9fbc5b8cbf7da3de2eae92e2e9c0d56 

Status:  needs_work → 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:
dae53af  Merge branch 'develop' into ticket/15623

comment:18 Changed 9 years ago by
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/sitepackages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/king/Sage/git/sage/local/lib/python2.7/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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 9 years ago by
There are more errors concerning the missing attribute 'vertex_ints'.
Nathann, do you have an idea what went wrong?
comment:20 Changed 9 years ago by
Status:  needs_review → needs_work 

comment:21 Changed 9 years ago by
Commit:  dae53af8e9fbc5b8cbf7da3de2eae92e2e9c0d56 → c5b6d591982ef3e8d5902ecd9f7bfbd05cbb85a4 

Branch pushed to git repo; I updated commit sha1. New commits:
c5b6d59  Reinsert a bit of code that had been erroneously deleted in the previous merge commit

comment:22 Changed 9 years ago by
Status:  needs_work → needs_review 

Ahaaaa! It seems that I did wrong when merging! Namely, I have removed the vertex_ints attribute.
In a second commit, I reintroduced 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 9 years ago by
Status:  needs_review → 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 9 years ago by
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 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:26 Changed 9 years ago by
Resolution:  → fixed 

Status:  positive_review → closed 
Last 10 new commits:
trac #15623: Immutable graph backend for Posets
trac #15622: Immutable graphs must not be relabeled
trac #15619: bug in the former definition; exception to avoid it in the future
trac #15619: Pickling of immutable graphs
trac #15603: "immutable=True" for Graph/Digraph __init__ and copy()
Trac 15278: Fix syntax error in doc test
Trac 15278: Only graphs that use the static backend are identical with their copy
Merge branch 'develop' into ticket/15278
Trac 15278: Error messages explain how to create (im)mutable graph copy
Make digraphs using the static backend immutable and hashable