Opened 10 years ago

Last modified 6 years ago

#8878 needs_work defect

Use Dijkstra to discover shortest coercion path

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

Description (last modified by nthiery)

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.

A preliminary patch lies on the Sage-Combinat server: http://combinat.sagemath.org/patches/file/tip/trac_8878_coerce_dijkstra-nt.patch but has not been touched in a long while and has most likely bit roten.

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 (4)

comment:1 Changed 10 years ago by nthiery

  • Status changed from new to needs_work

comment:2 Changed 10 years ago by nthiery

  • Description modified (diff)

comment:3 Changed 6 years ago by darij

The link to sage-combinat is dead.

(Posting this mainly to get a CC on this ticket.)

comment:4 Changed 6 years ago by nthiery

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