Opened 6 years ago
Closed 6 years ago
#18784 closed enhancement (fixed)
Tutte connectors for matroids
Reported by:  Rudi  Owned by:  Rudi 

Priority:  major  Milestone:  sage6.8 
Component:  matroid theory  Keywords:  
Cc:  chaoxu, Stefan, yomcat  Merged in:  
Authors:  Rudi Pendavingh  Reviewers:  Chao Xu 
Report Upstream:  N/A  Work issues:  
Branch:  9d932ee (Commits, GitHub, GitLab)  Commit:  9d932ee9b5e693b46fd7bfbd0da2ebb1d1bfdcc2 
Dependencies:  Stopgaps: 
Description (last modified by )
Tutte's linking theorem states that if S
, T
are disjoint subsets of the ground set of a matroid M
, then
\min\{\lambda_M(X): S\subseteq X, X\cap T =\emptyset\}
equals
\max\{\lambda_N(S): E(N)=S\cup T, N= M/I\setminus J\}
Here \lambda_M(X):=r_M(X)+r_M(EX)r_M(E)
is the connectivity of X
in M
.
Write a function that outputs both an optimal X
(a min separation) and an optimal I
(a max connector) as in Tutte's linking theorem.
Change History (26)
comment:1 Changed 6 years ago by
 Branch set to u/Rudi/tutte_connectors_for_matroids
comment:2 Changed 6 years ago by
 Commit set to 9acd9ebb43fbfe42eb22d5cd881056b80a50a020
comment:3 Changed 6 years ago by
My implementation of link() uses matroid intersection just like in connectivity(), but now I've implemented that algorithm for class Matroid without the actual construction of the two minors, and I also wrote a bitpacked version in class BasisExchangeMatroid?.
I used this new function link() to speed up both connectivity() and _is_3connected_CE. Here's the effect on the latter function.
Before:
sage: M = Matroid(MatrixSpace(GF(2), 100,200).random_element()) sage: %time M._is_3connected_CE(True) CPU times: user 3min 10s, sys: 982 ms, total: 3min 11s Wall time: 3min 12s (True, None)
After:
sage: M = Matroid(MatrixSpace(GF(2), 100,200).random_element()) sage: %time M._is_3connected_CE(True) CPU times: user 1.12 s, sys: 1.68 ms, total: 1.12 s Wall time: 1.13 s (True, None)
Of course, this is still horrible compared to Chao's BC implementation.
sage: %time M._is_3connected_BC() CPU times: user 46.5 ms, sys: 1.14 ms, total: 47.6 ms Wall time: 50.8 ms True
But connectivity(S,T) also got 180x faster.
Will go on to tweak and test a bit. Meanwhile, if anyone has a strong opinion on the name link()
, discuss. It's easy to change it at this stage.
comment:4 Changed 6 years ago by
 Commit changed from 9acd9ebb43fbfe42eb22d5cd881056b80a50a020 to 79c955a5a023aa4aa36515e6dd75904d4794a5f6
Branch pushed to git repo; I updated commit sha1. New commits:
79c955a  Removed trailing whitespace

comment:5 Changed 6 years ago by
 Commit changed from 79c955a5a023aa4aa36515e6dd75904d4794a5f6 to ea42ccae7acd58dc145a1caf323216ff63ef473e
Branch pushed to git repo; I updated commit sha1. New commits:
ea42cca  Killed bug in _is_3connected_CE

comment:6 Changed 6 years ago by
 Commit changed from ea42ccae7acd58dc145a1caf323216ff63ef473e to 494f04a7c37a4d0682ec34feaee6127a514b44a1
Branch pushed to git repo; I updated commit sha1. New commits:
494f04a  ... and added one in the process

comment:7 Changed 6 years ago by
 Owner changed from (none) to Rudi
comment:8 Changed 6 years ago by
 Description modified (diff)
comment:9 Changed 6 years ago by
 Commit changed from 494f04a7c37a4d0682ec34feaee6127a514b44a1 to db0904de2adadfcf1209aefb458ff126c2f651b0
Branch pushed to git repo; I updated commit sha1. New commits:
db0904d  A heuristic optimization

comment:10 Changed 6 years ago by
 Commit changed from db0904de2adadfcf1209aefb458ff126c2f651b0 to 152e9241637a0bdb46c3c2f8597cdf48f3844370
Branch pushed to git repo; I updated commit sha1. New commits:
152e924  Killed a bug

