#18784: Tutte connectors for matroids
-------------------------------------+-------------------------------------
Reporter: Rudi | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/Rudi/tutte_connectors_for_matroids|
9acd9ebb43fbfe42eb22d5cd881056b80a50a020
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by Rudi):
My implementation of link() uses matroid intersection just like in
connectivity(), but now I've implemented that algorithm for class Matroid
without the actual construction of the two minors, and I also wrote a
bitpacked version in class BasisExchangeMatroid.
I used this new function link() to speed up both connectivity() and
_is_3connected_CE. Here's the effect on the latter function.
Before:
{{{
sage: M = Matroid(MatrixSpace(GF(2), 100,200).random_element())
sage: %time M._is_3connected_CE(True)
CPU times: user 3min 10s, sys: 982 ms, total: 3min 11s
Wall time: 3min 12s
(True, None)
}}}
After:
{{{
sage: M = Matroid(MatrixSpace(GF(2), 100,200).random_element())
sage: %time M._is_3connected_CE(True)
CPU times: user 1.12 s, sys: 1.68 ms, total: 1.12 s
Wall time: 1.13 s
(True, None)
}}}
Of course, this is still horrible compared to Chao's BC implementation.
{{{
sage: %time M._is_3connected_BC()
CPU times: user 46.5 ms, sys: 1.14 ms, total: 47.6 ms
Wall time: 50.8 ms
True
}}}
But connectivity(S,T) also got 180x faster.
Will go on to tweak and test a bit. Meanwhile, if anyone has a strong
opinion on the name `link()`, discuss. It's easy to change it at this
stage.
--
Ticket URL: <http://trac.sagemath.org/ticket/18784#comment:3>
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.
