Opened 8 years ago

Closed 6 years ago

Last modified 6 years ago

#14019 closed defect (fixed)

equality is broken for Posets

Reported by: ncohen Owned by: sage-combinat
Priority: major Milestone: sage-6.4
Component: combinatorics Keywords: posets
Cc: hivert, nthiery, nborie, VivianePons, chapoton, aschilling, stumpc5, jmantysalo Merged in:
Authors: Travis Scrimshaw, Anne Schilling Reviewers: Travis Scrimshaw, Anne Schilling, John Palmieri, Nathann Cohen, Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: 23de9f5 (Commits) Commit:
Dependencies: #17059, #16933 Stopgaps: #14185

Description (last modified by ncohen)

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

Attachments (1)

trac_14019.patch (3.6 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (110)

comment:1 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 8 years ago by ncohen

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

comment:3 Changed 8 years ago by ncohen

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

comment:4 Changed 8 years ago by ncohen

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

comment:5 Changed 8 years ago by ncohen

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

Same result.

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

  • Cc chapoton aschilling added
  • Status changed from new to needs_info

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

Changed 8 years ago by ncohen

comment:7 in reply to: ↑ 6 ; follow-up: Changed 8 years ago by aschilling

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

comment:8 Changed 8 years ago by aschilling

  • Cc stumpc5 added

comment:9 in reply to: ↑ 7 ; follow-up: Changed 8 years ago by ncohen

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

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

comment:10 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:11 Changed 8 years ago by ncohen

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

comment:12 in reply to: ↑ 9 ; follow-up: Changed 8 years ago by nthiery

Hi Nathann,

Replying to ncohen:

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

comment:13 in reply to: ↑ 12 ; follow-up: Changed 8 years ago by ncohen

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

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

comment:14 in reply to: ↑ 13 Changed 8 years ago by nthiery

Replying to ncohen:

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.

comment:15 Changed 8 years ago by ncohen

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

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

comment:16 follow-up: Changed 8 years ago by vbraun

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.

comment:17 Changed 8 years ago by ncohen

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

comment:18 in reply to: ↑ 16 Changed 8 years ago by ncohen

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

comment:19 Changed 8 years ago by ncohen

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

Replying to ncohen:

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

comment:20 Changed 8 years ago by vbraun

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)
???

comment:21 Changed 8 years ago by lftabera

  • Stopgaps set to #14185

comment:22 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:23 Changed 7 years ago by andrew.mathas

  • Branch set to u/andrew.mathas/ticket/14019
  • Created changed from 01/26/13 15:28:37 to 01/26/13 15:28:37
  • Modified changed from 08/13/13 15:35:53 to 08/13/13 15:35:53

comment:24 Changed 7 years ago by andrew.mathas

  • Commit set to a1a85ff09dcc34a56b9362a9d4461d907296718e

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:

a1a85ffImporting Nathann's patch
8c2aefftrac #15479: Finite Words should be proud of their finiteness
Last edited 7 years ago by andrew.mathas (previous) (diff)

comment:25 Changed 7 years ago by andrew.mathas

Hmm, not sure why the commit for #15479 is also on this ticket. Probably I screwed up and didn't branch off the master:(

comment:26 Changed 7 years ago by ncohen

Hmmmmmm... Must be because my original patch fixed several things, and two of these fixes are not compatible with each other : I also made .hasse_diagram() return a HasseDiagram object. In the patch you imported with git, this modification is not made anymore. So you compare DiGraph objects, and not HasseDiagram objects. Perhaps it still works if you compare the results of .hasse_diagram() instead of ._hasse_diagram directly.

Arggggggg ! No, I think I understood ! I think that it is incorrect to compare the ._hasse_diagram digraphs, because they are always labelled with integers, so when you do that you do not compare the vertice' labels :

sage: list(posets.IntegerCompositions(3)) 
[[3], [1, 2], [2, 1], [1, 1, 1]]
sage: list(posets.IntegerCompositions(3).hasse_diagram())
[[3], [1, 2], [1, 1, 1], [2, 1]]
sage: list(posets.IntegerCompositions(3)._hasse_diagram) 
[0, 1, 2, 3]

And of course as you compare digraphs defined on integers there is no problem, for they don't have parents. But it may say that two posets are equal even if they are defined on disjoint sets of elements.

Nathann

comment:27 Changed 7 years ago by git

  • Commit changed from a1a85ff09dcc34a56b9362a9d4461d907296718e to d10a6efa75561632cdc76b2c98c5eca4312372ec

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

d10a6efImporting Nathann's patch

comment:28 Changed 7 years ago by andrew.mathas

I have just undone my mistaken branching off #15479

comment:29 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:30 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:31 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:32 Changed 6 years ago by ncohen

  • Cc jmantysalo added

Hello,

20 months ago, I thought that this problem would be fixed in a month. Yesterday Jori created ticket #17051 which is a bug report, apparently linked with what this ticket was meant to address.

Today is saturday. Unless somebody has a different way to solve the problem and is meaning to solve it during the week, I will create a ticket here that makes .relabel() return a Poset.

You cannot defend that Posets are both UniqueRepresentation and mutable. So .relabel() cannot change self. There will be no deprecation, for it is a bugfix.

Nathann

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

comment:33 follow-up: Changed 6 years ago by tscrim

relabel() does return a new poset. The issue is a little more subtle in regards to the ordering on the set of elements of the poset:

sage: list(p1)
[3, 2, 1]
sage: list(p2)
[2, 3, 1]

because

sage: p1._elements
(3, 2, 1)
sage: p2._elements
(2, 3, 1)

That is why they don't compare as equal (as it is part of the construction data). The simplist change (FTR, I don't consider this to be a bug, but instead a lack of documentation) would be to make the Hasse diagram the only part of the construction info, however this would mean we'd have to relabel the Hasse diagram at construction time rather than when calling hasse_diagram(). This also has the drawback of not being able to use the same digraph for all relabelings of a poset, which is probably used by the linear extensions and creates a much larger memory usage (and data duplication).

Hopefully before you have gotten angry, I think better standardization could be used here too.

I'm also not quite sure #17051 is because of this behavior, but I haven't really looked into it.

comment:34 in reply to: ↑ 33 ; follow-ups: Changed 6 years ago by ncohen

Yo !

relabel() does return a new poset.

Oh, True, True, I had forgotten what exactly the problem was. Two years ago, after all :-D

Cool, then the interface will not even change.

The simplist change would be to make the Hasse diagram the only part of the construction info, however this would mean we'd have to relabel the Hasse diagram at construction time rather than when calling hasse_diagram().

