Opened 10 years ago

Closed 8 years ago

# equality is broken for Posets

Reported by: Owned by: ncohen sage-combinat major sage-6.4 combinatorics posets hivert, nthiery, nborie, VivianePons, chapoton, aschilling, stumpc5, jmantysalo Travis Scrimshaw, Anne Schilling Travis Scrimshaw, Anne Schilling, John Palmieri, Nathann Cohen, Nicolas M. Thiéry N/A 23de9f5 #17059, #16933 #14185

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

### comment:1 Changed 10 years ago by ncohen

• Description modified (diff)

### comment:2 Changed 10 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 10 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 10 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 10 years ago by ncohen

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

Same result.

### comment:6 follow-up: ↓ 7 Changed 10 years ago by ncohen

• 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

### comment:7 in reply to: ↑ 6 ; follow-up: ↓ 9 Changed 10 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:9 in reply to: ↑ 7 ; follow-up: ↓ 12 Changed 10 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 10 years ago by ncohen (previous) (diff)

### comment:10 Changed 10 years ago by ncohen

• Description modified (diff)

### comment:11 Changed 10 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: ↓ 13 Changed 10 years ago by nthiery

Hi Nathann,

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: ↓ 14 Changed 10 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 10 years ago by ncohen (previous) (diff)

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

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 10 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 8 years ago by ncohen (previous) (diff)

### comment:16 follow-up: ↓ 18 Changed 10 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 10 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 10 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 10 years ago by 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 10 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 9 years ago by lftabera

• Stopgaps set to #14185

### comment:22 Changed 9 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:23 Changed 9 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 9 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:

 ​a1a85ff Importing Nathann's patch ​8c2aeff trac #15479: Finite Words should be proud of their finiteness
Last edited 9 years ago by andrew.mathas (previous) (diff)

### comment:25 Changed 9 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 9 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 9 years ago by git

• Commit changed from a1a85ff09dcc34a56b9362a9d4461d907296718e to d10a6efa75561632cdc76b2c98c5eca4312372ec

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

 ​d10a6ef Importing Nathann's patch

### comment:28 Changed 9 years ago by andrew.mathas

I have just undone my mistaken branching off #15479

### comment:29 Changed 9 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:30 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:31 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:32 Changed 8 years ago by ncohen

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 8 years ago by ncohen (previous) (diff)

### comment:33 follow-up: ↓ 34 Changed 8 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: ↓ 35 ↓ 36 Changed 8 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 8 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 8 years ago by jmantysalo

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 8 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 8 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: ↓ 41 Changed 8 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 8 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
• 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:

 ​691807b `Fixed issues with relabeling and elements. Fixed some doctests.` ​d5c570c `Some more fixes.` ​a1eca30 `reinstated linear_extension` ​95f735b `getting the interface right!` ​01dc92d `needed one more relabelling for correct linear extensions` ​f1511c0 `Fixing bugs in relabeling by not doing it automatically in __classcall__.` ​6f86a9a `fixed some docs` ​c7e7107 `Fixed last issues. All doctests pass.` ​ed7f091 `more doc test fixes` ​b1eefd7 `Some more documentation as reference.`

### comment:42 Changed 8 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: ↓ 49 Changed 8 years ago by ncohen

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

Nathann

### comment:44 Changed 8 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: ↓ 50 Changed 8 years ago by vbraun

• Status changed from positive_review to needs_work

Merge conflict, too

### comment:46 Changed 8 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: ↓ 54 Changed 8 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 8 years ago by git

• Commit changed from b1eefd78cd65736b44153761b929de1c4387cb70 to e575742951572b4b383abeae1e21e934b9e1683f

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

 ​e575742 `fixed failing doc tests`

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

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 8 years ago by tscrim

Merge conflict, too

What tickets does it conflict with?

### comment:51 follow-up: ↓ 53 Changed 8 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 8 years ago by git

• Commit changed from e575742951572b4b383abeae1e21e934b9e1683f to 68c2902122a52cc16a13831b80d7a52c4e98fe86

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

 ​68c2902 `fixed more spots where FinitePoset was used directly`

