Opened 6 years ago
Closed 6 years ago
#18687 closed enhancement (fixed)
Implement the shifting algorithm for 3 and 4connectivity
Reported by:  chaoxu  Owned by:  

Priority:  major  Milestone:  sage6.8 
Component:  matroid theory  Keywords:  
Cc:  Stefan, yomcat, Rudi  Merged in:  
Authors:  Chao Xu  Reviewers:  Stefan van Zwam 
Report Upstream:  N/A  Work issues:  
Branch:  095e372 (Commits, GitHub, GitLab)  Commit:  095e37273835694971d2232271d55273fb7a54e0 
Dependencies:  Stopgaps: 
Description
Implement the fast shifting algorithm for connectivity. It include a fast algorithm for both 3 and 4connectivity. (the algorithms also works for higher connectivity, but not as fast.)
The following two papers contain the idea of the algorithm:
http://www.caam.rice.edu/caam/trs/90/TR9015.pdf Rajan, A. (1987). Algorithmic applications of connectivity and related topics in matroid theory. Northwestern university.
Change History (21)
comment:1 Changed 6 years ago by
 Branch set to u/chaoxu/shifting_algorithm
comment:2 Changed 6 years ago by
 Commit set to a81e5ceffa65c5a284157415349ee199c4104afe
comment:3 Changed 6 years ago by
 Commit changed from a81e5ceffa65c5a284157415349ee199c4104afe to 4aa5dc25df720100bbb3041d9f60051b18d81d18
Branch pushed to git repo; I updated commit sha1. New commits:
4aa5dc2  The algorithm seems to fail when 2*r(E) > E, so take the dual

comment:4 Changed 6 years ago by
 Commit changed from 4aa5dc25df720100bbb3041d9f60051b18d81d18 to 8b7c0328066729a6c99ba579bf9b52fd1f921b61
Branch pushed to git repo; I updated commit sha1. New commits:
8b7c032  Fixed the bug

comment:5 Changed 6 years ago by
 Commit changed from 8b7c0328066729a6c99ba579bf9b52fd1f921b61 to bef6a5651f41f89b904f0e1e64e9b0f413a65e1e
Branch pushed to git repo; I updated commit sha1. New commits:
bef6a56  Only use edges in a spanning tree for computing 3 connectivity

comment:6 Changed 6 years ago by
 Commit changed from bef6a5651f41f89b904f0e1e64e9b0f413a65e1e to 14cdee9deac316c53af63229aea06678ef6eb979
Branch pushed to git repo; I updated commit sha1. New commits:
14cdee9  use reduced representation for linear matroids

comment:7 Changed 6 years ago by
 Commit changed from 14cdee9deac316c53af63229aea06678ef6eb979 to e5f519576e8ea761f2716fcca8122b5063f67788
Branch pushed to git repo; I updated commit sha1. New commits:
e5f5195  optimized 4_connected_shifting

comment:8 Changed 6 years ago by
 Commit changed from e5f519576e8ea761f2716fcca8122b5063f67788 to 95edcb0729deef502184b3a2d342a7087372b89c
comment:9 Changed 6 years ago by
 Commit changed from 95edcb0729deef502184b3a2d342a7087372b89c to 378fb37e1873f92117c8881cc0e3e7c29a63067c
comment:10 Changed 6 years ago by
 Status changed from new to needs_review
comment:12 Changed 6 years ago by
 Commit changed from 378fb37e1873f92117c8881cc0e3e7c29a63067c to c54b4b34b51b5e5fcce1ecb341dd5e4afedf055b
Branch pushed to git repo; I updated commit sha1. New commits:
c54b4b3  Merge branch 'develop' into t/18687/shifting_algorithm

comment:13 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:14 Changed 6 years ago by
 Cc Rudi added; rudi removed
comment:15 Changed 6 years ago by
 Commit changed from c54b4b34b51b5e5fcce1ecb341dd5e4afedf055b to d4cde3eb18d86b533582e4882dd0408e71c55a22
Branch pushed to git repo; I updated commit sha1. New commits:
d4cde3e  put shifting into lean_matrix

comment:16 Changed 6 years ago by
 Status changed from needs_review to needs_work
Something fishy is going on with the commits. When I click the green link above, it looks like the branch is removing all of the contents of matroid.pyx. The "git trac try" command seems to work fine, so I don't quite know what's going on here.
One thing that definitely needs fixing is that some makefiles get added by mistake.
Some more questions / issues:
 the shifting algorithm is not mentioned as an option in the is_3connected docstring
 the _is_3connected_shifting docstring mistakenly has a 4 in its first line
 there is no userfacing is_4connected that can benefit from the shifting algorithm.
comment:17 Changed 6 years ago by
 Commit changed from d4cde3eb18d86b533582e4882dd0408e71c55a22 to acfe0f1955ff081cc0241022283357672b005a25
comment:18 Changed 6 years ago by
 Commit changed from acfe0f1955ff081cc0241022283357672b005a25 to 095e37273835694971d2232271d55273fb7a54e0
comment:19 Changed 6 years ago by
 Status changed from needs_work to needs_review
I made a new merge, that strange problem seems to go away.
Fixed other problems.
comment:20 Changed 6 years ago by
 Reviewers set to Stefan van Zwam
 Status changed from needs_review to positive_review
I'm happy with this code now. Positive review from me.
comment:21 Changed 6 years ago by
 Branch changed from u/chaoxu/shifting_algorithm to 095e37273835694971d2232271d55273fb7a54e0
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
add testing for 4 connectivity