Indeed.I will do just that.

This also has the drawback of not being able to use the same digraph for all relabelings of a poset, which is probably used by the linear extensions and creates a much larger memory usage (and data duplication).

Hopefully before you have gotten angry, I think better standardization could be used here too.

I was angry two years ago, because I was told that the problem would be fixed, and it was not. Jori had been doing a lot of work to fix/improve the poset class in the last two days, and I just don't want to tell him that this bug will stay because nobody is willing to make a move.

I will write the branch that rewrites .relabel properly, and that will be all.

Nathann

comment:35 in reply to: ↑ 34 Changed 6 years ago by ncohen

Hopefully before you have gotten angry, I think better standardization could be used here too.

Can you implement your idea this week ? If you can't I will implement the simple idea I understand (just give the relabelled Hasse Diagram) to fix the bug. If you can, tell me and so that I do not implement this for nothing.

Thanks,

Nathann

comment:36 in reply to: ↑ 34 Changed 6 years ago by jmantysalo

Replying to ncohen:

Jori had been doing a lot of work to fix/improve the poset class in the last two days, and I just don't want to tell him that this bug will stay because nobody is willing to make a move.

This is not a blocker issue for me. I was just making some test set, but I can do it by other ways.

comment:37 Changed 6 years ago by ncohen

Okay, I am wasting my week-end on this bug that had been left to rot for 20 months again, and here is where I am:

In the __init__ of FinitePoset you have a hasse diagram on 0,...,n-1 and a list of labels for the n points. Those are used as the key for the equality inherited from UniqueRepresentation.

Of course, if you apply a graph isomorphism to the list of labels it still represents the very same poset. But the key is different, so equality answers 'no'.

Guys this bug is hard to fix because there is a LOT of code that uses these functions, and there are two layers of pre-treatment (Poset and FinitePoset.__classcall__). I would appreciate it if somebody felt responsible of that and fixed it.

Nathann

P.S.: I created #17059 that fixes some other stupid bug.

comment:39 in reply to: ↑ 38 Changed 6 years ago by aschilling

Hi Nathann,

To be honest, I cannot even reproduce the bug that you reported

sage: d = DiGraph({2:[1],3:[1]})   
sage: sage: p1 = Poset(d)
sage: sage: p2 = p1.relabel({1:1,2:3,3:2})
/Applications/sage/src/bin/sage-ipython:1:
********************************************************************************
Relabelling posets is known to break equality between posets (P == Q)
This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/14019.
********************************************************************************
sage: sage: p1.hasse_diagram() == p2.hasse_diagram()
True
sage: p1 == p2
True 

Is it possible that this was already fixed with #17059? I am running sage-6.4.beta4.

Anne

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

No Anne, I am not complaining about a bug that I fixed myself last week.

I found #17059 while working on it, and #17059 is only about a bad 'category' argument.

In particular, I can still reproduce it on my computer.

This being said, the code has absolutely no reason to be machine-dependent in its current state. Can you check this again and give us the output of p1._list and p2._list ? The relabel function, which you wrote yourself in #12536, makes sure that the ._list flag is modified, which breaks equality. This is not machine-dependent, so I do not understand why it may work on your computer.

Nathann

comment:41 in reply to: ↑ 40 Changed 6 years ago by aschilling

  • Authors changed from Nathann Cohen to Travis Scrimshaw, Anne Schilling
  • Branch changed from u/andrew.mathas/ticket/14019 to public/combinat/poset/fix_equality-14019
  • Commit changed from d10a6efa75561632cdc76b2c98c5eca4312372ec to b1eefd78cd65736b44153761b929de1c4387cb70
  • Keywords posets added
  • Reviewers set to Travis Scrimshaw, Anne Schilling
  • Status changed from needs_info to needs_review

The current branch fixes the bug. The rationale is to allow posets to not have a specified linear extension. This is achieved by changing the input behavior of FinitePoset. If elements is specified, this is used for the underlying linear extension. If elements is None, then the default linear extension is now computed in the __init__, so that posets where linear extensions are not specified now compare equal.

Travis and Anne


Last 10 new commits:

691807bFixed issues with relabeling and elements. Fixed some doctests.
d5c570cSome more fixes.
a1eca30reinstated linear_extension
95f735bgetting the interface right!
01dc92dneeded one more relabelling for correct linear extensions
f1511c0Fixing bugs in relabeling by not doing it automatically in __classcall__.
6f86a9afixed some docs
c7e7107Fixed last issues. All doctests pass.
ed7f091more doc test fixes
b1eefd7Some more documentation as reference.

comment:42 Changed 6 years ago by tscrim

  • Dependencies set to #17059
  • Status changed from needs_review to positive_review

FTR, we also did some minor cleanup of the file.

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

Positive review ? On my computer this code breaks a *LOT* of doctests in the combinat folder.

Nathann

comment:44 Changed 6 years ago by ncohen

Also, I do not understand what you do in the .dual() function. You seem to define a elements variable that you do not use. As a result the dual of a Poset with a linear extension becomes a poset without linear extension.

Would it also be possible to change the __repr__ function so that is says explicitly that the poset is a poset with a linear extension ? The two posets behave as if they were of different type (they can never be equal), and if such a poset is returned by a function it may surprise the user that the poset is never equal to a poset he built himself.

Nathann

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

  • Status changed from positive_review to needs_work

Merge conflict, too

comment:46 Changed 6 years ago by ncohen

Merge conflict ? Oh, yes probably with all the Poset tickets Jori wrote. Their code is based on the latest beta though.

Nathann

comment:47 follow-up: Changed 6 years ago by jhpalmieri

I can't even get to the point of running doctests: if I run make, then docbuilding fails with

[modmisc  ] loading pickled environment... not yet created
[modmisc  ] building [inventory]: targets for 16 source files that are out of date
[modmisc  ] updating environment: 16 added, 0 changed, 0 removed
[modmisc  ] reading sources... [  6%] index
[modmisc  ] reading sources... [ 12%] sage/modular/buzzard
Error building the documentation.

Note: incremental documentation builds sometimes cause spurious
error messages. To be certain that these are real errors, run
"make doc-clean" first and try again.
Traceback (most recent call last):
  File "/Users/palmieri/Desktop/Sage_stuff/git/sage/src/doc/common/builder.py", line 1491, in <module>
    getattr(get_builder(name), type)()
  File "/Users/palmieri/Desktop/Sage_stuff/git/sage/src/doc/common/builder.py", line 292, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/Users/palmieri/Desktop/Sage_stuff/git/sage/src/doc/common/builder.py", line 503, in _wrapper
    x.get(99999)
  File "/Users/palmieri/Desktop/Sage_stuff/git/sage/local/lib/python/multiprocessing/pool.py", line 558, in get
    raise self._value
