Immutable graph backend for Posets #15623

nathanncohen · 2014-01-02T21:36:09Z

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

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

Nathann

Depends on #15622

CC: @simon-king-jena

Component: combinatorics

Author: Nathann Cohen

Branch/Commit: u/SimonKing/ticket/15623 @ c5b6d59

Reviewer: Simon King

Issue created by migration from https://trac.sagemath.org/ticket/15623

The text was updated successfully, but these errors were encountered:

nathanncohen · 2014-01-03T11:16:20Z

Commit: b6ed038

nathanncohen · 2014-01-03T11:16:20Z

Branch: u/ncohen/15623

nathanncohen · 2014-01-03T11:16:20Z

Last 10 new commits:

`b6ed038`	`trac #15623: Immutable graph backend for Posets`
`0f57805`	`trac #15622: Immutable graphs must not be relabeled`
`c441178`	`trac #15619: bug in the former definition; exception to avoid it in the future`
`0229348`	`trac #15619: Pickling of immutable graphs`
`7860f39`	trac #15603: "immutable=True" for Graph/Digraph `__init__` and copy()
`2525d22`	`Trac 15278: Fix syntax error in doc test`
`fcf9e30`	`Trac 15278: Only graphs that use the static backend are identical with their copy`
`8fc9c94`	`Merge branch 'develop' into ticket/15278`
`51d6328`	`Trac 15278: Error messages explain how to create (im)mutable graph copy`
`2fc8a77`	`Make digraphs using the static backend immutable and hashable`

simon-king-jena · 2014-01-03T23:22:33Z

Work Issues: doctest error related with hash of mutable graphs

simon-king-jena · 2014-01-03T23:22:33Z

comment:3

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.

simon-king-jena · 2014-01-03T23:25:19Z

comment:4

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.

simon-king-jena · 2014-01-04T00:00:37Z

Changed branch from u/ncohen/15623 to u/SimonKing/ticket/15623

simon-king-jena · 2014-01-04T00:03:31Z

comment:6

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.

simon-king-jena · 2014-01-04T00:03:31Z

Changed commit from b6ed038 to ee8c395

simon-king-jena · 2014-01-06T15:59:01Z

comment:7

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

nathanncohen · 2014-01-07T08:10:38Z

comment:8

Done !

Nathann

nathanncohen · 2014-01-07T08:10:38Z

Changed commit from ee8c395 to none

nathanncohen · 2014-01-07T08:10:38Z

Changed branch from u/SimonKing/ticket/15623 to public/15623

sagetrac-git · 2014-01-07T08:10:55Z

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`

sagetrac-git · 2014-01-07T08:10:55Z

Commit: 95cecd1

nathanncohen · 2014-01-07T08:11:47Z

comment:10

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

simon-king-jena · 2014-01-07T22:49:00Z

comment:11

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

nathanncohen · 2014-01-12T16:35:55Z

Changed work issues from doctest error related with hash of mutable graphs to none

tscrim · 2014-01-27T07:20:18Z

comment:15

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

simon-king-jena · 2014-01-27T10:50:14Z

Changed branch from public/15623 to u/SimonKing/ticket/15623

simon-king-jena · 2014-01-27T10:52:10Z

comment:17

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`

simon-king-jena · 2014-01-27T10:52:10Z

Changed commit from 95cecd1 to dae53af

simon-king-jena · 2014-01-27T11:17:20Z

comment:18

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]

simon-king-jena · 2014-01-27T11:34:29Z

comment:19

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

Nathann, do you have an idea what went wrong?

sagetrac-git · 2014-01-27T11:53:20Z

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

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

sagetrac-git · 2014-01-27T11:53:20Z

Changed commit from dae53af to c5b6d59

simon-king-jena · 2014-01-27T11:56:53Z

comment:22

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!

simon-king-jena · 2014-01-27T13:18:12Z

comment:23

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

nathanncohen · 2014-01-28T14:02:37Z

comment:24

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

