equality is broken for Posets

[nathanncohen]

Plain and simple :

sage: d = DiGraph({2:[1],3:[1]})   
sage: p1 = Poset(d)
sage: p2 = p1.relabel({1:1,2:3,3:2})
sage: p1.hasse_diagram() == p2.hasse_diagram()
True
sage: p1 == p2
False

This can be fixed by saying that two posets are equal if their hasse diagrams are equal, as it should have been since the beginning.

This will probably make poset equality much slower. On the bright side it will work correctly.

Of course this patch could have been almost trivial, but there is in the FinitePoset class a "key" argument, whose purpose is to make two posets different if they have different keys. So this patch checks that too.

And the next time that somebody will need to store pairs "(a poset, a key)", the best will be to store pairs "(a poset, a key)". And not "A poset with a key included inside, which is useful just for my own code" as one could easily believe.

Oh. And the same with linear orderings, of course.

Nathann

Depends on #17059
Depends on #16933

CC: @hivert @nthiery @sagetrac-nborie @VivianePons @fchapoton @anneschilling @stumpc5 @jm58660

Component: combinatorics

Keywords: posets

Stopgaps: #14185

Author: Travis Scrimshaw, Anne Schilling

Branch: 23de9f5

Reviewer: Travis Scrimshaw, Anne Schilling, John Palmieri, Nathann Cohen, Nicolas M. Thiéry

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

[nathanncohen]

comment:2

Oh, yeah. And this patch also fixes this :

def hasse_diagram(self, wrapped = True):
    return DiGraph(self._hasse_diagram).relabel(self._list, inplace = False)

Combinat-Style.

Nathann

[nathanncohen]

comment:3

fixed by removing the useless keyword (it is useless, as it cannot be used and hence has never been). Casting the HasseDiagram to a digraph first is useless copy, as relabeling with inplace = False already makes a copy.

And also because for some reason, up to now, a call to .hasse_diagram() returned a DiGraph and not a HasseDiagram object.

Nathann

[nathanncohen]

comment:4

Yeahhhhhhhhhhhhh.....

def __eq__(self, other):
     return self.hasse_diagram() == other.hasse_diagram()

