#18791: Matroid k-connectivity
-------------------------------------+-------------------------------------
Reporter: chaoxu | Owner:
Type: enhancement | Status: positive_review
Priority: minor | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: Chao Xu | Reviewers: Rudi Pendavingh
Report Upstream: N/A | Work issues:
Branch: u/chaoxu/k | Commit:
-connectivity-intersection | a5ec517a99ff130dd35a1f728bf081ac121c5577
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Chao Xu', 'oldvalue': ''}):
* status: needs_review => positive_review
* reviewer: => Rudi Pendavingh
* author: => Chao Xu
Comment:
Code looks good to me. It's a lot faster than before too..
I tested with
{{{
def matroid_with_k_separation(r,n,k):
if r<=k or n<=2*k:
return
A=MatrixSpace(GF(293),r,n).random_element()
m = ZZ.random_element(k,n/2)
X = set(Subsets(range(n), m).random_element())
Y = set(range(n))-X
s = ZZ.random_element(max(m-n+r,0), min(m-k, r-k)+1)
for i in range(s+k, r):
for j in X:
A[i,j] =0
for i in range(s+1):
for j in Y:
A[i,j] =0
return Matroid(A),X
}}}
to get a matroid with a k-separation and
{{{
k=5
for i in range(100):
M, X = matroid_with_k_separation(12,24,k-1)
print M
c, X = M.is_kconnected(k,True)
if c or M.connectivity(X)>k-1 or min(len(X),
len(M.groundset()-X))<=M.connectivity(X):
print '!!'
break
}}}
to test-drive the code on some random examples.
Positive review.
--
Ticket URL: <http://trac.sagemath.org/ticket/18791#comment:12>
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.
