Opened 7 years ago

Closed 7 years ago

#18539 closed enhancement (fixed)

faster matroid 3 connectivity

Reported by: chaoxu Owned by: chaoxu
Priority: major Milestone: sage-6.8
Component: matroid theory Keywords:
Cc: Stefan, yomcat, Rudi Merged in:
Authors: Chao Xu Reviewers: Michael Welsh, Rudi Pendavingh
Report Upstream: N/A Work issues:
Branch: 482ce85 (Commits, GitHub, GitLab) Commit: 482ce8545892fa4dd927cbe34243456550e89827
Dependencies: 18448 Stopgaps:

Status badges

Description (last modified by chaoxu)

Implement the efficient 3 connectivity algorithm.

  1. E. Bixby, W. H. Cunningham, Matroids, Graphs, and 3-Connectivity. In Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, ON, 1977), 91-103

Attachments (1)

matroids9_low_rank.sobj (1.3 MB) - added by Rudi 7 years ago.
all matroids on n<= 9 elements with rank <= n/2

Download all attachments as: .zip

Change History (56)

comment:1 Changed 7 years ago by chaoxu

  • Branch set to u/chaoxu/faster_matroid_3_connectivity

comment:2 Changed 7 years ago by chaoxu

  • Cc Stefan added
  • Commit set to c4f38ebbc6b4ec4e3df38580d3f4971239a8697f
  • Component changed from PLEASE CHANGE to matroid theory
  • Description modified (diff)
  • Owner changed from (none) to chaoxu
  • Type changed from PLEASE CHANGE to enhancement

New commits:

c4f38ebbasic algorithm framework for further modification

comment:3 Changed 7 years ago by chaoxu

  • Cc yomcat added

comment:4 Changed 7 years ago by git

  • Commit changed from c4f38ebbc6b4ec4e3df38580d3f4971239a8697f to 5167f3d06289e4d43e865304e288798874d8f561

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

5167f3dremove excess code from copy & paste

comment:5 Changed 7 years ago by Rudi

  • Cc Rudi added

comment:6 Changed 7 years ago by git

  • Commit changed from 5167f3d06289e4d43e865304e288798874d8f561 to 313de5d24b0a44930f8ef6eefd47c269a01b9816

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

f9c59fcMerge branch 'develop' into t/18539/faster_matroid_3_connectivity
313de5dintermediate code, seems to be a correct implementation

comment:7 Changed 7 years ago by git

  • Commit changed from 313de5d24b0a44930f8ef6eefd47c269a01b9816 to 23cfab190acc6e26bd0bc20276e028438964ea95

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

23cfab1complete special cases in stage 0

comment:8 follow-up: Changed 7 years ago by chaoxu

Running the following code shows the new implementation matches the current behavior on named matroids.

def test(M): 
	return M.is_3connected_beta()==M.is_3connected()
results = []
for M in matroids.named_matroids.__dict__.values():
    if callable(M):
        results.append(test(M()))
all(results)

I will generate some larger examples to test the running time and start optimizing.

For the base case, I need to access Uniform(r,n). A direct import seems to cause circular dependency. If I use

from sage.matroids.catalog import Uniform
# some code that calls Uniform(r,n)

then the error ImportError: cannot import name Uniform appears during runtime. Somehow using from sage.matroids.catalog import * and write sage.matroids.catalog.Uniform(r,n) for every call works out. I wonder if there are better ways.

comment:9 in reply to: ↑ 8 Changed 7 years ago by Rudi

Replying to chaoxu:

For the base case, I need to access Uniform(r,n). A direct import seems to cause circular dependency. If I use

from sage.matroids.catalog import Uniform
# some code that calls Uniform(r,n)

then the error ImportError: cannot import name Uniform appears during runtime. Somehow using from sage.matroids.catalog import * and write sage.matroids.catalog.Uniform(r,n) for every call works out. I wonder if there are better ways.

A matroid of rank 1 is uniform if and only if it has no loops, and dually a matroid of corank 1 is uniform iff it has no coloops. So you could also replace your test

     if (self.size() <= 1 or
            self.is_isomorphic(sage.matroids.catalog.Uniform(1,2)) or
            self.is_isomorphic(sage.matroids.catalog.Uniform(1,3)) or
            self.is_isomorphic(sage.matroids.catalog.Uniform(2,3))):
            return True