comment:11 Changed 6 years ago by
 Commit changed from 152e9241637a0bdb46c3c2f8597cdf48f3844370 to 7205adde4a99952023a899aee6c336648c94b7d2
Branch pushed to git repo; I updated commit sha1. New commits:
7205add  Some optimizations

comment:12 followup: ↓ 13 Changed 6 years ago by
I see you fixed a bug in the 3connected code. Generally, the philosophy in Sage is one issue per ticket. Otherwise we're getting a mess of interdependent code.
comment:13 in reply to: ↑ 12 Changed 6 years ago by
Replying to Stefan:
I see you fixed a bug in the 3connected code. Generally, the philosophy in Sage is one issue per ticket. Otherwise we're getting a mess of interdependent code.
I could have opened another ticket, and I'm happy to do so if it has any advantages. But what would be the advantage here?
I started out using my new code to speed up an existing method, _is_3connected_CE. That by itself seems within the scope of this ticket. By doing so, I created dependency between this ticket and any other work on that method. So I'm not really making the mess worse by killing that bug, just solving a problem before it reaches the 6.8 release candidate. On the other hand, if I create a second ticket just for repairing the bug, then there will be two tickets interacting with _is_3connected_CE.
comment:14 Changed 6 years ago by
 Commit changed from 7205adde4a99952023a899aee6c336648c94b7d2 to 8ba307e4a5ac0ed982bbfdebbaebe92a326368c8
Branch pushed to git repo; I updated commit sha1. New commits:
8ba307e  More bugs

comment:15 Changed 6 years ago by
 Commit changed from 8ba307e4a5ac0ed982bbfdebbaebe92a326368c8 to b5cd8f1e72aefe116f81c938b6b2c99682f484c8
Branch pushed to git repo; I updated commit sha1. New commits:
b5cd8f1  Finishing touch docstrings

comment:16 Changed 6 years ago by
OK, trailing whitespace is gone, doctests run.
To test ._link() I verified that _is_3connected_CE agrees with _is_3connected_BC for all matroids on at most 9 elements.
I'll run some more tests tomorrow.
comment:17 Changed 6 years ago by
 Commit changed from b5cd8f1e72aefe116f81c938b6b2c99682f484c8 to 8ade550090c5b4e43f1683c74826aebe4abfb4ce
Branch pushed to git repo; I updated commit sha1. New commits:
8ade550  Explain steps in comments

comment:18 Changed 6 years ago by
 Status changed from new to needs_review
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 # Rank1 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.
comment:19 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hmm, the patchbot is half unhappy. Let me just merge with 6.8 beta 6.
comment:20 Changed 6 years ago by
 Commit changed from 8ade550090c5b4e43f1683c74826aebe4abfb4ce to 9df1cf15e77161940b29d3cbe75fb89f4f463223
Branch pushed to git repo; I updated commit sha1. New commits:
9df1cf1  Reduced number of calls to _link() in _is_3connected by factor 3

comment:21 Changed 6 years ago by
 Status changed from needs_work to needs_review
Well, I can't seem to merge or rebase on develop without going to an earlier version than beta6. Anyway, I realise now that rebasing won't help, that the one patchbot was unhappy about something unrelated to this ticket.
I did realise one more efficiency tweak which may actually help to speed up the test for kconnectedness as well. So have a look.
When _is_3connected_CE was based on matroid intersection it was quite a bit slower that _is_3connected_BC, now the picture is this:
sage: for i in range (10): M = Matroid(MatrixSpace(GF(2), i*10, i*20).random_element()) print i, M timeit("M._is_3connected_BC()") timeit("M._is_3connected_CE()") ....: 0 Binary matroid of rank 0 on 0 elements, type (0, 0) 625 loops, best of 3: 129 ns per loop 625 loops, best of 3: 147 ns per loop 1 Binary matroid of rank 10 on 20 elements, type (1, None) 625 loops, best of 3: 1.09 ms per loop 625 loops, best of 3: 704 µs per loop 2 Binary matroid of rank 20 on 40 elements, type (1, 1) 625 loops, best of 3: 1.38 ms per loop 125 loops, best of 3: 2.82 ms per loop 3 Binary matroid of rank 30 on 60 elements, type (1, 5) 125 loops, best of 3: 1.95 ms per loop 125 loops, best of 3: 6.57 ms per loop 4 Binary matroid of rank 40 on 80 elements, type (1, None) 125 loops, best of 3: 3.28 ms per loop 25 loops, best of 3: 13.8 ms per loop 5 Binary matroid of rank 50 on 100 elements, type (1, 3) 125 loops, best of 3: 5.09 ms per loop 25 loops, best of 3: 23.8 ms per loop 6 Binary matroid of rank 60 on 120 elements, type (0, 0) 125 loops, best of 3: 7.31 ms per loop 25 loops, best of 3: 39.3 ms per loop 7 Binary matroid of rank 70 on 140 elements, type (2, None) 25 loops, best of 3: 9.87 ms per loop 5 loops, best of 3: 61.5 ms per loop 8 Binary matroid of rank 80 on 160 elements, type (0, 6) 25 loops, best of 3: 12.7 ms per loop 5 loops, best of 3: 90.7 ms per loop 9 Binary matroid of rank 90 on 180 elements, type (0, 0) 25 loops, best of 3: 16.4 ms per loop 5 loops, best of 3: 122 ms per loop
So on a matroid on n elements, CE is about n/10 times slower than BC.
comment:22 Changed 6 years ago by
 Commit changed from 9df1cf15e77161940b29d3cbe75fb89f4f463223 to 9d932ee9b5e693b46fd7bfbd0da2ebb1d1bfdcc2
