#18910: Boost minimum spanning tree
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Boost, minimum | Merged in:
spanning tree | Reviewers:
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | 4bbb2980aab4b0a81fc07cf62afa5395ee7719c1
u/borassi/boost_minimum_spanning_tree| Stopgaps:
Dependencies: #18876, #18906 |
-------------------------------------+-------------------------------------
Comment (by dcoudert):
The documentation builds properly and is now good.
I tracked all calls to `min_spanning_tree` to launch tests. All tests pass
in graphs and homology.
However, one test is broken in `src/sage/matroids/utilities.py`, method
`lift_cross_ratios`. I suspect that this is due to the change in the
output ordering of edges.
I don't know what to do here. I have forced you to sort edges because all
methods where not returning edges in the same order, and I think it is
better now (the output is independent on the algorithm).
The set T constructed in this method is, before applying this patch:
{{{
set([((0, 0), (0, 1), (0, 0)), ((0, 0), (2, 1), (0, 2)), ((0, 1), (1, 0),
(1, 0)), ((1, 0), (1, 1), (1, 1)), ((1, 1), (2, 0), (2, 1)), ((0, 0), (3,
1), (0, 3)), ((0, 0), (4, 1), (0, 4))])
}}}
and with this patch:
{{{
set([((0, 0), (0, 1), (0, 0)), ((0, 0), (2, 1), (0, 2)), ((0, 1), (1, 0),
(1, 0)), ((1, 0), (1, 1), (1, 1)), ((2, 0), (2, 1), (2, 2)), ((0, 0), (3,
1), (0, 3)), ((0, 0), (4, 1), (0, 4))])
}}}
So only one entry differs: `((1, 1), (2, 0), (2, 1))` becomes `((2, 0),
(2, 1), (2, 2))`.
I don't know if we can safely update the expected output of this test or
not. Nathann?
--
Ticket URL: <http://trac.sagemath.org/ticket/18910#comment:13>
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/d/optout.
