Opened 6 years ago

# From poset to lattice: Do not copy Hasse Diagram

Reported by: Owned by: jmantysalo major sage-wishlist combinatorics tscrim N/A

```P = Poset({0:})
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.

### comment:2 Changed 5 years ago by jmantysalo

Actually this happens with just posets:

```P = Poset({0:})
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:})
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 `int`s.

### comment:3 follow-up: ↓ 4 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

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: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: ↓ 13 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

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: ↓ 15 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.