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:  sage6.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: 
Description (last modified by )
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)
Change History (23)
comment:1 Changed 6 years ago by
 Branch set to u/Rudi/add_the_matroid_connectivity_function
comment:2 Changed 6 years ago by
 Commit set to 2b9bd7511108a7df8390df66ba3ee82403cc6cd8
comment:3 Changed 6 years ago by
 Commit changed from 2b9bd7511108a7df8390df66ba3ee82403cc6cd8 to 9a57d0bfd530ac5a4d08ee33e662c932caca9200
Branch pushed to git repo; I updated commit sha1. New commits:
9a57d0b  Less is more

comment:4 Changed 6 years ago by
 Commit changed from 9a57d0bfd530ac5a4d08ee33e662c932caca9200 to be12041abe8c38fa2835050f6479b89bfefa5044
Branch pushed to git repo; I updated commit sha1. New commits:
be12041  Finishing touch

comment:5 Changed 6 years ago by
 Commit changed from be12041abe8c38fa2835050f6479b89bfefa5044 to e935dc2d1d62cf2280bc85a0c7ea2cf5d2370923
Branch pushed to git repo; I updated commit sha1. New commits:
e935dc2  Done

comment:6 Changed 6 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:7 Changed 6 years ago by
 Commit changed from e935dc2d1d62cf2280bc85a0c7ea2cf5d2370923 to 6929d5e33cd39c42f2187ed18b9c69683a918bc3
Branch pushed to git repo; I updated commit sha1. New commits:
6929d5e  Some further speedups

Changed 6 years ago by
Changed 6 years ago by
comment:8 Changed 6 years ago by
 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
 Commit changed from 6929d5e33cd39c42f2187ed18b9c69683a918bc3 to 5635654a4bf39acbb5cbad2219526b3c4493fde4
Branch pushed to git repo; I updated commit sha1. New commits:
5635654  Killed the last bug and tweaked BinaryMatroid._minor() for better efficiency

comment:11 Changed 6 years ago by
 Commit changed from 5635654a4bf39acbb5cbad2219526b3c4493fde4 to 01e11cd06efd516f8f5cb90562f24076f0cbcfaa
comment:12 Changed 6 years ago by
 Commit changed from 01e11cd06efd516f8f5cb90562f24076f0cbcfaa to 7d59d68674efb0dea16e28169e70687c9e860208
Branch pushed to git repo; I updated commit sha1. New commits:
7d59d68  One more bug

comment:13 Changed 6 years ago by
I could not resist adding functionality to is_3connected, namely returning a separation to certify that the matroid is nor 3connected. This did involve slightly altering the interface to the matroid intersection augmentation routine, to return the corresponding dual solution of a maxcardinality problem.
comment:14 Changed 6 years ago by
 Milestone changed from sage6.7 to sage6.8
comment:15 Changed 6 years ago by
 Cc chaoxu added
 Owner changed from (none) to Rudi
comment:16 Changed 6 years ago by
 Commit changed from 7d59d68674efb0dea16e28169e70687c9e860208 to 402fdf71b37a6753076be4ccf8a157667694b75d
Branch pushed to git repo; I updated commit sha1. New commits:
402fdf7  Killed a doctest bug

comment:17 followup: ↓ 18 Changed 6 years ago by
 Branch changed from u/Rudi/add_the_matroid_connectivity_function to public/matroid/add_matroid_connectivity18429
 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 < k1
?
New commits:
aa453e7  Merge branch 'do_not_checkout' into public/matroid/add_matroid_connectivity18429

9b55e71  Reviewer changes to docstring formatting and trailing whitespace.

comment:18 in reply to: ↑ 17 Changed 6 years ago by
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< k1
?
It's a bit more work, you should enumerate all partitions of a fixed (k1)
set into two sets, extend each of them them to a pair of disjoint (k1)
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, kconnectivity is part of the plans for this 'google summer of code'. I do not want to interfere with those plans.
comment:19 followup: ↓ 20 Changed 6 years ago by
Thanks. Alright, then if you're okay with my changes, positive review.
comment:20 in reply to: ↑ 19 Changed 6 years ago by
 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
 Branch changed from public/matroid/add_matroid_connectivity18429 to 9b55e71cbde687f3385ef19f98abc188ccc7362c
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Added function definitions.