Tutte connectors for matroids

[Rudi]

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(E-X)-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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9acd9eb

Used _link to speed up _is_3connected_CE

[Rudi]

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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​79c955a

Removed trailing whitespace

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ea42cca

Killed bug in _is_3connected_CE

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​494f04a

... and added one in the process

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​db0904d

A heuristic optimization

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​152e924

Killed a bug

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7205add

Some optimizations

[Stefan]

I see you fixed a bug in the 3-connected code. Generally, the philosophy in Sage is one issue per ticket. Otherwise we're getting a mess of interdependent code.

[Rudi]

Replying to Stefan:

I see you fixed a bug in the 3-connected 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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8ba307e

More bugs

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b5cd8f1

Finishing touch docstrings

[Rudi]

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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8ade550

Explain steps in comments

[Rudi]

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.

[Rudi]

Hmm, the patchbot is half unhappy. Let me just merge with 6.8 beta 6.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9df1cf1

Reduced number of calls to _link() in _is_3connected by factor 3

[Rudi]

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 k-connectedness 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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9d932ee

Order of initial test in _is_3connected_CE was wrong

[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.

[Rudi]

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

[chaoxu]

Hi Rudi,

Positive review.

Here are more things I have tried:

Some 4-connected(and not 5-connected) 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.