NotImplementedError: Non injective relabeling
make: *** [doc-html] Error 1

comment:48 Changed 6 years ago by git

  • Commit changed from b1eefd78cd65736b44153761b929de1c4387cb70 to e575742951572b4b383abeae1e21e934b9e1683f

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

e575742fixed failing doc tests

comment:49 in reply to: ↑ 43 Changed 6 years ago by aschilling

Replying to ncohen:

Positive review ? On my computer this code breaks a *LOT* of doctests in the combinat folder.

They were all trivial failures and are fixed now!

Also, I do not understand what you do in the .dual() function. You seem to define a >elements variable that you do not use. As a result the dual of a Poset with a linear >extension becomes a poset without linear extension.

Fixed.

Would it also be possible to change the repr function so that is says explicitly that the poset is a poset with a linear extension ? The two posets behave as if they were of different type (they can never be equal), and if such a poset is returned by a function it may surprise the user that the poset is never equal to a poset he built himself.

If this is only for HIM, I am sure this is now in your ability range to fix it, if it is important to you!

Anne

comment:50 in reply to: ↑ 45 Changed 6 years ago by tscrim

Replying to vbraun:

Merge conflict, too

What tickets does it conflict with?

comment:51 follow-up: Changed 6 years ago by jhpalmieri

I get lots of doctest failures with this. See http://sage.math.washington.edu/home/palmieri/misc/ptest-14019-OSX.log. (This is on an OS X machine, but I see the same failures on sage.math.)

comment:52 Changed 6 years ago by git

  • Commit changed from e575742951572b4b383abeae1e21e934b9e1683f to 68c2902122a52cc16a13831b80d7a52c4e98fe86

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

68c2902fixed more spots where FinitePoset was used directly

comment:53 in reply to: ↑ 51 ; follow-up: Changed 6 years ago by aschilling

Replying to jhpalmieri:

I get lots of doctest failures with this. See http://sage.math.washington.edu/home/palmieri/misc/ptest-14019-OSX.log. (This is on an OS X machine, but I see the same failures on sage.math.)

Oopsey daisey, thanks for reporting. We forgot a couple of places in the sage library, where FinitePoset? was used directly. Should be fixed now!

comment:54 in reply to: ↑ 47 Changed 6 years ago by aschilling

Replying to jhpalmieri:

I can't even get to the point of running doctests: if I run make, then docbuilding fails with

[modmisc  ] loading pickled environment... not yet created
[modmisc  ] building [inventory]: targets for 16 source files that are out of date
[modmisc  ] updating environment: 16 added, 0 changed, 0 removed
[modmisc  ] reading sources... [  6%] index
[modmisc  ] reading sources... [ 12%] sage/modular/buzzard
Error building the documentation.

Note: incremental documentation builds sometimes cause spurious
error messages. To be certain that these are real errors, run
"make doc-clean" first and try again.
Traceback (most recent call last):
  File "/Users/palmieri/Desktop/Sage_stuff/git/sage/src/doc/common/builder.py", line 1491, in <module>
    getattr(get_builder(name), type)()
  File "/Users/palmieri/Desktop/Sage_stuff/git/sage/src/doc/common/builder.py", line 292, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/Users/palmieri/Desktop/Sage_stuff/git/sage/src/doc/common/builder.py", line 503, in _wrapper
    x.get(99999)
  File "/Users/palmieri/Desktop/Sage_stuff/git/sage/local/lib/python/multiprocessing/pool.py", line 558, in get
    raise self._value
NotImplementedError: Non injective relabeling
make: *** [doc-html] Error 1

I am not sure why/how this would be caused by this branch.

Anne

comment:55 in reply to: ↑ 53 ; follow-up: Changed 6 years ago by jhpalmieri

Replying to aschilling:

Oopsey daisey, thanks for reporting. We forgot a couple of places in the sage library, where FinitePoset? was used directly. Should be fixed now!

Unfortunately not:

----------------------------------------------------------------------
sage -t src/sage/combinat/root_system/root_lattice_realizations.py  # 2 doctests failed
sage -t src/sage/modular/modform_hecketriangle/abstract_ring.py  # 377 doctests failed
sage -t src/sage/combinat/root_system/root_system.py  # 1 doctest failed
sage -t src/sage/modular/modform_hecketriangle/graded_ring_element.py  # 386 doctests failed
sage -t src/sage/homology/cell_complex.py  # 1 doctest failed
sage -t src/sage/modular/modform_hecketriangle/abstract_space.py  # 306 doctests failed
sage -t src/sage/modular/modform_hecketriangle/space.py  # 184 doctests failed
sage -t src/sage/categories/finite_posets.py  # 4 doctests failed
sage -t src/sage/modular/modform_hecketriangle/hecke_triangle_groups.py  # 107 doctests failed
sage -t src/sage/modular/modform_hecketriangle/series_constructor.py  # 144 doctests failed
sage -t src/sage/modular/modform_hecketriangle/functors.py  # 121 doctests failed
sage -t src/doc/en/reference/coercion/index.rst  # 1 doctest failed
sage -t src/sage/modular/modform_hecketriangle/analytic_type.py  # 113 doctests failed
sage -t src/sage/modular/modform_hecketriangle/graded_ring.py  # 65 doctests failed
sage -t src/sage/modular/modform_hecketriangle/readme.py  # 94 doctests failed
sage -t src/sage/modular/modform_hecketriangle/subspace.py  # 85 doctests failed
sage -t src/sage/misc/c3_controlled.pyx  # 9 doctests failed
sage -t src/sage/modular/modform_hecketriangle/element.py  # 32 doctests failed
sage -t src/sage/modular/modform_hecketriangle/constructor.py  # 30 doctests failed
----------------------------------------------------------------------

Re docbuilding:

I am not sure why/how this would be caused by this branch.

It definitely was, but it was fixed by commit e575472.

comment:56 in reply to: ↑ 55 ; follow-up: Changed 6 years ago by aschilling

Replying to jhpalmieri:

Replying to aschilling:

Oopsey daisey, thanks for reporting. We forgot a couple of places in the sage library, where FinitePoset? was used directly. Should be fixed now!

Unfortunately not:

