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: sage-6.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 jmantysalo

  • Branch set to u/jmantysalo/posets__canonical_label___returns_a_poset_from_lattice

comment:2 Changed 4 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Cc ncohen added
  • Commit set to c742ca4204a252d2ebebe4a2dd6d037469f019c4
  • Status changed from new to needs_review

Simple correction.


New commits:

c742ca4Corrected canonical_label().

comment:3 follow-up: Changed 4 years ago by ncohen

Hellooooo,

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

Nathann

comment:4 Changed 4 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:5 in reply to: ↑ 3 ; follow-up: Changed 4 years ago by jmantysalo

Replying to ncohen:

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

comment:6 in reply to: ↑ 5 Changed 4 years ago by ncohen

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

comment:7 follow-up: Changed 4 years ago by jmantysalo

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 ncohen

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.

comment:9 Changed 4 years ago by ncohen

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

comment:10 follow-up: Changed 4 years ago by jmantysalo

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 ncohen

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 jmantysalo

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 follow-up: Changed 4 years ago by ncohen

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 ; follow-up: Changed 4 years ago by jmantysalo

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 ; follow-up: Changed 4 years ago by ncohen

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

comment:16 in reply to: ↑ 15 Changed 4 years ago by jmantysalo

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 jmantysalo

  • Branch changed from u/jmantysalo/posets__canonical_label___returns_a_poset_from_lattice to public/18516
  • Commit changed from c742ca4204a252d2ebebe4a2dd6d037469f019c4 to ab6d104ac2c0462b12a20589cd7cb6cc79b38381

New commits:

6f074d5trac #18516: Bugfix
ab6d104trac 18516: Incorrect doctest

comment:18 Changed 4 years ago by git

  • Commit changed from ab6d104ac2c0462b12a20589cd7cb6cc79b38381 to b33c09759c0f5f45b693048e73c0ab74e3829dcb

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

b33c097Some documentation changes.

comment:19 Changed 4 years ago by jmantysalo

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 git

  • Commit changed from b33c09759c0f5f45b693048e73c0ab74e3829dcb to f55472a231b756ac4d14e513bf2a2bbe3f94b9da

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

37626bcAdded sorted() to docstring.
f55472aDuh. Facade-vs-not -thing.

comment:21 follow-up: Changed 4 years ago by jmantysalo

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

comment:22 in reply to: ↑ 21 Changed 4 years ago by ncohen

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

Yeah. I hate those things.

comment:23 Changed 4 years ago by git

  • Commit changed from f55472a231b756ac4d14e513bf2a2bbe3f94b9da to 48952c18d6ba6ccd6750d8fb537adc5b3831aa0d

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

48952c1Correction for facade vs. non-facade posets.

comment:24 Changed 4 years ago by jmantysalo

  • Authors changed from Jori Mäntysalo to Nathann Cohen, Jori Mäntysalo
  • Status changed from needs_info to needs_review

OK, now it should work.

comment:25 Changed 4 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Yep !

comment:26 Changed 4 years ago by vbraun

  • Branch changed from public/18516 to 48952c18d6ba6ccd6750d8fb537adc5b3831aa0d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.