From poset to lattice: Do not copy Hasse Diagram

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

P = Poset({0:[1]})
Q = Poset(P)
L = LatticePoset(P)
P._hasse_diagram is Q._hasse_diagram, P._hasse_diagram is L._hasse_diagram

outputs (True, False). Hence Hasse diagram, which is immutable, is copied --- and so also meet and join matrix will be computed twice.

CC: @tscrim

Component: combinatorics

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

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

comment:2

Actually this happens with just posets:

P = Poset({0:[1]})
R = Poset(P, facade=False)
P._hasse_diagram is R._hasse_diagram

also outputs False. I can see no reason for this either. And still more, what about

P = Poset({0:[1]})
Q = P.relabel(lambda i: chr(ord('a')+i))
P._hasse_diagram is Q._hasse_diagram

? Relabeling does not touch the underlying digraph of plain ints.

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

comment:3

If I remove the line hasse_diagram = hasse_diagram.copy(immutable=True) from posets.py, it seems that no test will fail. And still I got False when testing P._hasse_diagram is Q._hasse_diagram. Might be because

self._hasse_diagram = HasseDiagram(hasse_diagram.relabel(rdict, inplace=False), data_structure="static_sparse")

in __init__() does the copy. Maybe this relates to adding immutable graphs, and now copying is unnecessary?

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

comment:4

Might be because

self._hasse_diagram = HasseDiagram(hasse_diagram.relabel(rdict, inplace=False), data_structure="static_sparse")

Yes, this line would trigger a (relabelled) copy of the graph.

Nathann

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

comment:5

Travis, you might be interested in this.

To start with easy one: Why relabel() does not just have same Hasse diagram, and different _vertex_to_element etc? Is there something untrivial I can't see?

[tscrim]

comment:6

It has to do with how the constructor processes the digraph input as it gets the labels from the digraph vertex labels IIRC. When Anne and I were refactoring the class, we decided not to make backwards incompatible changes and not break things that required fixed linear extensions (and were under pressure because of some fud). There might be a better solution, but it would likely require a massive overhaul to keep certain (doctested) features from breaking.

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

comment:7

Sorry, but I do not understand. What is "required fixed linear extensions"?

For example there is three possible linear extension for the pentagon poset. If I do relabel(lambda i: chr(ord('a')+i)) to it, why I can not use exactly same Hasse diagram, and so exactly same linear extension? Or to say it by code, what will following break?

P=Posets.PentagonPoset()
P._elements=('a','b','c','d','e')
P._element_to_vertex_dict={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4}
P._list=('a','b','c','d','e')

[tscrim]

comment:8

There is some code which depends on the poset data including a particular (fixed) linear extension. I don't remember off-hand what it is, but doctests will break if that functionality to not specify a linear extension is removed. IIRC, it is this which requires the labels of the digraph to be used. Try looking in the linear extension file.

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

comment:9

Found it. After my example code Posets.PentagonPoset() will return poset with elements 'a'..'e'.

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

comment:10

See also #20434.

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

comment:11

The problem seems to be in UniqueRepresentation:

A = Poset( ([0,1,2], []) )
A._elements = ('a','b','c')
A._element_to_vertex_dict = {'a': 0, 'b': 1, 'c': 2}
A._list = ('a','b','c')
B = Poset( ([0,1,2], []) )
C = Poset( ([0,1,2], []), key="heyhou")
A.list(), B.list(), C.list()

outputs (['a', 'b', 'c'], ['a', 'b', 'c'], [2, 1, 0]).

This is too complicated for me, so I suggest this one to be closed.

[tscrim]

comment:12

What you are doing is clear abuse, and so we should not worry about that. We just need some code path in the constructor that shortcuts to FinitePoset (or FiniteLatticePoset) when given a poset and/or Hasse diagram.

[tscrim]

Description changed:

--- 
+++ 
@@ -6,6 +6,6 @@
 P._hasse_diagram is Q._hasse_diagram, P._hasse_diagram is L._hasse_diagram

-outputs (True, False). Hence Hasse diagram, which is immutable, is copied --- and so also meet and join matrix will be computed twise. +outputs (True, False). Hence Hasse diagram, which is immutable, is copied --- and so also meet and join matrix will be computed twice.

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

comment:13

Replying to @tscrim:

What you are doing is clear abuse, and so we should not worry about that. We just need some code path in the constructor that shortcuts to FinitePoset (or FiniteLatticePoset) when given a poset and/or Hasse diagram.

OK, but I raise my hands: can't do.

And the problem is smaller now, when meets and joins are faster to compute (thanks for review, btw).

[tscrim]

comment:14

I will try and find some time to work on this, but I can't promise anything in the next few days.

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

comment:15

Replying to @tscrim:

I will try and find some time to work on this, but I can't promise anything in the next few days.

Of course I am not against this, but as said, less important after several other changes.

[tscrim]

comment:16

At least with how we are currently doing things, there doesn't seem to be a way around this. I'm changing this to a wishlist item.