----------------------------------------------------------------------
sage -t src/sage/combinat/root_system/root_lattice_realizations.py  # 2 doctests failed
sage -t src/sage/modular/modform_hecketriangle/abstract_ring.py  # 377 doctests failed
sage -t src/sage/combinat/root_system/root_system.py  # 1 doctest failed
sage -t src/sage/modular/modform_hecketriangle/graded_ring_element.py  # 386 doctests failed
sage -t src/sage/homology/cell_complex.py  # 1 doctest failed
sage -t src/sage/modular/modform_hecketriangle/abstract_space.py  # 306 doctests failed
sage -t src/sage/modular/modform_hecketriangle/space.py  # 184 doctests failed
sage -t src/sage/categories/finite_posets.py  # 4 doctests failed
sage -t src/sage/modular/modform_hecketriangle/hecke_triangle_groups.py  # 107 doctests failed
sage -t src/sage/modular/modform_hecketriangle/series_constructor.py  # 144 doctests failed
sage -t src/sage/modular/modform_hecketriangle/functors.py  # 121 doctests failed
sage -t src/doc/en/reference/coercion/index.rst  # 1 doctest failed
sage -t src/sage/modular/modform_hecketriangle/analytic_type.py  # 113 doctests failed
sage -t src/sage/modular/modform_hecketriangle/graded_ring.py  # 65 doctests failed
sage -t src/sage/modular/modform_hecketriangle/readme.py  # 94 doctests failed
sage -t src/sage/modular/modform_hecketriangle/subspace.py  # 85 doctests failed
sage -t src/sage/misc/c3_controlled.pyx  # 9 doctests failed
sage -t src/sage/modular/modform_hecketriangle/element.py  # 32 doctests failed
sage -t src/sage/modular/modform_hecketriangle/constructor.py  # 30 doctests failed
----------------------------------------------------------------------

Strange, I do not get these errors:

root_system anne$ sage -t *.py
too few successful tests, not using stored timings
Running doctests with ID 2014-10-10-22-40-44-9fc5ba66.
Doctesting 44 files.
sage -t __init__.py
    [0 tests, 0.00 s]
sage -t all.py
    [0 tests, 0.00 s]
sage -t ambient_space.py
    [69 tests, 10.05 s]
sage -t associahedron.py
    [28 tests, 2.83 s]
sage -t branching_rules.py
    [252 tests, 10.29 s]
sage -t cartan_matrix.py
    [105 tests, 1.96 s]
sage -t cartan_type.py
    [408 tests, 3.53 s]
sage -t coxeter_group.py
    [28 tests, 4.64 s]
sage -t coxeter_matrix.py
    [10 tests, 0.15 s]
sage -t dynkin_diagram.py
    [104 tests, 0.84 s]
sage -t hecke_algebra_representation.py
    [286 tests, 5.06 s]
sage -t non_symmetric_macdonald_polynomials.py
    [533 tests, 13.02 s]
sage -t pieri_factors.py
    [225 tests, 13.11 s]
sage -t plot.py
    [256 tests, 28.88 s]
sage -t root_lattice_realization_algebras.py
    [309 tests, 4.04 s]
sage -t root_lattice_realizations.py
    [561 tests, 15.06 s]
sage -t root_space.py
    [77 tests, 4.89 s]
sage -t root_system.py
    [131 tests, 3.85 s]
sage -t type_A.py
    [48 tests, 0.27 s]
sage -t type_A_affine.py
    [31 tests, 0.04 s]
sage -t type_B.py
    [41 tests, 0.20 s]
sage -t type_BC_affine.py
    [44 tests, 0.05 s]
sage -t type_B_affine.py
    [27 tests, 0.04 s]
sage -t type_C.py
    [42 tests, 0.26 s]
sage -t type_C_affine.py
    [23 tests, 0.04 s]
sage -t type_D.py
    [41 tests, 0.20 s]
sage -t type_D_affine.py
    [25 tests, 0.04 s]
sage -t type_E.py
    [55 tests, 0.34 s]
sage -t type_E_affine.py
    [26 tests, 0.03 s]
sage -t type_F.py
    [39 tests, 0.31 s]
sage -t type_F_affine.py
    [19 tests, 0.03 s]
sage -t type_G.py
    [35 tests, 0.26 s]
sage -t type_G_affine.py
    [19 tests, 0.03 s]
sage -t type_H.py
    [20 tests, 0.15 s]
sage -t type_I.py
    [19 tests, 0.14 s]
sage -t type_affine.py
    [80 tests, 8.43 s]
sage -t type_dual.py
    [122 tests, 0.39 s]
sage -t type_folded.py
    [37 tests, 0.23 s]
sage -t type_reducible.py
    [72 tests, 0.30 s]
sage -t type_relabel.py
    [138 tests, 1.94 s]
sage -t weight_lattice_realizations.py
    [200 tests, 2.08 s]
sage -t weight_space.py
    [82 tests, 18.63 s]
sage -t weyl_characters.py
    [266 tests, 4.40 s]
