#8878: Use Dijkstra to discover shortest coercion path
--------------------------------------+-------------------------------------
Reporter: nthiery | Owner: robertwb
Type: defect | Status: needs_work
Priority: major | Milestone:
Component: coercion | Resolution:
Keywords: coercion, morphism | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Nicolas M. Thiéry | Merged in:
Dependencies: | Stopgaps:
--------------------------------------+-------------------------------------
Description changed by nthiery:
Old description:
> 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)
> }}}
New description:
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)
}}}
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8878#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