nathanncohen mannequin added this to the sage-6.1 milestone Jan 2, 2014

nathanncohen mannequin added c: combinatorics labels Jan 2, 2014

simon-king-jena added s: needs work and removed s: needs review labels Jan 3, 2014

simon-king-jena added s: needs review and removed s: needs work labels Jan 4, 2014

simon-king-jena added s: needs work and removed s: needs review labels Jan 6, 2014

nathanncohen mannequin added s: needs review and removed s: needs work labels Jan 7, 2014

tscrim added s: needs work and removed s: positive review labels Jan 27, 2014

simon-king-jena added s: needs review and removed s: needs work labels Jan 27, 2014

simon-king-jena added s: needs work and removed s: needs review labels Jan 27, 2014

simon-king-jena added s: needs review and removed s: needs work labels Jan 27, 2014

simon-king-jena added s: positive review and removed s: needs review labels Jan 27, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

vbraun removed the s: positive review label Feb 1, 2014

vbraun closed this as completed in 12b415d Feb 1, 2014

sagetrac-JStarx mannequin mentioned this issue Jan 14, 2023

Add representations of quivers and quiver algebras to sage #12630

Closed

This was referenced Sep 6, 2015

(disjoint) Union of graphs with multiple edges #15627

Closed

Name of immutable graphs #15681

Closed

simon-king-jena mentioned this issue Feb 14, 2014

Immutable directed graphs should know that they are directed #15810

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Immutable graph backend for Posets #15623

Immutable graph backend for Posets #15623

nathanncohen mannequin commented Jan 2, 2014

nathanncohen mannequin commented Jan 3, 2014

nathanncohen mannequin commented Jan 3, 2014

nathanncohen mannequin commented Jan 3, 2014

simon-king-jena commented Jan 3, 2014

simon-king-jena commented Jan 3, 2014

simon-king-jena commented Jan 3, 2014

simon-king-jena commented Jan 4, 2014

simon-king-jena commented Jan 4, 2014

simon-king-jena commented Jan 4, 2014

simon-king-jena commented Jan 6, 2014

nathanncohen mannequin commented Jan 7, 2014

nathanncohen mannequin commented Jan 7, 2014

nathanncohen mannequin commented Jan 7, 2014

sagetrac-git mannequin commented Jan 7, 2014

sagetrac-git mannequin commented Jan 7, 2014

nathanncohen mannequin commented Jan 7, 2014

simon-king-jena commented Jan 7, 2014

nathanncohen mannequin commented Jan 12, 2014

tscrim commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

sagetrac-git mannequin commented Jan 27, 2014

sagetrac-git mannequin commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

nathanncohen mannequin commented Jan 28, 2014

Immutable graph backend for Posets #15623

Immutable graph backend for Posets #15623

Comments

nathanncohen mannequin commented Jan 2, 2014

nathanncohen mannequin commented Jan 3, 2014

nathanncohen mannequin commented Jan 3, 2014

nathanncohen mannequin commented Jan 3, 2014

simon-king-jena commented Jan 3, 2014

simon-king-jena commented Jan 3, 2014

simon-king-jena commented Jan 3, 2014

simon-king-jena commented Jan 4, 2014

simon-king-jena commented Jan 4, 2014

simon-king-jena commented Jan 4, 2014

simon-king-jena commented Jan 6, 2014

nathanncohen mannequin commented Jan 7, 2014

nathanncohen mannequin commented Jan 7, 2014

nathanncohen mannequin commented Jan 7, 2014

sagetrac-git mannequin commented Jan 7, 2014

sagetrac-git mannequin commented Jan 7, 2014

nathanncohen mannequin commented Jan 7, 2014

simon-king-jena commented Jan 7, 2014

nathanncohen mannequin commented Jan 12, 2014

tscrim commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

sagetrac-git mannequin commented Jan 27, 2014

sagetrac-git mannequin commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

simon-king-jena commented Jan 27, 2014

nathanncohen mannequin commented Jan 28, 2014