#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|
9d932ee9b5e693b46fd7bfbd0da2ebb1d1bfdcc2
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by chaoxu):
All tests pass.
The code looks alright.
All 3-connectivity related code passes.
I use the following code to test k connectivity, which also verifies
link().
{{{
cpdef is_kconnected(self, k):
if k<=2:
return self.is_connected()
if not self.is_kconnected(k-1):
return False
m = k-1
E = set(self.groundset())
w = {e:1 for e in E}
Q = set(list(E)[:m])
E = E-Q
I = set()
for r in range(len(Q)/2):
for Q1 in map(set,combinations(Q, r)):
Q2 = Q-Q1
for A in map(set,combinations(E, m - len(Q1))):
T = Q1|A
for B in map(set,combinations(E-A, m - len(Q2))):
S = Q2|B
if(self.connectivity(T,S)<m):
return False
return True
}}}
some tests which shows expected behavior, uniform matroids
{{{
def test_uniform(n):
for i in range(3,n):
for j in range(i*2+2,3*i+2):
if not matroids.Uniform(i,j).is_kconnected(i+1):
return False
if matroids.Uniform(i,j).is_kconnected(i+2):
return False
return True
sage: test_uniform(7):
True
}}}
testing affine geometries
{{{
sage: matroids.AG(5,2).is_kconnected(4)
True
sage: matroids.AG(5,2).is_kconnected(5)
False
sage: matroids.AG(6,2).is_kconnected(4)
True
sage: matroids.AG(6,2).is_kconnected(5)
False
sage: matroids.AG(7,2).is_kconnected(4)
True
sage: matroids.AG(7,2).is_kconnected(5)
False
}}}
I will tests some more before giving a positive review.
--
Ticket URL: <http://trac.sagemath.org/ticket/18784#comment:23>
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.
