#18784: Tutte connectors for matroids
-------------------------------------+-------------------------------------
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:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/Rudi/tutte_connectors_for_matroids|
8ade550090c5b4e43f1683c74826aebe4abfb4ce
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by Rudi):
* status: new => needs_review
Comment:
I'm done.
I saw that _is_3connected_CE did not always respond to `certificate=True`
(in paticular when there were loops or coloops). So I repaired that,
making extra sure that all the fringe cases are handled correctly.
Tested _is_3connected_CE on all matroids of size <=9. I also recycled
Stefan's test for Chao's implementation of BC:
{{{
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_CE()
}}}
Indirectly all this also tests the correctness of the new method `link()`.
The time needed to detect a smallest separation using connectivity(S,T)
improved significantly. I'll post some timings later, right now all of
sage is recompiling.
Needs review.
--
Ticket URL: <http://trac.sagemath.org/ticket/18784#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.