Branch pushed to git repo; I updated commit sha1. New commits:
9d932ee  Order of initial test in _is_3connected_CE was wrong

comment:23 Changed 6 years ago by
All tests pass. The code looks alright.
All 3connectivity 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(k1): return False m = k1 E = set(self.groundset()) w = {e:1 for e in E} Q = set(list(E)[:m]) E = EQ I = set() for r in range(len(Q)/2): for Q1 in map(set,combinations(Q, r)): Q2 = QQ1 for A in map(set,combinations(E, m  len(Q1))): T = Q1A for B in map(set,combinations(EA, m  len(Q2))): S = Q2B 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.
comment:24 followup: ↓ 25 Changed 6 years ago by
Hi Chao,
thanks for doing the review! If you have any comments, then I will still be able to respond in the next two weeks but after 26/7 I'll be travelling for a while.
Cheers, Rudi
comment:25 in reply to: ↑ 24 Changed 6 years ago by
 Reviewers set to Chao Xu
 Status changed from needs_review to positive_review
Hi Rudi,
Positive review.
Here are more things I have tried:
Some 4connected(and not 5connected) binary matroids given by Gordon Royle.
each list is a matroid and each number in the list expressed in binary is a column of a matrix representing the matroid.
[[1,2,4,7,8,11,13,14,16,21,25,31], [1,2,4,8,15,16,21,25,32,41,51,63], [1,2,4,8,15,16,21,22,32,41,42,51], [1,2,4,7,8,13,16,31,32,35,52,61], [1,2,4,8,15,16,32,54,64,90,109,113], [1,2,4,7,8,11,13,14,16,19,21,22,25,31], [1,2,4,8,15,16,21,25,30,32,37,41,44,51], [1,2,4,8,15,16,21,25,30,32,37,41,46,51], [1,2,4,8,15,16,21,25,30,32,37,41,51,52], [1,2,4,8,15,16,21,25,30,32,37,41,51,54], [1,2,4,8,15,16,21,27,28,32,39,41,51,56], [1,2,4,8,15,16,21,22,27,28,32,41,42,51], [1,2,4,8,15,16,21,22,27,32,39,41,42,51], [1,2,4,8,15,16,21,22,27,32,41,42,44,51], [1,2,4,8,15,16,21,22,32,41,42,51,61,62], [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31], [1,2,4,8,15,16,21,25,30,32,37,41,46,51,52,56], [1,2,4,8,15,16,21,25,30,32,37,41,46,51,54,56], [1,2,4,8,15,16,21,25,30,32,37,41,46,51,54,58], [1,2,4,8,15,16,21,27,28,32,39,41,44,51,52,56], [1,2,4,8,15,16,21,22,27,28,32,39,41,42,51,52], [1,2,4,8,15,16,21,22,27,28,32,39,41,42,44,51], [1,2,4,8,15,16,21,22,27,32,39,41,42,51,61,62], [1,2,4,7,8,11,13,14,16,19,22,31,32,35,52,61], [1,2,4,7,8,11,13,14,16,19,28,31,32,35,52,61]]
Applying is_kconnected(4)
and is_kconnecte(5)
returns desired results.
comment:26 Changed 6 years ago by
 Branch changed from u/Rudi/tutte_connectors_for_matroids to 9d932ee9b5e693b46fd7bfbd0da2ebb1d1bfdcc2
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Used _link to speed up _is_3connected_CE