sage -t weyl_group.py
    [180 tests, 8.64 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 176.0 seconds
    cpu time: 140.0 seconds
    cumulative wall time: 169.7 seconds
modform_hecketriangle anne$ sage -t *.py
too few successful tests, not using stored timings
Running doctests with ID 2014-10-10-22-44-49-0b9b275e.
Doctesting 15 files.
sage -t __init__.py
    [0 tests, 0.00 s]
sage -t abstract_ring.py
    [377 tests, 3.89 s]
sage -t abstract_space.py
    [309 tests, 9.34 s]
sage -t all.py
    [0 tests, 0.00 s]
sage -t analytic_type.py
    [119 tests, 0.60 s]
sage -t constructor.py
    [31 tests, 0.97 s]
sage -t element.py
    [35 tests, 1.17 s]
sage -t functors.py
    [121 tests, 1.20 s]
sage -t graded_ring.py
    [65 tests, 0.48 s]
sage -t graded_ring_element.py
    [409 tests, 24.97 s]
sage -t hecke_triangle_groups.py
    [112 tests, 1.89 s]
sage -t readme.py
    [94 tests, 4.54 s]
sage -t series_constructor.py
    [144 tests, 0.51 s]
sage -t space.py
    [186 tests, 5.31 s]
sage -t subspace.py
    [86 tests, 3.62 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 60.2 seconds
    cpu time: 57.1 seconds
    cumulative wall time: 58.5 seconds

Did you pull the latest version?

Anne

comment:57 in reply to: ↑ 56 Changed 6 years ago by aschilling

You are right (I was in the wrong branch when running the tests whilst trying to investigate the doc build failure). I get the same doc failures.

Posets are used in src/sage/modular/modform_hecketriangle/analytic_type.py

Anne

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

Hello !

I think that there is something wrong with the code for canonical label:

sage: Poset(digraphs.Path(10)).canonical_label().linear_extension()
[0, 9, 7, 5, 3, 2, 4, 6, 8, 1]

In particular, the code looks like you suppose that range(n) is a linear extension of a canonically labelled digraph, and this is wrong:

sage: digraphs.Path(10).canonical_label(certify=True)[1]
{0: 0, 1: 9, 2: 7, 3: 5, 4: 3, 5: 2, 6: 4, 7: 6, 8: 8, 9: 1}

This seems to work fine with the latest beta release

sage: Poset(digraphs.Path(10)).canonical_label().linear_extension()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Nathann

comment:59 in reply to: ↑ 58 ; follow-up: Changed 6 years ago by aschilling

Hi Nathann,

I am not quite sure why this is supposed to be wrong. As you wrote the output of canonical_label of DiGraph is

sage: D = digraphs.Path(10)
sage: D.edges()
[(0, 1, None),
 (1, 2, None),
 (2, 3, None),
 (3, 4, None),
 (4, 5, None),
 (5, 6, None),
 (6, 7, None),
 (7, 8, None),
 (8, 9, None)]
sage: D.canonical_label().edges()
[(0, 9, None),
 (2, 4, None),
 (3, 2, None),
 (4, 6, None),
 (5, 3, None),
 (6, 8, None),
 (7, 5, None),
 (8, 1, None),
 (9, 7, None)]

I do not understand why (the documentation says that this is supposed to be unique, but there seems nothing unique about this particular choice to me). But with this we obtain

sage: P = Poset(digraphs.Path(10))
sage: Pp = P.canonical_label()
sage: Pp.cover_relations()
[[0, 9], [9, 7], [7, 5], [5, 3], [3, 2], [2, 4], [4, 6], [6, 8], [8, 1]]
sage: Pp.linear_extension()
[0, 9, 7, 5, 3, 2, 4, 6, 8, 1]

which is indeed the single linear extension for this poset. If this is not the desired output, perhaps someone should rewrite the documentation and specify precisely what this *unique* poset is supposed to be. Is it supposed to be naturally labelled perhaps? Is that what your problem is? It does not say so in the documentation.

Anne

comment:60 in reply to: ↑ 59 ; follow-up: Changed 6 years ago by ncohen

Yo !

I am not quite sure why this is supposed to be wrong. As you wrote the output of canonical_label of DiGraph is

My mistake, I was convinced that I had displayed the poset with a .show() and looked at a path labelled with 0,1,2,3,... while the linear extension was 0,9,... There is nothing wrong with this example indeed.

This being said, i still do not understand the code. Is the following behaviour correct ?

sage: P = Poset(digraphs.Path(4),['a','b','c','d'],linear_extension=True)
sage: list(P.canonical_label())
[0, 1, 2, 3]

I do not understand what you do with the elements list in canonical_label given that the output is labelled with 0,1,2,3. Especially when linear_extension=False O_o

Nathann

comment:61 Changed 6 years ago by git

  • Commit changed from 68c2902122a52cc16a13831b80d7a52c4e98fe86 to eff9b6093b060eeaba124c94cf2045ff96662676

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

eff9b60fixed doc tests

comment:62 Changed 6 years ago by git

  • Commit changed from eff9b6093b060eeaba124c94cf2045ff96662676 to 8dddb16ee9bce94fab03989228cf83dd567f8ac0

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

8dddb16changes to canonical_label

comment:63 in reply to: ↑ 60 ; follow-up: Changed 6 years ago by aschilling

Hi Nathann,

My mistake, I was convinced that I had displayed the poset with a .show() and looked at a path labelled with 0,1,2,3,... while the linear extension was 0,9,... There is nothing wrong with this example indeed.

Ok. Why does the documentation say *unique* though? It does not make sense to me.

This being said, i still do not understand the code. Is the following behaviour correct ?

sage: P = Poset(digraphs.Path(4),['a','b','c','d'],linear_extension=True)
sage: list(P.canonical_label())
[0, 1, 2, 3]

I think so. The documentation says that canonical_label is supposed to label the poset with elements \{0,1,\ldots,n-1\}. I changed the code slightly, so that [0,1,2,...] is a linear extension of the canonical relabeled poset.

I do not understand what you do with the elements list in canonical_label given that the output is labelled with 0,1,2,3. Especially when linear_extension=False O_o

The documentation says that canonical relabeled means indexed by 0,1,\ldots,n-1. I did not write this code, so am not sure what this is used for.

Internally, now the poset code still stores P._hasse_diagram as a Hasse diagram on 0,1,\ldots,n-1 to make it light-weight and only compare integers internally. The elements are taken from the Hasse diagram, when elements is not specified. So passing a Hasse diagram that is on 0,1,\ldots,n-1 will automatically make the element set equal to this.

Anne

PS: I fixed the doc failures that John reported except the ones in src/sage/modular/modform_hecketriangle


New commits:

8dddb16changes to canonical_label

comment:64 in reply to: ↑ 63 ; follow-up: Changed 6 years ago by ncohen

Hello !

Ok. Why does the documentation say *unique* though? It does not make sense to me.

Take two digraphs D1,D2 labelled on whatever you want, and such that D1.is_isomorphic(D2) is True. Then D1.canonical_label()==D2.canonical_label() is True. In such a way, the output of canonical_label is unique on its isomorphism class.

To me this is a sufficient reason to raise an exception in canonical_label when an linear extension is defined: DiGraph.canonical_label ignores the linear extension, and so the output is not unique for a pair "Poset, linear extension".

I also believe that is_isomorphic should raise an exception in that case.

I think so. The documentation says that canonical_label is supposed to label the poset with elements \{0,1,\ldots,n-1\}. I changed the code slightly, so that [0,1,2,...] is a linear extension of the canonical relabeled poset.

Okay, but now the code totally ignores the linear extension that may be stored within the poset. I have nothing against that, but it would be more honest to raise an exception in that case, to say to the "PosetWithLinearExtension?" users that they should first explicitly convert their poset to a 'normal one' before computing that. We are unable to compute a canonical label for a pair "Poset, linear extension" right now.

Nathann

comment:65 in reply to: ↑ 64 ; follow-up: Changed 6 years ago by aschilling

Ok. Why does the documentation say *unique* though? It does not make sense to me.

Take two digraphs D1,D2 labelled on whatever you want, and such that D1.is_isomorphic(D2) is True. Then D1.canonical_label()==D2.canonical_label() is True. In such a way, the output of canonical_label is unique on its isomorphism class.

That condition is fine, but the labeling of the "canonical" labeling is still arbitrary and not unique (as you can see, it has changed).

To me this is a sufficient reason to raise an exception in canonical_label when an linear extension is defined: DiGraph.canonical_label ignores the linear extension, and so the output is not unique for a pair "Poset, linear extension".

Why? Your isomorphism property is still satisfied:

sage: p1 = Poset(d, linear_extension=True)
sage: p2 = p1.relabel({1:1,2:3,3:2})
sage: q1 = p1.canonical_label()
sage: q2 = p2.canonical_label()
sage: q1.is_isomorphic(q2)
True
sage: q1._linear_extension
True
sage: q2._linear_extension
True

I also believe that is_isomorphic should raise an exception in that case.

No, it checks that the posets are isomorphic (which has nothing to do with the linear extension chosen).

Anne

comment:66 in reply to: ↑ 65 ; follow-up: Changed 6 years ago by ncohen

That condition is fine, but the labeling of the "canonical" labeling is still arbitrary and not unique (as you can see, it has changed).

No, it is unique. And it is always integers from 0 to n-1.

Try it in Sage: take a graph D1 labelled on whatever you want, then compute its canonical representative R. Then relabel the vertices of D1 into a graph D2 in any way you like: the representatie of D2 will be equal to R.

Why? Your isomorphism property is still satisfied:

Two pairs "Poset, linear_extension" are "isomorphic" if there is an isomorphism of the two posets that sends the first linear extension on the second linear extension. But we never check this second part (and similarly for the canonical representatives).

For instance, if P is a poset on three points 0,1,2 where the cover relations are only (1<2), then the pair "Poset, linear extension" equal to P,[0,1,2] is not isomorphic to P,[1,0,2].

No, it checks that the posets are isomorphic (which has nothing to do with the linear extension chosen).

Indeed, and to me that is incorrect. It is quite simple: you cannot say that two "posets with linear extension" P1,P2 are isomorphic unless there is a relabel function f such that P1.relabel(f)==P2.

As it is implemented right now this does not hold.

Nathann

comment:67 Changed 6 years ago by git

  • Commit changed from 8dddb16ee9bce94fab03989228cf83dd567f8ac0 to 115a32500018148858b06dc0040fc0a4e506041a

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

f4e8c06Fixing doctests.
63b1156Merge branch 'develop' into public/combinat/poset/fix_equality-14019
115a325Fixing trivial doctest failures.

comment:68 in reply to: ↑ 66 ; follow-up: Changed 6 years ago by tscrim

Replying to ncohen:

That condition is fine, but the labeling of the "canonical" labeling is still arbitrary and not unique (as you can see, it has changed).

No, it is unique. And it is always integers from 0 to n-1.

Try it in Sage: take a graph D1 labelled on whatever you want, then compute its canonical representative R. Then relabel the vertices of D1 into a graph D2 in any way you like: the representatie of D2 will be equal to R.

However the labeling itself is not unique. Consider the path on 3 vertices with labelings 0 - 1 - 2 and 1 - 0 - 2. The first one is no more canonical than the second.

Two pairs "Poset, linear_extension" are "isomorphic" if there is an isomorphism of the two posets that sends the first linear extension on the second linear extension. But we never check this second part (and similarly for the canonical representatives).

For instance, if P is a poset on three points 0,1,2 where the cover relations are only (1<2), then the pair "Poset, linear extension" equal to P,[0,1,2] is not isomorphic to P,[1,0,2].

No, it checks that the posets are isomorphic (which has nothing to do with the linear extension chosen).

Indeed, and to me that is incorrect. It is quite simple: you cannot say that two "posets with linear extension" P1,P2 are isomorphic unless there is a relabel function f such that P1.relabel(f)==P2.

As it is implemented right now this does not hold.

It depends on what we want to actually check. Yet as currently stated in the documentation of is_isomorphic, it does return the correct value as it checks "if both posets are isomorphic". My thought is that if we decide we want to also check with a specified linear extension, then we add another argument to is_isomorphic. At present, the method should not raise an error, and this should probably be done on another ticket.

Anyways, doctests are now all fixed.

comment:69 follow-up: Changed 6 years ago by git

  • Commit changed from 115a32500018148858b06dc0040fc0a4e506041a to aa1cc73510663efb9552f12dd432109c8fd0d20d

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

aa1cc73two more doc fixes in order_tree

comment:70 in reply to: ↑ 69 ; follow-ups: Changed 6 years ago by aschilling

There were two more doc test failures in combinat/ordered_trees.py due to the non-canonical way of labeling the vertices in canonical_label. I fixed those. Everything else looks ok to me.

However the labeling itself is not unique. Consider the path on 3 vertices with labelings 0 - 1 - 2 and 1 - 0 - 2. The first one is no more canonical than the second.

Precisely!

John: if you are happy now, can we set it back to positive review?

Nathann: if you are still unhappy, please change the behavior in a different ticket. In this ticket we wanted to keep the behavior of the posets with _linear_extension = True as previous.

comment:71 follow-up: Changed 6 years ago by git

  • Commit changed from aa1cc73510663efb9552f12dd432109c8fd0d20d to c5c6a0c6c0cc48a2ce6a89652aaccb48b35b987a

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

c5c6a0coops, undid the ipython change

comment:72 in reply to: ↑ 71 Changed 6 years ago by aschilling

Oops, sorry, I accidentally pushed the ipython change (without which my sage does not even start any longer) ... but that is a problem with the most recent develop branch.

comment:73 Changed 6 years ago by jmantysalo

Should I complain here that relabel is also broken with return type:

P=LatticePoset({1:[2]})
P.relabel(lambda x: x+1)

outputs "Finite poset containing 2 elements".

comment:74 in reply to: ↑ 68 Changed 6 years ago by ncohen

Hello,

It depends on what we want to actually check. Yet as currently stated in the documentation of is_isomorphic, it does return the correct value as it checks "if both posets are isomorphic". My thought is that if we decide we want to also check with a specified linear extension, then we add another argument to is_isomorphic. At present, the method should not raise an error, and this should probably be done on another ticket.

Well. I am convinced that you understand what is happening right now, and that you know how and why it is that while two posets object P1,P2 may be reported to be isomorphic by Sage, it does not necessarily mean that there is a relabelling of one that makes it equal to the other. I will not fight for the bugs of this 'poset with linear extension' feature.

Nathann

comment:75 in reply to: ↑ 70 Changed 6 years ago by ncohen

Hello !

Nathann: if you are still unhappy, please change the behavior in a different ticket. In this ticket we wanted to keep the behavior of the posets with _linear_extension = True as previous.

Well I still have to look at the commits you added, but otherwise it does it job. Thanks for fixing that bug in the end.

Nathann

comment:76 Changed 6 years ago by ncohen

Hello,

Besides Jori's report, I have one question. Why did you do this change ?

-        G = DiGraph(self._hasse_diagram).relabel(self._list, inplace=False)
+        G = DiGraph(self._hasse_diagram).relabel(self._elements, inplace=False)

Did the meaning of self._list changed in some way ? If it did, this function probably isn't the only one that needs to be updated O_o

More importantly: aren't self._list and self._elements the same thing ? It would be nice in a later patch to change this name is something like linear_extension, for it really is a pain to work with this class when variables are not named according to what they represent. And perhaps one day it will become trustworthy :-P

Thanks,

Nathann

comment:77 follow-ups: Changed 6 years ago by tscrim

  • Status changed from needs_work to needs_review

No, self._list are wrapped elements (if not a facade), whereas self._elements are always the unwrapped elements, and we always want to label the digraph by the unwrapped elements.

The return type of relabel should be another ticket IMO.

comment:78 in reply to: ↑ 70 Changed 6 years ago by jhpalmieri

Replying to aschilling:

John: if you are happy now, can we set it back to positive review?

As long as doctests pass and the documentation builds, I'm happy. I'm also not seriously reviewing this ticket -- I haven't looked at any of the code and I don't plan to -- so everyone else needs to be happy, too.

comment:79 in reply to: ↑ 77 ; follow-up: Changed 6 years ago by ncohen

No, self._list are wrapped elements (if not a facade), whereas self._elements are always the unwrapped elements, and we always want to label the digraph by the unwrapped elements.

Okay. Do you have any objections if later the following variables are renamed

  • _list -> _linear_extension_of_wrapped_elements
  • _elements -> _linear_extension_of_unwrapped_elements

By the way, what would you think in this ticket of renaming the linear_extension parameter you added ? The name does not sound at all like it is a boolean variable, and you create a Poset._linear_extension variable which is boolean. If you renamed it to Poset._carries_linear_extension or something (whose name sounds like a boolean variable) we could rename _list to _linear_extension and _elements to _linear_extension_unwrapped_elements (which I think is better/shorter).

The thing is that if we have to rename linear_extension later we will have to deprecate it --> loss of time.

Nathann

comment:80 in reply to: ↑ 79 ; follow-up: Changed 6 years ago by aschilling

Replying to ncohen:

No, self._list are wrapped elements (if not a facade), whereas self._elements are always the unwrapped elements, and we always want to label the digraph by the unwrapped elements.

Okay. Do you have any objections if later the following variables are renamed

  • _list -> _linear_extension_of_wrapped_elements
  • _elements -> _linear_extension_of_unwrapped_elements

By the way, what would you think in this ticket of renaming the linear_extension parameter you added ? The name does not sound at all like it is a boolean variable, and you create a Poset._linear_extension variable which is boolean. If you renamed it to Poset._carries_linear_extension or something (whose name sounds like a boolean variable) we could rename _list to _linear_extension and _elements to _linear_extension_unwrapped_elements (which I think is better/shorter).

The thing is that if we have to rename linear_extension later we will have to deprecate it --> loss of time.

Nathann

Go ahead and write a review patch which makes these changes!

Anne

comment:81 in reply to: ↑ 77 Changed 6 years ago by jmantysalo

Replying to tscrim:

The return type of relabel should be another ticket IMO.

OK, let it be part of #17142.

comment:82 in reply to: ↑ 80 ; follow-up: Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_work

Go ahead and write a review patch which makes these changes!

I will. The branch still does not pass tests though

sage -t --long src/sage/categories/finite_coxeter_groups.py

Nathann

comment:83 in reply to: ↑ 82 ; follow-up: Changed 6 years ago by aschilling

Replying to ncohen:

Go ahead and write a review patch which makes these changes!

I will. The branch still does not pass tests though

sage -t --long src/sage/categories/finite_coxeter_groups.py

On both Travis' and my machine there is no problem

sage -t --long finite_coxeter_groups.py
too few successful tests, not using stored timings
Running doctests with ID 2014-10-13-14-15-29-a31aa4aa.
Doctesting 1 file.
sage -t --long finite_coxeter_groups.py
    [91 tests, 7.57 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 8.0 seconds
    cpu time: 6.1 seconds
    cumulative wall time: 7.6 seconds

Please post at least the error that you get!

comment:84 in reply to: ↑ 83 ; follow-up: Changed 6 years ago by ncohen

Yo !

On both Travis' and my machine there is no problem

O_o

Weird.

Please post at least the error that you get!

I get three things like that

sage -t --long categories/finite_coxeter_groups.py
**********************************************************************
File "categories/finite_coxeter_groups.py", line 143, in sage.categories.finite_coxeter_groups.FiniteCoxeterGroups.ParentMethods.bruhat_poset
Failed example:
    P.show()
Exception raised:
    Traceback (most recent call last):
      File "/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 488, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 851, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.categories.finite_coxeter_groups.FiniteCoxeterGroups.ParentMethods.bruhat_poset[3]>", line 1, in <module>
        P.show()
      File "/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/combinat/posets/posets.py", line 1523, in show
        vertex_size=vertex_size, vertex_colors=vertex_colors, layout=layout).show(**kwds)
      File "/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/combinat/posets/posets.py", line 1497, in plot
        **kwds)
      File "/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/misc/decorators.py", line 550, in wrapper
        return func(*args, **options)
      File "/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 15675, in plot
        return self.graphplot(**options).plot()
      File "/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 15376, in graphplot
        return GraphPlot(graph=self, options=options)
      File "/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/graph_plot.py", line 247, in __init__
        self.set_vertices()
      File "/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/graph_plot.py", line 426, in set_vertices
        self._pos[v], rgbcolor=(0,0,0), zorder=8))
    KeyError: [0 0 1]
    [0 1 0]
    [1 0 0]