with this simpler one

     if self.size() <= 1:
            return True
     if self.size() <= 3 and self.full_rank()==1 and not self.loops():
            return True
     if self.size() <= 3 and self.full_corank()==1 and not self.coloops():
            return True

comment:10 Changed 7 years ago by Stefan

While I agree that Rudi's method is better (isomorphism testing is VERY expensive), let's look at the import issue too. Was your import inside the method instead of global? You might want to look at the way it was done in, for instance, the _minor method in matroid.pyx. I think you can't do it better than that.

comment:11 Changed 7 years ago by git

  • Commit changed from 23cfab190acc6e26bd0bc20276e028438964ea95 to 0033334e6a0795d4e6033ac4721f3a8f432e7b55

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

0033334Optimization: Clever choice of basis and fundamental cocircuits.

comment:12 follow-up: Changed 7 years ago by chaoxu

Thanks Rudi, I have incorporated your suggestions. It's much faster now.

One can use the following code to test the running time of the current implementation and the original one.

def bench(beta=False):
	for M in matroids.named_matroids.__dict__.values():
  		if callable(M):
  			if beta:
				M().is_3connected_beta()
			else:
				M().is_3connected()
sage: %time bench(False)
CPU times: user 298 ms, sys: 10.5 ms, total: 309 ms
Wall time: 301 ms
sage: %time bench(True)
CPU times: user 36.9 ms, sys: 1.83 ms, total: 38.8 ms
Wall time: 37.5 ms

I also benchmarked on 3-connected binary matroids listed here. The old algorithm takes 925 ms, the new one takes 51 ms.

For correctness, I will try to see if the original and the new implementation agrees for all matroids with at most 9 elements. (data from Database of Matroids).

Changed 7 years ago by Rudi

all matroids on n<= 9 elements with rank <= n/2

comment:13 in reply to: ↑ 12 Changed 7 years ago by Rudi

Replying to chaoxu:

One can use the following code to test the running time of the current implementation and the original one.

sage: %time bench(False)
CPU times: user 298 ms, sys: 10.5 ms, total: 309 ms
Wall time: 301 ms
sage: %time bench(True)
CPU times: user 36.9 ms, sys: 1.83 ms, total: 38.8 ms
Wall time: 37.5 ms

I also benchmarked on 3-connected binary matroids listed here. The old algorithm takes 925 ms, the new one takes 51 ms.

That really is very nice work. Cheers!

What part of your code is currently using most of the time on these test cases?

For correctness, I will try to see if the original and the new implementation agrees for all matroids with at most 9 elements. (data from Database of Matroids).

I have attached the set of matroids on at most 9 elements, perhaps that will save you some time translating their data. If you want I can also send the Sage code I used to generate these matroids, just let me know.

comment:14 Changed 7 years ago by git

  • Commit changed from 0033334e6a0795d4e6033ac4721f3a8f432e7b55 to e4917ce7de458b357ab1471c3a9b2b68ac377539

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

e4917cefix bug.

comment:15 Changed 7 years ago by git

  • Commit changed from e4917ce7de458b357ab1471c3a9b2b68ac377539 to 84a81fdefe60c488faf9e4610c170c985e0c5f2f

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

84a81fdreduce number of candidate cocircuits

comment:16 follow-up: Changed 7 years ago by chaoxu

Replying to Rudi:

I have attached the set of matroids on at most 9 elements, perhaps that will save you some time translating their data.

Thanks, that's really helpful. I found a bug and now it have been fixed. Now it works for all test cases. I'm pretty convinced of the correctness.

What part of your code is currently using most of the time on these test cases?

