Opened 7 years ago
Last modified 6 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 )
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 7 years ago by
- Cc ncohen added
comment:2 Changed 7 years ago by
comment:3 follow-up: ↓ 4 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
- 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 7 years ago by
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 7 years ago by
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 7 years ago by
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 7 years ago by
Found it. After my example code Posets.PentagonPoset()
will return poset with elements 'a'..'e'
.
comment:10 Changed 6 years ago by
See also #20434.
comment:11 Changed 6 years ago by
- 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: ↓ 13 Changed 6 years ago by
- 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 6 years ago by
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
(orFiniteLatticePoset
) 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: ↓ 15 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
- 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.
Actually this happens with just posets:
also outputs
False
. I can see no reason for this either. And still more, what about? Relabeling does not touch the underlying digraph of plain
int
s.