Nathann

comment:85 in reply to: ↑ 84 ; follow-up: Changed 6 years ago by aschilling

Do you get these errors without the branch applied?

Anne

comment:86 in reply to: ↑ 85 Changed 6 years ago by ncohen

Do you get these errors without the branch applied?

I do not.

comment:87 Changed 6 years ago by tscrim

Works for me in a sage session too; same for view(P, tightpage=True).

FTR, I have Coxeter3, dot2tex, database_gap, and gap_packages installed on my machine.

comment:88 Changed 6 years ago by jhpalmieri

For what it's worth, I see the same errors as Nathann both on sage.math and on an OS X 10.9 machine.

comment:89 Changed 6 years ago by git

  • Commit changed from c5c6a0c6c0cc48a2ce6a89652aaccb48b35b987a to 02e3dabb60bd4b7e63622966b6f4bfe07f94439f

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

02e3dabReverted change in hasse_diagram() to fix poset show(). Fixed related issue in dual().

comment:90 Changed 6 years ago by tscrim

  • Status changed from needs_work to needs_review

This should fix the problems. I reverted the change that made hasse_diagram()'s labels be the labels as opposed to (for non-facade parents) elements of the poset. I also made a related change in dual(). I uninstalled dot2tex from my machine and was able to reproduce the error and checked things in that state and after re-installing dot2tex.