For the named cases, _corank and minor operation taking the most of the time. For the small 3 connected binary matroids, most time was spent on is_circuit, is_cosimple, is_simple. For matroids with large rank (I generated a random rank 500 binary matroid), components take the most time. Here is an time breakdown for a rank 500 binary matroid.

         136529 function calls in 18.426 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      501    6.947    0.014   11.109    0.022 matroid.pyx:4477(components)
   125515    4.162    0.000    4.162    0.000 matroid.pyx:1351(circuit)
        1    3.968    3.968    3.968    3.968 matroid.pyx:4441(is_cosimple)
      500    3.216    0.006    3.246    0.006 matroid.pyx:3438(minor)
        1    0.027    0.027   14.356   14.356 matroid.pyx:4807(_is_3connected_beta)
     1000    0.026    0.000    0.044    0.000 matroid.pyx:1772(fundamental_cocircuit)
        1    0.026    0.026    0.026    0.026 matroid.pyx:4408(is_simple)
     1000    0.014    0.000    0.014    0.000 matroid.pyx:820(_is_basis)
      500    0.013    0.000    0.013    0.000 {method '_max_coindependent' of 'sage.matroids.basis_exchange_matroid.BasisExchangeMatroid' objects}
      500    0.005    0.000    0.030    0.000 utilities.py:184(sanitize_contractions_deletions)
        1    0.005    0.005    0.005    0.005 matroid.pyx:2040(coloops)
      500    0.005    0.000    0.005    0.000 {method '_max_independent' of 'sage.matroids.basis_exchange_matroid.BasisExchangeMatroid' objects}
     1000    0.003    0.000    0.017    0.000 matroid.pyx:1887(is_basis)
     1000    0.003    0.000    0.003    0.000 {method 'issuperset' of 'frozenset' objects}
     1000    0.002    0.000    0.002    0.000 {method 'difference' of 'frozenset' objects}
     1000    0.002    0.000    0.002    0.000 {method 'union' of 'frozenset' objects}
      500    0.001    0.000    3.248    0.006 matroid.pyx:3631(delete)
      500    0.000    0.000   11.060    0.022 matroid.pyx:4518(is_connected)
      500    0.000    0.000    0.000    0.000 {method 'isdisjoint' of 'frozenset' objects}
     1000    0.000    0.000    0.000    0.000 {method 'groundset' of 'sage.matroids.basis_exchange_matroid.BasisExchangeMatroid' objects}
        1    0.000    0.000    0.000    0.000 matroid.pyx:1811(loops)
        1    0.000    0.000   18.431   18.431 <string>:1(<module>)
        1    0.000    0.000   18.431   18.431 {method 'is_3connected_beta' of 'sage.matroids.matroid.Matroid' objects}
        1    0.000    0.000   18.431   18.431 matroid.pyx:4740(is_3connected_beta)
        3    0.000    0.000    0.000    0.000 matroid.pyx:1216(size)
        1    0.000    0.000    0.000    0.000 matroid.pyx:1236(rank)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

I will get it to return a separator and write some docs for the next update.

comment:17 in reply to: ↑ 16 Changed 7 years ago by Rudi

Replying to chaoxu:

What part of your code is currently using most of the time on these test cases?

For the named cases, _corank and minor operation taking the most of the time. For the small 3 connected binary matroids, most time was spent on is_circuit, is_cosimple, is_simple. For matroids with large rank (I generated a random rank 500 binary matroid), components take the most time. Here is an time breakdown for a rank 500 binary matroid.

Thanks for sending that data. The many calls to circuits() are probably happening in the Matroids.components() routine. I think I may have written that routine, and looks as if I did not really optimize it for speed.

  • the method calls .circuit() in it's innermost loop, and then the use of _circuit() is preferred. The underscored versions of Matroid methods do the same as the original, but without the sanity checking of the input (in this case, testing if the input is a set of elements from the ground set).
  • circuit() is used to get a fundamental circuit, and I think we later created that optimized method for that: fundamental_circuit

So the following tweaks to components() may make a difference.

        B = self.basis()
        components = []
        for e in self.groundset() - B:
            C = set(self._fundamental_cocircuit(B,e))
            components2 = []
            for comp in components:
                if (C & comp):
                    C.update(comp)
                else:
                    components2.append(comp)
            components2.append(frozenset(C))
            components = components2
        components.extend([frozenset([e]) for e in self.loops()])
        return components

You could also consider rewriting a bit more, use the above when r(M) <= r^*(M) and the dual version (circuits) in the other case. That way the inner loop always has the least number of iterations. And if this routine really stays a bottleneck, a bitpacked version is always an option.

Since your routine is_3connected_beta also computes fundamental cocircuits, you would also gain a bit by using the unguarded _fundamental_cocircuit. It is perhaps wasteful to compute those fundamental cocircuits again in components and indirectly, in is_connected. You could consider rewriting these routines so that they take a set of fundamental circuits and/or a set of fundamental cociruits as input. Note that if Y is a fundamental cocircuit as in step 2, then the fundamental cocircuits of self.delete(Y) are obtained by deleting Y from the other fundamental cocircuits of self. So you could even avoid creating self.delete(Y) in step 2.

It is very, very strange indeed that a single call to is_cosimple takes that much time. I cannot explain how it can take any more time than is_simple. I'll look into it.

