Opened 5 years ago

Closed 3 years ago

#25183 closed defect (fixed)

Bug in the associahedron object

Reported by: Jean-Philippe Labbé Owned by:
Priority: major Milestone: sage-9.0
Component: geometry Keywords: associahedron
Cc: Frédéric Chapoton, Christian Stump, Travis Scrimshaw, Moritz Firsching, Jean-Philippe Labbé, Laith Rastanawi Merged in:
Authors: Jonathan Kliem Reviewers: Jean-Philippe Labbé, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: d9083b7 (Commits, GitHub, GitLab) Commit: d9083b70195aafacf95eb991e21099136101ce3d
Dependencies: #27798 Stopgaps:

Status badges

Description (last modified by gh-kliem)

The following lines currently occur:

sage: A = polytopes.associahedron(['A',3])
sage: face = A.faces(2)[3]
sage: face
<6,8,9,10>
sage: face.as_polyhedron()
/home/jplabbe/sage/local/lib/python2.7/site-packages/sage/repl/rich_output/display_manager.py:590: RichReprWarning: Exception in _rich_repr_ while displaying object: 'Associahedra_with_category.element_class' object has no attribute '_cartan_type'
  RichReprWarning,
<repr(<sage.combinat.root_system.associahedron.Associahedra_with_category.element_class at 0x7f48d0d7ad70>) failed: AttributeError: 'Associahedra_with_category.element_class' object has no attribute '_cartan_type'>

The construction as_polyhedron initializes the new (face-)polyhedron via P.__class__(parent, Vrep, None). In the case of the associahedron, this does not give a valid object, as the associahedron requires a cartan type as well.

Same (or similar problem) with:

  • minkowski_sum,
  • minkowski_difference,
  • translation,
  • dilation,
  • convex_hull,
  • intersection (actually even worse as coercion fails),
  • polar.

We fix the initialization of the associahedron to now require the cartan type on __init__ (before it was assumed to be set after initialization).

Further we have __new__ return the correct parent class such that e.g. the face of an Associahedron_class_ppl is constructed as Polyhedron_ppl.

We fix _coerce_map_from_ to take into account that no general polyhedron can be coerced to an associahedron.

We manually set the correct pushout of polyhedra over ZZ and associahedra (over QQ) to be polyhedra over QQ.

Change History (17)

comment:1 Changed 5 years ago by Moritz Firsching

Cc: Moritz Firsching added

comment:2 Changed 4 years ago by gh-kliem

I think I took care of it in #27798.

comment:3 Changed 4 years ago by gh-kliem

Authors: Jonathan Kliem
Branch: public/25183
Commit: 65b11c9de95bb2ecde90c722ca2e9781fdac7cc5
Dependencies: 27798
Description: modified (diff)
Status: newneeds_review

This branch should fix the bug.

Feel free to change it, alter it, abonden it, etc.

Maybe there is a better way to obtain the correct parent, i.e. improve the following lines:

156             for typ1 in ancestors_of_associahedron:
157                 if typ1 in mro:
158                     return typ1(parent, Vrep, Hrep, **kwds)

New commits:

2643078added `backend` to associahedron and flow polytope
a9b4826typo
8716985corrected docstring
b873156associahedron actually uses the claimed backend now
1f4bb25comments by tscrim
2c812c5should have fixed bug in #25183
65b11c9removed redundant line

comment:4 Changed 4 years ago by gh-kliem

Dependencies: 27798#27798

comment:5 Changed 3 years ago by gh-kliem

Milestone: sage-8.2sage-8.9

comment:6 Changed 3 years ago by gh-kliem

Status: needs_reviewneeds_work

Once #27798 is done, I'm going to rebase it and solve the merge conflict. At the moment it seems pointless to me.

comment:7 Changed 3 years ago by gh-kliem

Description: modified (diff)

comment:8 Changed 3 years ago by git

Commit: 65b11c9de95bb2ecde90c722ca2e9781fdac7cc50e892e7019001400faf0c3cfed542fffd3ac7227

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

949b0a9added `backend` to associahedron and flow polytope
e137199changed default value of `backend`; small changes in documentation
0e892e7modify construction and coercion of associahedra to fix bug #25183

comment:9 Changed 3 years ago by gh-kliem

Description: modified (diff)
Status: needs_workneeds_review

comment:10 Changed 3 years ago by gh-kliem

I think I got things fixed now. Suggestions for better solutions are welcome.

comment:11 Changed 3 years ago by gh-kliem

Cc: Jean-Philippe Labbé Laith Rastanawi added

comment:12 Changed 3 years ago by Jean-Philippe Labbé

Reviewers: Jean-Philippe Labbé

That looks good to me. Might be good to have some feedback from Travis or Frédéric on the cartan side of things, if they are done properly.

I would put this to positive review since the error appears to be fixed.

comment:13 Changed 3 years ago by Travis Scrimshaw

I don't have any comments on the Cartan side as you are not really doing anything with them. However, I do have one comment about this code block:

            for typ1 in ancestors_of_associahedron:
                if typ1 in mro:
                    return typ1(parent, Vrep, Hrep, **kwds)

My understanding is there is no subclass relations among the classes in ancestors_of_associahedron. So I think it is faster to make that a set object and test

            for typ1 in mro:
                if typ1 in ancestors_of_associahedron:
                    return typ1(parent, Vrep, Hrep, **kwds)

as set containment check is much faster and these classes are likely to be higher in the MRO. It also has a side effect of making all of these classes run in the same time. For example, imagine if you are looking for a Polyhedron_polymake, that means it has to check the through the entire MRO 4 times (and a bit more to actually find it). So this could become really expensive if you create lots of (temporary) associahedra.

Last edited 3 years ago by Travis Scrimshaw (previous) (diff)

comment:14 Changed 3 years ago by gh-kliem

Branch: public/25183public/25183-reb
Commit: 0e892e7019001400faf0c3cfed542fffd3ac7227d9083b70195aafacf95eb991e21099136101ce3d

New commits:

cc20d20modify construction and coercion of associahedra to fix bug #25183
d9083b7small change of order of iteration to be more efficient

comment:15 Changed 3 years ago by gh-kliem

Changed to order of iteration, such that it only runs once through mro now.

comment:16 Changed 3 years ago by Travis Scrimshaw

Milestone: sage-8.9sage-9.0
Reviewers: Jean-Philippe LabbéJean-Philippe Labbé, Travis Scrimshaw
Status: needs_reviewpositive_review

Thanks. LGTM.

comment:17 Changed 3 years ago by Volker Braun

Branch: public/25183-rebd9083b70195aafacf95eb991e21099136101ce3d
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.