#8878: Use Dijkstra to discover shortest coercion path
---------------------------------+------------------------------------------
Reporter: nthiery | Owner: robertwb
Type: defect | Status: needs_work
Priority: major | Milestone:
Component: coercion | Keywords: coercion, morphism
Author: Nicolas M. Thiéry | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
---------------------------------+------------------------------------------
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.
>
> 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.
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)
}}}
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8878#comment:2>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