comment:91 Changed 6 years ago by tscrim

FTR, this conflicts with #16933 which also removes the p(i) for p[i] thing.

comment:92 Changed 6 years ago by ncohen

Okay, after having tried again I will not rename those attributes ._list and ._elements, for it breaks doctests everywhere as everybody calls the private parameters directly.

Nathann

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

comment:93 follow-up: Changed 6 years ago by git

  • Commit changed from 02e3dabb60bd4b7e63622966b6f4bfe07f94439f to e677d31fa4e40822bcd00c509dd1ca94ed6de52d

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

e677d31trac #14019: rename _linear_extension to _carries_linear_extension

comment:94 in reply to: ↑ 93 ; follow-up: Changed 6 years ago by nthiery

Replying to git:

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

e677d31trac #14019: rename _linear_extension to _carries_linear_extension

Thanks so much everyone for your work on this! Big kuddos to Anne and Travis for taking the lead!

I read the discussion, and the decisions taken make sense to me. I still need to have a look at the code, but what I had seen in an earlier version Anne had pointed me too was looking good, so feel free to proceed anyway.

Just one thing: I would prefer _with_linear_extension rather than _carries_linear_extensions since we already use this convention in our "WithBasis?" and friends. I can do this change if you wish.

comment:95 in reply to: ↑ 94 ; follow-up: Changed 6 years ago by aschilling

