#15303: Coercion discovery fails to be transitive
-------------------------------------+-------------------------------------
Reporter: nbruin | Owner:
Type: defect | Status: needs_work
Priority: major | Milestone: sage-5.13
Component: coercion | Resolution:
Keywords: | Merged in:
Authors: Simon King | Reviewers:
Report Upstream: N/A | Work issues: Implement
Branch: | backtracking properly
u/SimonKing/ticket/15303 | Commit:
Dependencies: #14711 | 74821fe5409c3104b5d6eb7407a8287d54170df9
| Stopgaps:
-------------------------------------+-------------------------------------
Comment (by SimonKing):
Replying to [comment:54 nbruin]:
> Above, you also talk about "forbidden" and "temporarily forbidden"
paths. Are those part of the depth-first path discovery?
Of course. By "temporarily forbidden", I mean those that have already been
visited in the depth-first search and shall thus not be visited again
during the same search. Thus "temporarily", because in the next search
they could be visited.
> That would be an even better reason to see if we can get a "cheapest
first" search in, since that naturally avoids cycles.
How would that be?
Also note that if you want to compare costs, you need to construct the
maps. It could become very costly, if you want to compare many paths.
> Replying to [comment:53 SimonKing]:
> Can we explain these rules purely in terms of the coercion graph?
Somehow (see below).
> Does `_coerce_map_from_(..)==True` somehow indicate an edge with a
property (colour?) that should be avoided or an edge with the cost
modified (increased)?
Not at all. `_coerce_map_from_` is only called if there is no edge. Note
that "long time ago" (in one of the posts above) I talked about "short-
cuts" in the coerce digraph. `_coerce_map_from_` is for the shortcuts, not
for the edges.
So, in terms of the coerce digraph: We have a digraph with some connected
components X,Y. It is possible that there is a coercion from a node x in X
to a node y in Y; this is the case of `y._coerce_map_from_(x)` returns
True or returns a map. However, this does not mean that an edge is
inserted that would connect X and Y: The two components remain separate,
and a reference to any node in Y does not prevent the whole component X
from garbage collection.
This situation is easy. Difficulties only arise if x and y belong to ''the
same'' component X. In this situation, we may have several possibilities
to construct a map from x to y: There could be different paths in X, and
there could be a map provided by `y._coerce_map_from_(x)`, or
`y._coerce_map_from_(x)` returns True. In the latter case, it means that
we can use `y._generic_convert_map(x)` for coercion.
Which of these maps to choose? It is required that these maps are
mathematically the same. So, our choice can not be based on the maths
only.
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:58>
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.
