Opened 4 years ago
Closed 4 years ago
#18516 closed defect (fixed)
Posets: canonical_label() returns a poset from lattice
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage6.8 
Component:  combinatorics  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Nathann Cohen, Jori Mäntysalo  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  48952c1 (Commits)  Commit:  48952c18d6ba6ccd6750d8fb537adc5b3831aa0d 
Dependencies:  Stopgaps: 
Description
sage: L=LatticePoset({1:[2]}); L Finite lattice containing 2 elements sage: L.canonical_label() Finite poset containing 2 elements
Canonically relabeling a (semi)lattice should return a (semi)lattice. (Compare to .relabel()
.)
Change History (26)
comment:1 Changed 4 years ago by
 Branch set to u/jmantysalo/posets__canonical_label___returns_a_poset_from_lattice
comment:2 Changed 4 years ago by
 Cc ncohen added
 Commit set to c742ca4204a252d2ebebe4a2dd6d037469f019c4
 Status changed from new to needs_review
comment:3 followup: ↓ 5 Changed 4 years ago by
Hellooooo,
Why wouldn't just call FinitePoset.relabel
which already handles that?
Nathann
comment:4 Changed 4 years ago by
 Status changed from needs_review to needs_info
comment:5 in reply to: ↑ 3 ; followup: ↓ 6 Changed 4 years ago by
comment:6 in reply to: ↑ 5 Changed 4 years ago by
I don't understand. How? Calling
canonical_label
from DiGraph? gives a DiGraph?, not a dictionary that could be directly used forrelabel()
.
sage: graphs.PetersenGraph().canonical_label(certify=True) (Graph on 10 vertices, {0: 9, 1: 8, 2: 5, 3: 4, 4: 6, 5: 7, 6: 2, 7: 3, 8: 1, 9: 0})
Honestly I don't see why canonical_label
should always return a copy of the graph. In this present case, we see that it is not necessary at all O_o
Nathann
comment:7 followup: ↓ 8 Changed 4 years ago by
OK. But actually... How is self.canonical_label()
different from Poset(self._hasse_diagram, linear_extension=self._with_linear_extension, category=self.category(), facade=self._is_facade)
? I.e. when is canonical label of Hasse diagram not already on canonically numbered?
comment:8 in reply to: ↑ 7 Changed 4 years ago by
I.e. when is canonical label of Hasse diagram not already on canonically numbered?
I am not sure I understand your question, but there is no reason why _hasse_diagram
should be canonically labelled by default, even though it is integervalued.
comment:9 Changed 4 years ago by
The point of using FinitePoset.relabel
directly is that it handles the 'class' (Lattice
, MeetSemiLattice
, ...) already.
comment:10 followup: ↓ 11 Changed 4 years ago by
OK, so you mean to convert this to oneliner
self.relabel(self.cover_relations_graph().canonical_label(certify=True)[1])
? Then relabel()
will take care of facade property, poset vs. lattice thing and so on.
comment:11 in reply to: ↑ 10 Changed 4 years ago by
self.relabel(self.cover_relations_graph().canonical_label(certify=True)[1])? Then
relabel()
will take care of facade property, poset vs. lattice thing and so on.
Yep, that's the idea. Though you can avoid creating a copy of the graph by: 1) computing the canonical label on _hasse_diagram 2) "relabel the canonical label" using the correspondance between _hasse_diagram vertices and poset vertices 3) call relabel on the poset itself with the "relabelled" canonical label
Nathann
comment:12 Changed 4 years ago by
Uh, got a headache. So you mean
self.relabel({self._list[e]:e for e in self._hasse_diagram.canonical_label(certify=True)[1]})
?
comment:13 followup: ↓ 14 Changed 4 years ago by
I added a commit at public/18516.
It also fixes a bug, as the embedded linear extension seemed to be excluded from the relabelling.
Nathann
comment:14 in reply to: ↑ 13 ; followup: ↓ 15 Changed 4 years ago by
Replying to ncohen:
I added a commit at public/18516.
Why those # random
parts on doctests? And isn't sorted
unneeded, as the order of 'a' and 'b' is always the same?
Also you say that this issue is now corrected, but give an example with relabel
function, not with canonical_relabel
?
comment:15 in reply to: ↑ 14 ; followup: ↓ 16 Changed 4 years ago by
Hello !
Why those
# random
parts on doctests?
Because the doctests wrongly assume that the canonical label should never change. We had this problem with bliss: the canonical labels it returns are different from the ones returned by 'native' Sage.
A labelling is 'canonical' in the sense that two isomorphic object will be relabelled to the same object. This being said, nothing says that a canonical label never changes in time, and in particular the documentation of Nauty says explicitly that it will.
And isn't
sorted
unneeded, as the order of 'a' and 'b' is always the same?
I am not sure. These letters will be stored on dictionaries, and you never know what happens with dictionaires on different architectures. Anyway I removed that, because of your next comment:
Also you say that this issue is now corrected, but give an example with
relabel
function, not withcanonical_relabel
?
My mistake. I added another commit at the same location.
Nathann
comment:16 in reply to: ↑ 15 Changed 4 years ago by
Replying to ncohen:
A labelling is 'canonical' in the sense that two isomorphic object will be relabelled to the same object. This being said, nothing says that a canonical label never changes in time, and in particular the documentation of Nauty says explicitly that it will.
OK. It seems to be good now, but I don't have time to test it just now.
comment:17 Changed 4 years ago by
 Branch changed from u/jmantysalo/posets__canonical_label___returns_a_poset_from_lattice to public/18516
 Commit changed from c742ca4204a252d2ebebe4a2dd6d037469f019c4 to ab6d104ac2c0462b12a20589cd7cb6cc79b38381
comment:18 Changed 4 years ago by
 Commit changed from ab6d104ac2c0462b12a20589cd7cb6cc79b38381 to b33c09759c0f5f45b693048e73c0ab74e3829dcb
Branch pushed to git repo; I updated commit sha1. New commits:
b33c097  Some documentation changes.

comment:19 Changed 4 years ago by
After canonical relabeling we should be sure of the *elements* of the poset, even if not sure of their *position*, i.e. cover relations. Hence I removed a # random
. But it seems that sorted
does not work. Strange, what did I forgot?
I also moved a part of documentation from tests to examples.
Maybe these were stupid changes and should be reverted.
comment:20 Changed 4 years ago by
 Commit changed from b33c09759c0f5f45b693048e73c0ab74e3829dcb to f55472a231b756ac4d14e513bf2a2bbe3f94b9da
comment:21 followup: ↓ 22 Changed 4 years ago by
I should not code today. There is no order for nonfacade elements.
comment:22 in reply to: ↑ 21 Changed 4 years ago by
I should not code today. There is no order for nonfacade elements.
Yeah. I hate those things.
comment:23 Changed 4 years ago by
 Commit changed from f55472a231b756ac4d14e513bf2a2bbe3f94b9da to 48952c18d6ba6ccd6750d8fb537adc5b3831aa0d
Branch pushed to git repo; I updated commit sha1. New commits:
48952c1  Correction for facade vs. nonfacade posets.

comment:24 Changed 4 years ago by
 Status changed from needs_info to needs_review
OK, now it should work.
comment:25 Changed 4 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
Yep !
comment:26 Changed 4 years ago by
 Branch changed from public/18516 to 48952c18d6ba6ccd6750d8fb537adc5b3831aa0d
 Resolution set to fixed
 Status changed from positive_review to closed
Simple correction.
New commits:
Corrected canonical_label().