#18791: Matroid k-connectivity
-------------------------------------+-------------------------------------
Reporter: chaoxu | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: u/chaoxu/k | Commit:
-connectivity-intersection | 87d7ff6812f5525c82e717290d3c25df62e5b4ad
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by Rudi):
Hi Chao,
just saw that you had finished this one. I have some comments on the code
below:
{{{
m = k-1
E = set(self.groundset())
w = {e:1 for e in E}
Q = set(list(E)[:m])
E = E-Q
for r in range(len(Q)/2):
for Q1 in map(set,combinations(Q, r)):
Q2 = Q-Q1
# Given Q1, Q2 partition of Q, find all extensions
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
I, _ = self._link(S, T)
if(len(I) - self.full_rank() + self.rank(S) +
self.rank(T) < m):
if certificate:
return False, I
return False
}}}
- w is defined but not used
- `I` is not the min separation, but the max connector. If you have `I, X
= self._link(S, T)`, then `return False, X`. You could even do without `I`
if you tested the connectivity by `if self._connectivity(X)<m:`
- if `r == len(Q)/2`, then the unordered pair {Q1, Q2} is generated and
tested twice.
The set of pairs {S,T} tested by your code is what Bixby & Cunningham
describe in their paper to argue that O(n^k^) connectivity tests are
enough. It will not be possible to attain o(n^k^) pairs, but the constant
hidden by the O() can be significantly better.
E.g. in the r-th iteration, set aside r elements R from E-Q, also split R
in all possible ways R1, R2, and then put S= Q1|R1|A, T=Q2|R2|B. The A and
B you need are now smaller (|A|+|B| went down by r), hence fewer
possibilities. Another optimization is this: once you are done testing all
A containing a given e, you have established that e must be on the other
side of the separation and so you may as well fix it in B, again reducing
the number of possibilities for B. And this can be iterated of course.
For a positive review, it would be enough that you fix the above three
points, and that the code passes some tests I will run of course.
Optimizing the number of connectivity tests is not necessary, but would be
appreciated. It is actually an interesting question what is the minimum
number of tests as a function of n,k here.
--
Ticket URL: <http://trac.sagemath.org/ticket/18791#comment:5>
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.
