Opened 6 years ago

Last modified 4 years ago

#18776 needs_work enhancement

From poset to lattice: Do not copy Hasse Diagram

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-wishlist
Component: combinatorics Keywords:
Cc: tscrim Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by tscrim)

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.

Change History (16)

comment:1 Changed 6 years ago by ncohen

  • Cc ncohen added

comment:2 Changed 5 years ago by jmantysalo

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.

comment:3 follow-up: Changed 5 years ago by jmantysalo

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?

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

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

comment:5 Changed 5 years ago by jmantysalo

  • Cc tscrim added

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?

comment:6 Changed 5 years ago by tscrim

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.

comment:7 Changed 5 years ago by jmantysalo

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')

comment:8 Changed 5 years ago by tscrim

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.

comment:9 Changed 5 years ago by jmantysalo

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

comment:10 Changed 5 years ago by jmantysalo

See also #20434.

comment:11 Changed 4 years ago by jmantysalo

  • Milestone changed from sage-wishlist to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

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.

comment:12 follow-up: Changed 4 years ago by tscrim

  • Cc ncohen removed
  • Description modified (diff)
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-7.5
  • Status changed from needs_review to needs_work

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.

comment:13 in reply to: ↑ 12 Changed 4 years ago by jmantysalo

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

comment:14 follow-up: Changed 4 years ago by tscrim

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

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

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.

comment:16 Changed 4 years ago by tscrim

  • Milestone changed from sage-7.5 to sage-wishlist

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.

Note: See TracTickets for help on using tickets.