Result :

      ...
      File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 826, in __eq__
        return ((self.hasse_diagram() == other.hasse_diagram()) and
      File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 432, in __eq__
        if self.vertices() != other.vertices():
      File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/combinat/posets/elements.py", line 116, in __eq__
        return have_same_parent(self, other) \
      File "sage_object.pyx", line 700, in sage.structure.sage_object.have_same_parent (sage/structure/sage_object.c:8386)
      File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 826, in __eq__
        return ((self.hasse_diagram() == other.hasse_diagram()) and
      ...
      RuntimeError: maximum recursion depth exceeded

Categories strike again.

Nathann

[nathanncohen]

comment:5

return ((DiGraph.__eq__(self.hasse_diagram(), other.hasse_diagram()))

Same result.

[nathanncohen]

comment:6

Ok guys, you did it, I have no way to write a new __eq__ method in Poset which is not "self is other" without getting an infinite loop.

If I want to actually compare the data of the posets (hasse diagram, vertices), then comparing the data will raise a call to compare their parents, and I'm gone for another loop.

Now what ?

Nathann

[anneschilling]

comment:7

Attachment: trac_14019.patch.gz

We discussed this at the Sage Days last week (unfortunately you were not there). The best way might be to have an option in Posets which would allow to create posets with and without an attached linear extension. Your use case would be in the new default case of no linear extension attached.

Best,

Anne

[nathanncohen]

comment:9

We discussed this at the Sage Days last week (unfortunately you were not there).

I'm pretty sure that I was, but I admittedly have a very poor memory.

The best way might be to have an option in Posets which would allow to create posets with and without an attached linear extension.

And the one without fancy stuff would be the default Poset.

Your use case would be in the new default case of no linear extension attached.

My use case is the definition of what a Poset is. In any book. Also, do we overlook the fact that this is a conceptual problem of categories, and equalities, an parents, and all that stuff ?

Nathann

[nathanncohen]

comment:11

Quotes from posets.py

            # We need to relabel the digraph since range(self._n) must be a linear                                                                                                             
            # extension. Too bad we need to compute this again. TODO: Fix this.  

Nathann

[nthiery]

comment:12

Hi Nathann,

Replying to @nathanncohen:

We discussed this at the Sage Days last week (unfortunately you were not there).

I'm pretty sure that I was, but I admittedly have a very poor memory.

The discussion continued later.

Your use case would be in the new default case of no linear extension attached.

My use case is the definition of what a Poset is. In any book.

Obviously. We all agree that this is the rationale for the new default
value.

Also, do we overlook the fact that this is a conceptual problem of
categories, and equalities, an parents, and all that stuff ?

This has nothing to do with categories. This is a consequence of the
choice of having unique representation for posets. The constructor
should do the right thing and then equality be simply tested by "is".

Now if you would not mind stopping spreading FUD on unrelated things
for no reason except that you happen to not need them yourself, «ça
nous ferait des vacances».

Cheers,
Nicolas

[nathanncohen]

comment:13

Obviously. We all agree that this is the rationale for the new default
value.

Just to make sure everybody accepts that code will be broken.

This has nothing to do with categories. This is a consequence of the
choice of having unique representation for posets. The constructor
should do the right thing and then equality be simply tested by "is".

Nice. Now, if I have a class that I define myself which contains elements which belong to the category framework : does it mean that this class has to be UniqueRepresentation ? That seems to be the source of my problem above.

Now if you would not mind stopping spreading FUD on unrelated things
for no reason except that you happen to not need them yourself, «ça
nous ferait des vacances».

Fix the bugs you introduce and we have a deal. How do I break out of this infinite loop ?

Nathann

[nthiery]

comment:14

Replying to @nathanncohen:

Obviously. We all agree that this is the rationale for the new default
value.

Just to make sure everybody accepts that code will be broken.

Please reread. The new default is what we both agree on and is correct.

Nice. Now, if I have a class that I define myself which contains elements which belong to the category framework : does it mean that this class has to be UniqueRepresentation ?

No. Some parents don't have unique representation.

Fix the bugs you introduce and we have a deal.

I did not introduce this bug. And anyway it's Chet's fault.

How do I break out of this infinite loop ?

I know it's frustrating when one can't have an influence to improve the world. But in the case at hand the only step you can take is to stop wasting our time repeating the same things over and over.

[nathanncohen]

comment:15

Helloooooooooooooo !!!

Okayyyyyyyyyy, I just had a nice evening with Florent which had begun with a conversation about this patch, and he said that he'd have a patch for this one month from now.

This being said, I still have no answer for a problem with categories : you say that some parents do not have a unique representation, but here is the reason behind the infinite loop I got today :

1. My Poset parent implements __eq__ by first comparing the hasse diagrams, which leads to check that the elements of the digraph are equal.

2. In order to know whether the elements are equal, the category mechanism makes them check that they have the same parents

3. I check that the parents are equal again, and loop ...

That's why I asked whether Parents need to be UniqueRepresentation. Because if they aren't, they sure cannot compare their elements !

Nathann

[vbraun]

comment:16

Generally, == should mean identical and not just isomorphic. Up to automorphism there is only one set of a given size. But surely we don't want all sets of fixed size to compare equal, right?

Any two objects that satisfy == may be substituted for each other in cached method calls.

If you want "isomorphic with possibly non-unique isomorphism" then just implement a is_isomorphic() method.

[nathanncohen]

comment:17

There's nothing related to isomorphism in what I said. The same way that you expect that int(1) == Integer(1) is True, I would like that two posets that represent the very same partially ordered set be equal. This is totally linear, and consists in checking that i<j in one poset if and only if i<j in the other one. That's not an isomorphism, there is no relabeling involved.

This being said, I would like to have an answer to my question above. Not being able to define an __eq__ function as you see fit because of the parent stuff looks to me like a problem.

Nathann

[nathanncohen]

comment:18

But surely we don't want all sets of fixed size to compare equal, right?

And surely we don't want all Sage objects to be UniqueRepresentation.

Nathann

[nathanncohen]

comment:19

(Answer from Nicolas Thiery, because trac is in a bad mood)

Replying to @nathanncohen:

Okayyyyyyyyyy, I just had a nice evening with Florent which had begun with a conversation about this patch, and he said that he'd have a patch for this one month from now.

Excellent :-)

This being said, I still have no answer for a problem with categories : you say that some parents do not have a unique representation, but here is the reason behind the infinite loop I got today :

1. My Poset parent implements __eq__ by first comparing the hasse diagrams, which leads to check that the elements of the digraph are equal.
2. In order to know whether the elements are equal, the category mechanism makes them check that they have the same parents
3. I check that the parents are equal again, and loop ...

That's why I asked whether Parents need to be UniqueRepresentation. Because if they aren't, they sure cannot compare their elements !

Ok, I get your point now.

That's a situation we never met before; parents not often compare
themselves by comparing (some of) their elements. When this is the
case, this probably means that those elements were part of the
definition of the parent, and thus constructed from some data that
preexisted the parent.

To break the loop, one could thus compare that data. In the case at
hand, that would amount to compare the digraph that was use as input
to the Poset constructor.

Even if this occurred from time to time, I guess I would not see this
as a recurrent problem of elements/parent, but of data structures with
loops in general.

Cheers,
Nicolas

[vbraun]

comment:20

What is the expected output of the following:

sage: d = DiGraph({2:[1],3:[1]})   
sage: p1 = Poset(d)
sage: p2 = p1.relabel({1:1,2:3,3:2})
sage: p1[0] 
3
sage: p2[0]
2
sage: @cached_function
....: def first_element(poset): 
....:     return poset[0]
....: 
sage: first_element(p1)
3
sage: first_element(p2)
???

[lftabera]

Stopgaps: #14185

[AndrewMathas]

Branch: u/andrew.mathas/ticket/14019

[AndrewMathas]

comment:24

Hi Nathann,

I moved your patch over to git and I found a hack which stops the infinite loop: it turns out that posets have an attribute _hasse_diagram and checking this seems to be better for some (unknown) reason. A few of the doctests still fail:

sage -t posets.py
**********************************************************************
File "posets.py", line 456, in sage.combinat.posets.posets.Poset
Failed example:
    P1 == P2
Expected:
    False
Got:
    True
**********************************************************************
File "posets.py", line 838, in sage.combinat.posets.posets.FinitePoset.__eq__
Failed example:
    p3 == p1
Expected:
    False
Got:
    True
**********************************************************************
File "posets.py", line 842, in sage.combinat.posets.posets.FinitePoset.__eq__
Failed example:
    p3 == p5
Expected:
    False
Got:
    True
**********************************************************************
File "posets.py", line 1133, in sage.combinat.posets.posets.FinitePoset.hasse_diagram
Failed example:
    Q.hasse_diagram()
Expected:
    Hasse diagram of a poset containing 6 elements
Got:
    Digraph on 6 vertices
**********************************************************************

I guess that the failing equality tests are bad, but I am happy that the infinite loop is gone.

Florent, Nicolas: it would be good if you could take some time to look at this too as this has been sitting around unloved for quite awhile.

Andrew

---

New commits:

[a1a85ff](https://github.com/sagemath/sagetrac-mirror/commit/a1a85ff)	Importing Nathann's patch
[8c2aeff](https://github.com/sagemath/sagetrac-mirror/commit/8c2aeff)	trac #15479: Finite Words should be proud of their finiteness

[sagetrac-git]

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

46f4fdc	remove deprecated code
ea330d3	revert remove of iterator() and list()
2e4f269	Merge remote-tracking branch 'origin/develop' into depr_func
cf77bc2	deprecate compact argument
c79991e	Merge branch 'u/aapitzsch/ticket/16933' of trac.sagemath.org:sage into public/combinat/poset/fix_equality-14019
1c0d02d	Merge branch 'public/combinat/poset/fix_equality-14019' of trac.sagemath.org:sage into public/combinat/poset/fix_equality-14019

[sagetrac-git]

Changed commit from 3afec89 to 1c0d02d

[tscrim]

comment:102

I've handled the conflict from #16933, so we're back to positive review.

[tscrim]

Changed dependencies from #17059 to #17059 #16933

[anneschilling]

Changed author from Travis Scrimshaw, Anne Schilling to Nathann Cohen, John Palmieri, Travis Scrimshaw, Anne Schilling

[vbraun]

comment:104

Breaks docbuild after #16933 is applied.

[vbraun]

Changed dependencies from #17059 #16933 to #17059, #16933, #16933

[sagetrac-git]

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

23de9f5

Fixing documentation and references.

[sagetrac-git]

Changed commit from 1c0d02d to 23de9f5

[tscrim]

comment:106

Fixed. What had happened is we removed a reference (because it was a duplicate), but without deleting the doc first, there was still a reference for sphinx, which is why we didn't catch it before when we checked that the doc builds.

[tscrim]

Changed reviewer from Travis Scrimshaw, Anne Schilling to Travis Scrimshaw, Anne Schilling, John Palmieri

[tscrim]

Changed author from Nathann Cohen, John Palmieri, Travis Scrimshaw, Anne Schilling to Nathann Cohen, Travis Scrimshaw, Anne Schilling

[tscrim]

Changed dependencies from #17059, #16933, #16933 to #17059, #16933

[anneschilling]

Changed author from Nathann Cohen, Travis Scrimshaw, Anne Schilling to Travis Scrimshaw, Anne Schilling

[anneschilling]

Changed reviewer from Travis Scrimshaw, Anne Schilling, John Palmieri to Travis Scrimshaw, Anne Schilling, John Palmieri, Nathann Cohen

[vbraun]

Changed branch from public/combinat/poset/fix_equality-14019 to 23de9f5

[nthiery]

Changed commit from 23de9f5 to none

[nthiery]

Changed reviewer from Travis Scrimshaw, Anne Schilling, John Palmieri, Nathann Cohen to Travis Scrimshaw, Anne Schilling, John Palmieri, Nathann Cohen, Nicolas M. Thiéry

[nthiery]

comment:109

Thanks Anne for finalizing!