Opened 2 years ago

Closed 23 months ago

#18784 closed enhancement (fixed)

Tutte connectors for matroids

Reported by: Rudi Owned by: Rudi
Priority: major Milestone: sage-6.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) Commit: 9d932ee9b5e693b46fd7bfbd0da2ebb1d1bfdcc2
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (26)

comment:1 Changed 2 years ago by Rudi

  • Branch set to u/Rudi/tutte_connectors_for_matroids

comment:2 Changed 2 years ago by git

  • Commit set to 9acd9ebb43fbfe42eb22d5cd881056b80a50a020

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

9acd9ebUsed _link to speed up _is_3connected_CE

comment:3 Changed 2 years ago by 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.

comment:4 Changed 2 years ago by git

  • Commit changed from 9acd9ebb43fbfe42eb22d5cd881056b80a50a020 to 79c955a5a023aa4aa36515e6dd75904d4794a5f6

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

79c955aRemoved trailing whitespace

comment:5 Changed 2 years ago by git

  • Commit changed from 79c955a5a023aa4aa36515e6dd75904d4794a5f6 to ea42ccae7acd58dc145a1caf323216ff63ef473e

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

ea42ccaKilled bug in _is_3connected_CE

comment:6 Changed 2 years ago by git

  • 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 2 years ago by Rudi

  • Authors set to Rudi Pendavingh
  • Owner changed from (none) to Rudi

comment:8 Changed 2 years ago by Rudi

  • Description modified (diff)

comment:9 Changed 2 years ago by git

  • Commit changed from 494f04a7c37a4d0682ec34feaee6127a514b44a1 to db0904de2adadfcf1209aefb458ff126c2f651b0

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

db0904dA heuristic optimization

comment:10 Changed 2 years ago by git

  • Commit changed from db0904de2adadfcf1209aefb458ff126c2f651b0 to 152e9241637a0bdb46c3c2f8597cdf48f3844370

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

152e924Killed a bug

comment:11 Changed 2 years ago by git

  • Commit changed from 152e9241637a0bdb46c3c2f8597cdf48f3844370 to 7205adde4a99952023a899aee6c336648c94b7d2

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

7205addSome optimizations

comment:12 follow-up: Changed 2 years ago by 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.

comment:13 in reply to: ↑ 12 Changed 2 years ago by 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.

comment:14 Changed 2 years ago by git

  • Commit changed from 7205adde4a99952023a899aee6c336648c94b7d2 to 8ba307e4a5ac0ed982bbfdebbaebe92a326368c8

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

8ba307eMore bugs

comment:15 Changed 2 years ago by git

  • Commit changed from 8ba307e4a5ac0ed982bbfdebbaebe92a326368c8 to b5cd8f1e72aefe116f81c938b6b2c99682f484c8

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

b5cd8f1Finishing touch docstrings

comment:16 Changed 2 years ago by 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.

comment:17 Changed 2 years ago by git

  • Commit changed from b5cd8f1e72aefe116f81c938b6b2c99682f484c8 to 8ade550090c5b4e43f1683c74826aebe4abfb4ce

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

8ade550Explain steps in comments

comment:18 Changed 2 years ago by Rudi

  • 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
    #  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.

comment:19 Changed 2 years ago by Rudi

  • 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 2 years ago by git

  • Commit changed from 8ade550090c5b4e43f1683c74826aebe4abfb4ce to 9df1cf15e77161940b29d3cbe75fb89f4f463223

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

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

comment:21 Changed 2 years ago by Rudi

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

comment:22 Changed 23 months ago by git

  • Commit changed from 9df1cf15e77161940b29d3cbe75fb89f4f463223 to 9d932ee9b5e693b46fd7bfbd0da2ebb1d1bfdcc2

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

9d932eeOrder of initial test in _is_3connected_CE was wrong

comment:23 Changed 23 months ago 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.

comment:24 follow-up: Changed 23 months ago by 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

comment:25 in reply to: ↑ 24 Changed 23 months ago by chaoxu

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

comment:26 Changed 23 months ago by vbraun

  • Branch changed from u/Rudi/tutte_connectors_for_matroids to 9d932ee9b5e693b46fd7bfbd0da2ebb1d1bfdcc2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.