#18539: faster matroid 3 connectivity
-------------------------------------+-------------------------------------
Reporter: chaoxu | Owner: chaoxu
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: Chao Xu | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/chaoxu/faster_matroid_3_connectivity|
eca042a03f89753c1254d982e0dd663ec7d1b686
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Chao Xu', 'oldvalue': ''}):
* status: needs_review => needs_work
* author: => Chao Xu
Comment:
Rudi, feel free to review any GSoC tickets.
FWIW, here's a slightly more generic test where the 2-separation is a
truly random partition:
{{{
def test_3c(n,m):
A = Matrix(GF(2), n, m)
k = ZZ.random_element(n)
R = set([ZZ.random_element(n) for i in range(k)])
k = ZZ.random_element(m)
C = set([ZZ.random_element(m) for i in range(k)])
if len(R) + m - len(C) < 2 or len(C) + n - len(R) < 2:
print "boundary case"
return False
# Rank-1 submatrix indexed by R, C
Rs = {x: ZZ.random_element(2) for x in R}
Cs = {x: ZZ.random_element(2) for x in C}
for i in range(n):
for j in range(m):
if i in R and j in C:
A[i,j] = Rs[i] * Cs[j]
elif i in R or j in C:
A[i,j] = ZZ.random_element(2)
else:
A[i,j] = 0
return Matroid(field=GF(2), reduced_matrix=A).is_3connected()
}}}
which I ran a bunch of times:
{{{
%time
for n in range(10,20):
for m in range(15,25):
for k in range(1000):
if test_3c(n,m):
print "Whoops"
print "ok"
}}}
Took under 36 seconds on my laptop.
Now, for the review of this ticket.
* You removed the optional argument to is_3connected. When I told you not
to implement it at this point, I didn't realize the argument was already
there. For now, I would say you have a second helper method (something
like _is_3connected_naive) that does the old, brute-force thing. You can't
just remove functionality from Sage without a deprecation period.
* Every method, even the hidden ones, needs an EXAMPLES:: section for
testing purposes. The code snippets in that section are run and compared
against the provided output for every new release of Sage. This ensures
everything keeps working as it should. You can run those tests with
{{{./sage -t src/sage/matroids/*.py*}}} from the Sage home directory. You
can test if your code satisfies the requirements by running {{{./sage
-coverage src/sage/matroids/*.py*}}}
* The helper function does not need a "SEEALSO" section, but it DOES need
an explicit description of assumptions on the instances for which it is
invoked (simple, at least 4 elements, etc.)
* The comment in line 4727 is confusing
* In line 4730, why do you make a copy?
* Maybe name the helper function _is_3connected_BC to indicate which
algorithm it implements? That way, we can also have an
_is_3connected_shifting version.
Apart from that, the code looks clean. If you make these changes, it can
get a positive review.
--
Ticket URL: <http://trac.sagemath.org/ticket/18539#comment:31>
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.
