Posets: canonical_label() returns a poset from lattice

[f29946bc-ee7b-48cd-9abc-3445948c551d]

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().)

CC: @nathanncohen

Component: combinatorics

Author: Nathann Cohen, Jori Mäntysalo

Branch/Commit: 48952c1

Reviewer: Nathann Cohen

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

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Branch: u/jmantysalo/posetscanonicallabelreturns_a_poset_from_lattice

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Author: Jori Mäntysalo

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Commit: c742ca4

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:2

Simple correction.

---

New commits:

c742ca4

Corrected canonical_label().

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:3

Hellooooo,

Why wouldn't just call FinitePoset.relabel which already handles that?

Nathann

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:5

Replying to @nathanncohen:

Why wouldn't just call FinitePoset.relabel which already handles that?

I don't understand. How? Calling canonical_label from DiGraph gives a DiGraph, not a dictionary that could be directly used for relabel().

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:6

I don't understand. How? Calling canonical_label from DiGraph gives a DiGraph, not a dictionary that could be directly used for relabel().

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

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:7

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?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:8

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 integer-valued.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:9

The point of using FinitePoset.relabel directly is that it handles the 'class' (Lattice, MeetSemiLattice, ...) already.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:10

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.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:11

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

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:12

Uh, got a headache. So you mean

self.relabel({self._list[e]:e for e in self._hasse_diagram.canonical_label(certify=True)[1]})

?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:13

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

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:14

Replying to @nathanncohen:

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?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:15

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 with canonical_relabel?

My mistake. I added another commit at the same location.

Nathann

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:16

Replying to @nathanncohen:

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.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

New commits:

6f074d5	trac #18516: Bugfix
ab6d104	trac 18516: Incorrect doctest

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Changed commit from c742ca4 to ab6d104

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Changed branch from u/jmantysalo/posetscanonicallabelreturns_a_poset_from_lattice to public/18516

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ab6d104 to b33c097

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b33c097

Some documentation changes.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:19

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

37626bc	Added sorted() to docstring.
f55472a	Duh. Facade-vs-not -thing.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b33c097 to f55472a

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:21

I should not code today. There is no order for non-facade elements.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:22

I should not code today. There is no order for non-facade elements.

Yeah. I hate those things.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

48952c1

Correction for facade vs. non-facade posets.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f55472a to 48952c1

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:24

OK, now it should work.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Changed author from Jori Mäntysalo to Nathann Cohen, Jori Mäntysalo

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:25

Yep !

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Reviewer: Nathann Cohen

[vbraun]

Changed branch from public/18516 to 48952c1