#18429: Add the matroid connectivity function
-------------------------------------+-------------------------------------
Reporter: Rudi | Owner: Rudi
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: Rudi Pendavingh | Reviewers: Travis Scrimshaw
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/matroid/add_matroid_connectivity-18429|
9b55e71cbde687f3385ef19f98abc188ccc7362c
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by Rudi):
Replying to [comment:17 tscrim]:
> Do you have some timings between the current version and your proposed
version of `is_3connected`?
With the current version:
{{{
sage: M= matroids.named_matroids.T12()
sage: timeit("M.is_3connected()")
5 loops, best of 3: 91.4 ms per loop
sage: N= matroids.named_matroids.Terrahawk()
sage: timeit("N.is_3connected()")
5 loops, best of 3: 1.4 s per loop
}}}
With the proposed one:
{{{
sage: M=matroids.named_matroids.T12()
sage: timeit("M.is_3connected()")
125 loops, best of 3: 8.12 ms per loop
sage: N=matroids.named_matroids.Terrahawk()
sage: timeit("N.is_3connected()")
25 loops, best of 3: 20.7 ms per loop
}}}
M has 12 elements, N has 16 elements.
>Also should we just change this to a method `is_k_connected`, as I think
all we'd need to change is `< 2` to `< k-1`?
It's a bit more work, you should enumerate all partitions of a fixed
`k`-set into two sets, extend each of them them to a pair of disjoint
k-sets from the ground set, then compute connectivity between the two
sets. If you do this, there may be other optimizations to consider, like
the best order in which to process these pairs.
But more importantly, k-connectivity is part of the plans for this `google
summer of code'. I do not want to interfere with those plans.
--
Ticket URL: <http://trac.sagemath.org/ticket/18429#comment:18>
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.
