Ticket #8878 (needs_work defect)

Opened 3 years ago

Last modified 3 years ago

Use Dijkstra to discover shortest coercion path

Reported by: nthiery Owned by: robertwb
Priority: major Milestone:
Component: coercion Keywords: coercion, morphism
Cc: sage-combinat Work issues:
Report Upstream: N/A Reviewers:
Authors: Nicolas M. Thiéry Merged in:
Dependencies: Stopgaps:

Description (last modified by nthiery) (diff)

In #7420, it was discussed that the current coercion model is using depth first search to find for coercion paths between different parents, and that it would be better to use breath-first / Dijkstra to get a shortest coercion path. For example, we obtained once a coercion path of length 20 among symmetric functions.

Patch under development on the Sage-Combinat server:  http://combinat.sagemath.org/hgwebdir.cgi/patches/file/tip/trac_8878_coerce_dijkstra-nt.patch

Note: the following issue is probably related:

A = CombinatorialFreeModule(QQ, ZZ, prefix = "A")
B = CombinatorialFreeModule(QQ, ZZ, prefix = "B")
C = CombinatorialFreeModule(QQ, ZZ, prefix = "C")
D = CombinatorialFreeModule(QQ, ZZ, prefix = "D")

def make_morph(X, Y):
    X.module_morphism(Y.monomial).register_as_coercion()

make_morph(A,B)
make_morph(B,A)

make_morph(C,A)

make_morph(D,C)

d = D.monomial(1)

A(d)
B(d)

Change History

comment:1 Changed 3 years ago by nthiery

  • Status changed from new to needs_work

comment:2 Changed 3 years ago by nthiery

  • Description modified (diff)
Note: See TracTickets for help on using tickets.