Opened 6 years ago

Closed 6 years ago

#18429 closed enhancement (fixed)

Add the matroid connectivity function

Reported by: Rudi Owned by: Rudi
Priority: major Milestone: sage-6.8
Component: matroid theory Keywords:
Cc: Stefan, chaoxu Merged in:
Authors: Rudi Pendavingh Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 9b55e71 (Commits, GitHub, GitLab) Commit: 9b55e71cbde687f3385ef19f98abc188ccc7362c
Dependencies: Stopgaps:

Status badges

Description (last modified by Rudi)

There is a simple reduction from matroid connectivity to matroid intersection. Implement the connectivity function using this reduction. Use the connectivity function to improve the efficiency of is_3connected, which currently has a naive implementation.

Attachments (2)

matroid.pxd (4.7 KB) - added by Rudi 6 years ago.
matroid.pyx (175.3 KB) - added by Rudi 6 years ago.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 6 years ago by Rudi

  • Branch set to u/Rudi/add_the_matroid_connectivity_function

comment:2 Changed 6 years ago by git

  • Commit set to 2b9bd7511108a7df8390df66ba3ee82403cc6cd8

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

2b9bd75Added function definitions.

comment:3 Changed 6 years ago by git

  • Commit changed from 2b9bd7511108a7df8390df66ba3ee82403cc6cd8 to 9a57d0bfd530ac5a4d08ee33e662c932caca9200

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

9a57d0bLess is more

comment:4 Changed 6 years ago by git

  • Commit changed from 9a57d0bfd530ac5a4d08ee33e662c932caca9200 to be12041abe8c38fa2835050f6479b89bfefa5044

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

be12041Finishing touch

comment:5 Changed 6 years ago by git

  • Commit changed from be12041abe8c38fa2835050f6479b89bfefa5044 to e935dc2d1d62cf2280bc85a0c7ea2cf5d2370923

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

e935dc2Done

comment:6 Changed 6 years ago by Rudi

  • Description modified (diff)
  • Status changed from new to needs_review

comment:7 Changed 6 years ago by git

  • Commit changed from e935dc2d1d62cf2280bc85a0c7ea2cf5d2370923 to 6929d5e33cd39c42f2187ed18b9c69683a918bc3

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

6929d5eSome further speedups

Changed 6 years ago by Rudi

Changed 6 years ago by Rudi

comment:8 Changed 6 years ago by Rudi

  • Status changed from needs_review to needs_work

Finally my sage installation is back on it's feet again.

Now that I can properly test my own work I see that this patch still needs some work, so I'll upload my improved version later.

Sorry for the mess.

comment:9 Changed 6 years ago by git

  • Commit changed from 6929d5e33cd39c42f2187ed18b9c69683a918bc3 to 5635654a4bf39acbb5cbad2219526b3c4493fde4

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

5635654Killed the last bug and tweaked BinaryMatroid._minor() for better efficiency

comment:10 Changed 6 years ago by Rudi

  • Status changed from needs_work to needs_review

Happy now.

comment:11 Changed 6 years ago by git

  • Commit changed from 5635654a4bf39acbb5cbad2219526b3c4493fde4 to 01e11cd06efd516f8f5cb90562f24076f0cbcfaa

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

e29cbe1_intersection_augmentation efficiency tweak
01e11cdMatroid.is_3connected() can now provide a separation to certify non-3-connectedness

comment:12 Changed 6 years ago by git

  • Commit changed from 01e11cd06efd516f8f5cb90562f24076f0cbcfaa to 7d59d68674efb0dea16e28169e70687c9e860208

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

7d59d68One more bug

comment:13 Changed 6 years ago by Rudi

I could not resist adding functionality to is_3connected, namely returning a separation to certify that the matroid is nor 3-connected. This did involve slightly altering the interface to the matroid intersection augmentation routine, to return the corresponding dual solution of a max-cardinality problem.

comment:14 Changed 6 years ago by Rudi

  • Milestone changed from sage-6.7 to sage-6.8

comment:15 Changed 6 years ago by Rudi

  • Cc chaoxu added
  • Owner changed from (none) to Rudi

comment:16 Changed 6 years ago by git

  • Commit changed from 7d59d68674efb0dea16e28169e70687c9e860208 to 402fdf71b37a6753076be4ccf8a157667694b75d

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

402fdf7Killed a doctest bug

comment:17 follow-up: Changed 6 years ago by tscrim

  • Branch changed from u/Rudi/add_the_matroid_connectivity_function to public/matroid/add_matroid_connectivity-18429
  • Commit changed from 402fdf71b37a6753076be4ccf8a157667694b75d to 9b55e71cbde687f3385ef19f98abc188ccc7362c
  • Reviewers set to Travis Scrimshaw

Do you have some timings between the current version and your proposed version of is_3connected? Also should we just change this to a method is_k_connected, as I think all we'd need to change is < 2 to < k-1?


New commits:

aa453e7Merge branch 'do_not_checkout' into public/matroid/add_matroid_connectivity-18429
9b55e71Reviewer changes to docstring formatting and trailing whitespace.

comment:18 in reply to: ↑ 17 Changed 6 years ago by Rudi

Replying to tscrim:

Do you have some timings between the current version and your proposed version of is_3connected?

With the current version:

sage: M= matroids.named_matroids.T12()
sage: timeit("M.is_3connected()")
5 loops, best of 3: 91.4 ms per loop
sage: N= matroids.named_matroids.Terrahawk()
sage: timeit("N.is_3connected()")
5 loops, best of 3: 1.4 s per loop
sage: K=matroids.CompleteGraphic(7)
sage: timeit("K.is_3connected()")
5 loops, best of 3: 52.7 s per loop

With the proposed one:

sage: M=matroids.named_matroids.T12()
sage: timeit("M.is_3connected()")
125 loops, best of 3: 8.12 ms per loop
sage: N=matroids.named_matroids.Terrahawk()
sage: timeit("N.is_3connected()")
25 loops, best of 3: 20.7 ms per loop
sage: K=matroids.CompleteGraphic(7)
sage: timeit("K.is_3connected()")
5 loops, best of 3: 46.9 ms per loop

M has 12 elements, N has 16 elements, K has 21 elements.

Also should we just change this to a method is_k_connected, as I think all we'd need to change is < 2 to < k-1?

It's a bit more work, you should enumerate all partitions of a fixed (k-1)-set into two sets, extend each of them them to a pair of disjoint (k-1)-sets from the ground set, then compute connectivity between the two sets. If you do this, there may be other optimizations to consider, like the best order in which to process these pairs.

But more importantly, k-connectivity is part of the plans for this 'google summer of code'. I do not want to interfere with those plans.

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

comment:19 follow-up: Changed 6 years ago by tscrim

Thanks. Alright, then if you're okay with my changes, positive review.

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

  • Status changed from needs_review to positive_review

Replying to tscrim:

Thanks. Alright, then if you're okay with my changes, positive review.

Absolutely. Thanks for reviewing and for making these changes.

comment:21 Changed 6 years ago by vbraun

  • Branch changed from public/matroid/add_matroid_connectivity-18429 to 9b55e71cbde687f3385ef19f98abc188ccc7362c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.