Just one thing: I would prefer _with_linear_extension rather than _carries_linear_extensions since we already use this convention in our "WithBasis?" and friends. I can do this change if you wish.

That is fine with me! Travis and I are done with the patch, so you can change whatever you two agree on!

Best,

Anne

comment:96 in reply to: ↑ 95 ; follow-up: Changed 6 years ago by ncohen

That is fine with me! Travis and I are done with the patch, so you can change whatever you two agree on!

No prob !

Nathann

comment:97 in reply to: ↑ 96 ; follow-up: Changed 6 years ago by aschilling

Replying to ncohen:

That is fine with me! Travis and I are done with the patch, so you can change whatever you two agree on!

No prob !

Are we done now and can set positive review?

Anne

comment:98 in reply to: ↑ 97 Changed 6 years ago by ncohen

Are we done now and can set positive review?

Nicolas wants to rename something.

Nathann

comment:99 follow-up: Changed 6 years ago by git

  • Commit changed from e677d31fa4e40822bcd00c509dd1ca94ed6de52d to 3afec891b4d2d75b659c163c540bf02606477810

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

3afec89renamed _carries_linear_extension to _with_linear_extension

comment:100 in reply to: ↑ 99 Changed 6 years ago by aschilling

I renamed _carries_linear_extension to _with_linear_extension. Please set a positive review now if you are happy!

Anne

comment:101 Changed 6 years ago by git

  • Commit changed from 3afec891b4d2d75b659c163c540bf02606477810 to 1c0d02dd479f1805b3250bd8d79257e94369bffd

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

46f4fdcremove deprecated code
ea330d3revert remove of iterator() and list()
2e4f269Merge remote-tracking branch 'origin/develop' into depr_func
cf77bc2deprecate compact argument
c79991eMerge branch 'u/aapitzsch/ticket/16933' of trac.sagemath.org:sage into public/combinat/poset/fix_equality-14019
1c0d02dMerge branch 'public/combinat/poset/fix_equality-14019' of trac.sagemath.org:sage into public/combinat/poset/fix_equality-14019

comment:102 Changed 6 years ago by tscrim

  • Dependencies changed from #17059 to #17059 #16933
  • Status changed from needs_review to positive_review

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

comment:103 Changed 6 years ago by aschilling

  • Authors changed from Travis Scrimshaw, Anne Schilling to Nathann Cohen, John Palmieri, Travis Scrimshaw, Anne Schilling

comment:104 Changed 6 years ago by vbraun

  • Dependencies changed from #17059 #16933 to #17059, #16933, #16933
  • Status changed from positive_review to needs_work

Breaks docbuild after #16933 is applied.

comment:105 Changed 6 years ago by git

  • Commit changed from 1c0d02dd479f1805b3250bd8d79257e94369bffd to 23de9f5da6ad88e771740e0ecc9404d9b39d283f

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

23de9f5Fixing documentation and references.

comment:106 Changed 6 years ago by tscrim

  • Authors changed from Nathann Cohen, John Palmieri, Travis Scrimshaw, Anne Schilling to Nathann Cohen, Travis Scrimshaw, Anne Schilling
  • Dependencies changed from #17059, #16933, #16933 to #17059, #16933
  • Reviewers changed from Travis Scrimshaw, Anne Schilling to Travis Scrimshaw, Anne Schilling, John Palmieri
  • Status changed from needs_work to positive_review

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.

comment:107 Changed 6 years ago by aschilling

  • Authors changed from Nathann Cohen, Travis Scrimshaw, Anne Schilling to Travis Scrimshaw, Anne Schilling
  • Reviewers changed from Travis Scrimshaw, Anne Schilling, John Palmieri to Travis Scrimshaw, Anne Schilling, John Palmieri, Nathann Cohen

comment:108 Changed 6 years ago by vbraun

  • Branch changed from public/combinat/poset/fix_equality-14019 to 23de9f5da6ad88e771740e0ecc9404d9b39d283f
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:109 Changed 6 years ago by nthiery

  • Commit 23de9f5da6ad88e771740e0ecc9404d9b39d283f deleted
  • Reviewers changed from Travis Scrimshaw, Anne Schilling, John Palmieri, Nathann Cohen to Travis Scrimshaw, Anne Schilling, John Palmieri, Nathann Cohen, Nicolas M. Thiéry

Thanks Anne for finalizing!

Note: See TracTickets for help on using tickets.