Use Dijkstra to discover shortest coercion path

[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)

CC: @sagetrac-sage-combinat

Component: coercion

Keywords: morphism

Author: Nicolas M. Thiéry

Issue created by migration from https://trac.sagemath.org/ticket/8878

[darijgr]

comment:3

The link to sage-combinat is dead.

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