### comment:53 in reply to: ↑ 51 ; follow-up: ↓ 55 Changed 8 years ago by aschilling

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 8 years ago by aschilling

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: ↓ 56 Changed 8 years ago by jhpalmieri

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: ↓ 57 Changed 8 years ago by 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]
[65 tests, 0.48 s]
[409 tests, 24.97 s]
sage -t hecke_triangle_groups.py
[112 tests, 1.89 s]
[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
```

Anne

### comment:57 in reply to: ↑ 56 Changed 8 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: ↓ 59 Changed 8 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: ↓ 60 Changed 8 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: ↓ 63 Changed 8 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 8 years ago by git

• Commit changed from 68c2902122a52cc16a13831b80d7a52c4e98fe86 to eff9b6093b060eeaba124c94cf2045ff96662676

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

 ​eff9b60 `fixed doc tests`

### comment:62 Changed 8 years ago by git

• Commit changed from eff9b6093b060eeaba124c94cf2045ff96662676 to 8dddb16ee9bce94fab03989228cf83dd567f8ac0

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

 ​8dddb16 `changes to canonical_label`

### comment:63 in reply to: ↑ 60 ; follow-up: ↓ 64 Changed 8 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:

 ​8dddb16 `changes to canonical_label`

### comment:64 in reply to: ↑ 63 ; follow-up: ↓ 65 Changed 8 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: ↓ 66 Changed 8 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: ↓ 68 Changed 8 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 8 years ago by git

• Commit changed from 8dddb16ee9bce94fab03989228cf83dd567f8ac0 to 115a32500018148858b06dc0040fc0a4e506041a

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

 ​f4e8c06 `Fixing doctests.` ​63b1156 `Merge branch 'develop' into public/combinat/poset/fix_equality-14019` ​115a325 `Fixing trivial doctest failures.`

### comment:68 in reply to: ↑ 66 ; follow-up: ↓ 74 Changed 8 years ago by tscrim

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: ↓ 70 Changed 8 years ago by git

• Commit changed from 115a32500018148858b06dc0040fc0a4e506041a to aa1cc73510663efb9552f12dd432109c8fd0d20d

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

 ​aa1cc73 `two more doc fixes in order_tree`

### comment:70 in reply to: ↑ 69 ; follow-ups: ↓ 75 ↓ 78 Changed 8 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: ↓ 72 Changed 8 years ago by git

• Commit changed from aa1cc73510663efb9552f12dd432109c8fd0d20d to c5c6a0c6c0cc48a2ce6a89652aaccb48b35b987a

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

 ​c5c6a0c `oops, undid the ipython change`

### comment:72 in reply to: ↑ 71 Changed 8 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 8 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 8 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 8 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 8 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: ↓ 79 ↓ 81 Changed 8 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 8 years ago by jhpalmieri

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: ↓ 80 Changed 8 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: ↓ 82 Changed 8 years ago by aschilling

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 8 years ago by jmantysalo

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: ↓ 83 Changed 8 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: ↓ 84 Changed 8 years ago by aschilling

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: ↓ 85 Changed 8 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: ↓ 86 Changed 8 years ago by aschilling

Do you get these errors without the branch applied?

Anne

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

Do you get these errors without the branch applied?

I do not.

### comment:87 Changed 8 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 8 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 8 years ago by git

• Commit changed from c5c6a0c6c0cc48a2ce6a89652aaccb48b35b987a to 02e3dabb60bd4b7e63622966b6f4bfe07f94439f

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

 ​02e3dab `Reverted change in hasse_diagram() to fix poset show(). Fixed related issue in dual().`

### comment:90 Changed 8 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 8 years ago by tscrim

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

### comment:92 Changed 8 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 8 years ago by ncohen (previous) (diff)

### comment:93 follow-up: ↓ 94 Changed 8 years ago by git

• Commit changed from 02e3dabb60bd4b7e63622966b6f4bfe07f94439f to e677d31fa4e40822bcd00c509dd1ca94ed6de52d

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

 ​e677d31 `trac #14019: rename _linear_extension to _carries_linear_extension`

### comment:94 in reply to: ↑ 93 ; follow-up: ↓ 95 Changed 8 years ago by nthiery

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

 ​e677d31 `trac #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: ↓ 96 Changed 8 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: ↓ 97 Changed 8 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: ↓ 98 Changed 8 years ago by aschilling

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 8 years ago by ncohen

Are we done now and can set positive review?

Nicolas wants to rename something.

Nathann

### comment:99 follow-up: ↓ 100 Changed 8 years ago by git

• Commit changed from e677d31fa4e40822bcd00c509dd1ca94ed6de52d to 3afec891b4d2d75b659c163c540bf02606477810

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

 ​3afec89 `renamed _carries_linear_extension to _with_linear_extension`

### comment:100 in reply to: ↑ 99 Changed 8 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 8 years ago by git

• Commit changed from 3afec891b4d2d75b659c163c540bf02606477810 to 1c0d02dd479f1805b3250bd8d79257e94369bffd

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`

### comment:102 Changed 8 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 8 years ago by aschilling

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

### comment:104 Changed 8 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 8 years ago by git

• Commit changed from 1c0d02dd479f1805b3250bd8d79257e94369bffd to 23de9f5da6ad88e771740e0ecc9404d9b39d283f

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

 ​23de9f5 `Fixing documentation and references.`

### comment:106 Changed 8 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 8 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 8 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