A quicker method to create the parallel class of e is:

parallel_class = M._closure([e])

The minor-taking/deletion is also expensive in your method. Improving the inefficiency of minor itself is probably more involved, and this would really deserve it's own ticket. It may be possible to reduce the number of times you construct a minor, e.g. by testing the rank of the minor before actually constructing it.

Last edited 7 years ago by Rudi (previous) (diff)

comment:18 follow-up: Changed 7 years ago by Rudi

Hi Chao,

somehow the inefficiency of components() became a major earworm for me today, so I coded a more efficient version for BasisExchangeMatroid? (ticket #18591) to get it out of my system. The real inefficiency turned out to be in the set union operations, and calculating with bitsets rather than python sets works miracles for that.

I also felt a bit bad for luring you into my bad habits of premature code optimization, but by just using my patch you can stay focussed on testing correctness and enhancing functionality, which is probably better.

I realized why is_cosimple() is that much slower than is_simple() for BinaryMatroids? (and Ternary and Quaternary). There is a specialized ultra fast method to get a fundamental cocircuit for such matroids, essentially copying the row of a bitpacked matrix (which is a bitset) into another bitset, which is the internal representation of the cocircuit. For circuits you are back to touching each of the groundset elements one by one, which is way slower. This asymmetry makes closure() faster that coclosure, and in turn is_simple faster than is_cosimple. I still need to see what is a clean way to solve that.

Rudi

comment:19 in reply to: ↑ 18 ; follow-up: Changed 7 years ago by chaoxu

Replying to Rudi:

The real inefficiency turned out to be in the set union operations, and calculating with bitsets rather than python sets works miracles for that.

Great. Thanks I will review that code soon. What is the abstract way to find components from a set of fundamental cocircuits? This code didn't return the same output as the original components.

       B = self.basis()
        components = []
        for e in self.groundset() - B:
            C = set(self._fundamental_cocircuit(B,e))
            components2 = []
            for comp in components:
                if (C & comp):
                    C.update(comp)
                else:
                    components2.append(comp)
            components2.append(frozenset(C))
            components = components2
        components.extend([frozenset([e]) for e in self.loops()])
        return components

comment:20 in reply to: ↑ 19 Changed 7 years ago by Rudi

Replying to chaoxu:

This code didn't return the same output as the original components.

It should be:

           for e in B:
           C = set(self._fundamental_cocircuit(B,e))

or

           for e in self.groundset() - B:
           C = set(self._fundamental_circuit(B,e))

I mixed them up.

What is the abstract way to find components from a set of fundamental cocircuits?

Consider the hypergraph H whose ground set is E(M) and whose edges are the fundamental cocircuits of M relative to a fixed basis B. Then the components of H are the components of M.

Last edited 7 years ago by Rudi (previous) (diff)

comment:21 Changed 7 years ago by Rudi

Hi Chao,

I have reduced the amount of time spent on is_cosimple() as well, see ticket #18605. Together with the patch for components() this leaves minor() as the main bottleneck. Not so sure if I can make that one much more efficient.

Looking at the effect of my patches on various types of matroids I ran into a bug. Try this:

sage: M=Matroid(graphs.RandomRegular(3,200))
sage: M.is_3connected_beta()

It's random, but nearly always results in a error.

comment:22 Changed 7 years ago by Rudi

Hi Chao,

there is an import from sage.matroids.catalog import * in your matroid.pyx which causes errors and breaks the doctest (my guess is this is probably due to circular imports). You don't seem to need this import anymore since you stopped checking isomorphism with uniform matroids, so perhaps it is best if you remove this line.

Cheers, Rudi

comment:23 Changed 7 years ago by Rudi

Hi Chao,

I worked a bit on _minor(), a patch is in ticket #18660. Together with #18638 and #18605 that will probably take the time needed to solve your 500x1000 binary matroid to below 1 second.

It should be possible to make your method another ~5x faster, seeing that essentially all the work is happening in Step 2. It is possible to eliminate all the minor-taking from that part of your method. The set of fundamental circuits by itself is enough to detect that disconnecting cocircuit, and so a routine which solves that problem using bitpacked fundamental cocircuits could do all that in about the time now spent on components(). I will perhaps write such a specialised routine once your code is in final form, in a follow-up ticket.

Cheers, Rudi

comment:24 follow-up: Changed 7 years ago by chaoxu

Hi Rudi,

This is great news, I will take a look.

We could create a function that finds the components of a hypergraph given the edges. Then both components() and the code in Step 2 can just call that function.

comment:25 in reply to: ↑ 24 Changed 7 years ago by Rudi

Replying to chaoxu:

We could create a function that finds the components of a hypergraph given the edges. Then both components() and the code in Step 2 can just call that function.

That is true, and it would not be that much work either to make such a more elementary function for SetSystem?. But I'm afraid that just filling these hypergraphs with python sets may become the bottleneck. But maybe if I also write a routine for SetSystem? to delete a fixed subset from all subsets in the system.

I'll whip something up.

comment:26 Changed 7 years ago by Rudi

I wrote .is_connected() for SetSystem? here #18682, and it seems to work, have look. But looking at the timings just this one command may not be enough for what you need. The connectivity routine is fast enough, but filling the SetSystems? may not be. Or maybe you can experiment with it a bit.

If not enough, what exactly would suffice for your purposes? A method component(e) (to compute the component containing e) and a method to restrict all subsets to a given subset?

Last edited 7 years ago by Rudi (previous) (diff)

comment:27 Changed 7 years ago by chaoxu

It's fairly strange that filling in the SetSystem? takes that long... I will check if it can be optimized.

If not enough, what exactly would suffice for your purposes? A method component(e) (to compute the component containing e) and a method to restrict all subsets to a given subset?

Yes. But instead of component(e), components() is enough, since we have to iterate over all components if it's not connected.

comment:28 Changed 7 years ago by git

  • Commit changed from 84a81fdefe60c488faf9e4610c170c985e0c5f2f to eca042a03f89753c1254d982e0dd663ec7d1b686

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

43fcbbfcleaner logic
c03e0f5Replaced the old 3 connectivity with new 3 connectivity algorithm.
eca042afix import

comment:29 Changed 7 years ago by chaoxu

  • Status changed from new to needs_review

This is the completed code for bridge based 3-connectivity algorithm.

It doesn't return a separator. (The ticket:18687 will implement an alternative algorithm that returns a separator).

comment:30 Changed 7 years ago by Rudi

Hi Chao,

I don't think I should be reviewing your code since Stefan is your mentor on the gsoc project, but I can help a little.

So I tested your code to see if it would detect a separation if it exist, using the following:

def binary_matroid_with_2_separation(r,n):
    A=MatrixSpace(GF(2),r,n).random_element()
    s = ZZ.random_element(2,r-3)
    m = ZZ.random_element(2,n-2)
    for i in range(s+1, r):
        for j in range(m):
            A[i,j] =0
    for i in range(s):
        for j in range(m, n):
            A[i,j] =0        
    return Matroid(A)

and

for i in range(10000):
    r=ZZ.random_element(6,20)
    n=ZZ.random_element(r+6, 5*r)
    M = binary_matroid_with_2_separation(20,50)
    if M.is_3connected():
        print M
        break

Your code seems to withstand such testing all the time.

Cheers, Rudi

comment:31 follow-up: Changed 7 years ago by Stefan

  • Authors set to Chao Xu
  • Status changed from needs_review to needs_work

Rudi, feel free to review any GSoC tickets.

FWIW, here's a slightly more generic test where the 2-separation is a truly random partition:

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()

which I ran a bunch of times:

%time
for n in range(10,20):
    for m in range(15,25):
        for k in range(1000):
            if test_3c(n,m):
                print "Whoops"
print "ok"

Took under 36 seconds on my laptop.

Now, for the review of this ticket.

  • You removed the optional argument to is_3connected. When I told you not to implement it at this point, I didn't realize the argument was already there. For now, I would say you have a second helper method (something like _is_3connected_naive) that does the old, brute-force thing. You can't just remove functionality from Sage without a deprecation period.
  • Every method, even the hidden ones, needs an EXAMPLES:: section for testing purposes. The code snippets in that section are run and compared against the provided output for every new release of Sage. This ensures everything keeps working as it should. You can run those tests with ./sage -t src/sage/matroids/*.py* from the Sage home directory. You can test if your code satisfies the requirements by running ./sage -coverage src/sage/matroids/*.py*
  • The helper function does not need a "SEEALSO" section, but it DOES need an explicit description of assumptions on the instances for which it is invoked (simple, at least 4 elements, etc.)
  • The comment in line 4727 is confusing
  • In line 4730, why do you make a copy?
  • Maybe name the helper function _is_3connected_BC to indicate which algorithm it implements? That way, we can also have an _is_3connected_shifting version.

Apart from that, the code looks clean. If you make these changes, it can get a positive review.

comment:32 in reply to: ↑ 31 ; follow-ups: Changed 7 years ago by yomcat

Replying to Stefan:

  • Maybe name the helper function _is_3connected_BC to indicate which algorithm it implements? That way, we can also have an _is_3connected_shifting version.

Is this the best way to implement it? Would an optional argument algorithm='??' (that defaults to whichever algorithm ends up being faster) work better?

comment:33 in reply to: ↑ 32 Changed 7 years ago by Rudi

Replying to yomcat:

Would an optional argument algorithm='??' (that defaults to whichever algorithm ends up being faster) work better?

I think such an optional argument would be best. So you would have

is_3connected(certify = False, algorithm = None)

and helper functions

_is_3_connected_BC(certify = False), your new algorithm, throwing NotImplemented? when certify =True _is_3_connected_CE(certify = False), the algorithm using matroid intersection you removed (Cunningham - Edmonds?)

comment:34 in reply to: ↑ 32 Changed 7 years ago by Stefan

Replying to yomcat:

Replying to Stefan:

  • Maybe name the helper function _is_3connected_BC to indicate which algorithm it implements? That way, we can also have an _is_3connected_shifting version.

Is this the best way to implement it? Would an optional argument algorithm='??' (that defaults to whichever algorithm ends up being faster) work better?

The public-facing function would work like you describe, and call one of the private ones either using an internal decision process, or using the algorithm argument. A separate method for each algorithm allows you to do things like recursion (in this case relevant). So I guess we are all on the same page.

comment:35 Changed 7 years ago by Stefan

The standard name for the certifying argument in the Graph methods is "certificate", which I'd use as an alternate to the "separation" argument. So the signature would be

cpdef is_3connected(self, certificate=False, algorithm=None, separation=False):

where you start with

certificate = certificate or separation, and put in a deprecation warning when the "separation" argument is set to True.

comment:36 Changed 7 years ago by git

  • Commit changed from eca042a03f89753c1254d982e0dd663ec7d1b686 to b7cfd150951bcc47534682cf63f53eeb930dea5e

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

b7cfd15incorporate review comments, improve test coverage

comment:37 Changed 7 years ago by chaoxu

  • Status changed from needs_work to needs_review

I have made the suggested changes.

comment:38 Changed 7 years ago by yomcat

  • Status changed from needs_review to needs_work

Rudi changed the naive algorithm in #18429 (which I missed) to one based on matroid intersection. You should update names and docstrings to reflect that.

I also think (but am happy to be overruled) that something like this is more appropriate:

``None`` -- The most appropriate algorithm is chosen automatically.
+          - ``"bridges"`` -- Bixby and Cunningham's algorithm, based on bridges [BC79]_. Note that this cannot return a separator.
+          - ``"intersection"`` An algorithm based on matroid intersection.

comment:39 Changed 7 years ago by git

  • Commit changed from b7cfd150951bcc47534682cf63f53eeb930dea5e to 6a3484d37844b63bc30da968e58bc2ccf8836486

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

6a3484dupdate names and doc string

comment:40 Changed 7 years ago by chaoxu

  • Status changed from needs_work to needs_review

Good point. updated.

comment:41 Changed 7 years ago by yomcat

  • Reviewers set to Michael Welsh

I'm happy with it now. I'll wait for Stefan/Rudi? to give the final sign off. And patchbot should get involved.

comment:42 Changed 7 years ago by Rudi

Hi Chao,

I think the code as such looks great and works great. Repair these last few issues and I'll give a positive review:

The docstring of is_3connected only mentions BC under ..ALGORITHM:. Please also describe the other method.

When _is_3connected_BC throws NotImplementedError, give a description of the problem , e.g. NotImplementedError?("The Bixby-Cunningham algorithm does not return a separation")

In the docstring of _is_3connected_CE and _is_3connected_BC, there are several X and one T that need to have single accolades (now double). You can check the appearance of the docstring in the notebook by entering M._is_3connected_BC? on a matroid M.

Finally, I don't believe keeping&depricating the option separation is necessary in this case. This option was introduced in 6.8 beta and so never saw an official release. So if we make sure it's gone before 6.8 is released we should be fine.

If the others agree you can perhaps still change this. Otherwise I'll give the positive review after you settled the above 3 issues.

comment:43 Changed 7 years ago by git

  • Commit changed from 6a3484d37844b63bc30da968e58bc2ccf8836486 to 183b216c277b0efde6da3bf914e47b104e340a9e

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

183b216updated docs

comment:44 Changed 7 years ago by Rudi

  • Reviewers changed from Michael Welsh to Michael Welsh, Rudi Pendavingh
Error building the documentation.
Traceback (most recent call last):
  File "/Users/rudi/Documents/Development/sage-6.7/src/doc/common/builder.py", line 1626, in <module>
    getattr(get_builder(name), type)()
  File "/Users/rudi/Documents/Development/sage-6.7/src/doc/common/builder.py", line 292, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/Users/rudi/Documents/Development/sage-6.7/src/doc/common/builder.py", line 503, in _wrapper
    x.get(99999)
  File "/Users/rudi/Documents/Development/sage-6.7/local/lib/python/multiprocessing/pool.py", line 558, in get
    raise self._value
OSError: [matroids ] docstring of sage.matroids.matroid.Matroid.is_3connected:33: WARNING: Bullet list ends without a blank line; unexpected unindent.

comment:45 Changed 7 years ago by git

  • Commit changed from 183b216c277b0efde6da3bf914e47b104e340a9e to 23724761865a2107bae93a220680ca186ec4462d

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

2372476indent problem

comment:46 Changed 7 years ago by Rudi

  • Status changed from needs_review to positive_review

Code compiles, tests succeed, docs build.

Positive review!

comment:47 Changed 7 years ago by vbraun

merge conflict, probably #18448

comment:48 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

comment:49 Changed 7 years ago by git

  • Commit changed from 23724761865a2107bae93a220680ca186ec4462d to 34be00b7a1f4a0ffd0770fdf7734b995e3865f40

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

34be00bMerge branch 'develop' into t/18539/faster_matroid_3_connectivity

comment:50 Changed 7 years ago by chaoxu

What can I do at this point to resolve the merge conflict?

comment:51 Changed 7 years ago by Rudi

Hi Chao,

I am also still learning git so perhaps I'm not the right person to give expert advice. But take a look at the way a merge conflict is resolved in this recent ticket #17492. The way to go seems to be to merge the conflicting ticket #18448 into your code. You can do so by a git trac pull 18448 while working on your ticket (this is destructive so if you want to be safe, perform a merge of the two patches in a separate branch). The automatic merge will partially fail and you have to repair some of the source (probably matroid.pyx). Places where the automerger could not decide what to do will be indicated in the source with <<< and >>>.

I doubt that the manual merge will be very difficult in this case, the issue is probably that the new code in both tickets are more or less in the same location. If you want, I will attempt the merge for you.

Just merging develop into your branch as you just did may not suffice, since 18448 is not yet part of develop.

Cheers, Rudi

comment:52 Changed 7 years ago by git

  • Commit changed from 34be00b7a1f4a0ffd0770fdf7734b995e3865f40 to 482ce8545892fa4dd927cbe34243456550e89827

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

edaf4c7Improved docstrings, added .is_binary() for BinaryMatroid and RegularMatroid
7ad1f5bDocstring improvements
503b1e7Finishing touch docstrings
63767a1One more ALGORITHM block
8967234Fixed latex in docstring
29e84daMerge branch 'u/Rudi/add_test_if_a_matroid_is_binary' of trac.sagemath.org:sage into u/Rudi/add_test_if_a_matroid_is_binary
ada6742Some changes, tweaks, and made a method public.
b9c3268Added method .binary_matroid() for Matroid, BinaryMatroid, RegularMatroid
fab68ccdeleted a white space that messed up unindent in docs
482ce85Merge branch 'u/Rudi/binary_matroid-18448' of git://git.sagemath.org/sage into t/18539/faster_matroid_3_connectivity

comment:53 Changed 7 years ago by chaoxu

  • Status changed from needs_work to needs_review

Thanks Rudi, I followed your steps. Hopefully this solves all the conflicts.

comment:54 Changed 7 years ago by Rudi

  • Dependencies set to 18448
  • Status changed from needs_review to positive_review

Yes, that should do it. Positive review again.

comment:55 Changed 7 years ago by vbraun

  • Branch changed from u/chaoxu/faster_matroid_3_connectivity to 482ce8545892fa4dd927cbe34243456550e89827
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.