Opened 8 years ago
Closed 7 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 8 years ago by
Branch:  → u/chaoxu/shifting_algorithm 

comment:2 Changed 8 years ago by
Commit:  → a81e5ceffa65c5a284157415349ee199c4104afe 

comment:3 Changed 8 years ago by
Commit:  a81e5ceffa65c5a284157415349ee199c4104afe → 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 8 years ago by
Commit:  4aa5dc25df720100bbb3041d9f60051b18d81d18 → 8b7c0328066729a6c99ba579bf9b52fd1f921b61 

Branch pushed to git repo; I updated commit sha1. New commits:
8b7c032  Fixed the bug

comment:5 Changed 8 years ago by
Commit:  8b7c0328066729a6c99ba579bf9b52fd1f921b61 → 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 8 years ago by
Commit:  bef6a5651f41f89b904f0e1e64e9b0f413a65e1e → 14cdee9deac316c53af63229aea06678ef6eb979 

Branch pushed to git repo; I updated commit sha1. New commits:
14cdee9  use reduced representation for linear matroids

comment:7 Changed 8 years ago by
Commit:  14cdee9deac316c53af63229aea06678ef6eb979 → e5f519576e8ea761f2716fcca8122b5063f67788 

Branch pushed to git repo; I updated commit sha1. New commits:
e5f5195  optimized 4_connected_shifting

comment:8 Changed 8 years ago by
Commit:  e5f519576e8ea761f2716fcca8122b5063f67788 → 95edcb0729deef502184b3a2d342a7087372b89c 

comment:9 Changed 8 years ago by
Commit:  95edcb0729deef502184b3a2d342a7087372b89c → 378fb37e1873f92117c8881cc0e3e7c29a63067c 

comment:10 Changed 8 years ago by
Status:  new → needs_review 

comment:12 Changed 8 years ago by
Commit:  378fb37e1873f92117c8881cc0e3e7c29a63067c → c54b4b34b51b5e5fcce1ecb341dd5e4afedf055b 

Branch pushed to git repo; I updated commit sha1. New commits:
c54b4b3  Merge branch 'develop' into t/18687/shifting_algorithm

comment:13 Changed 8 years ago by
Status:  needs_work → needs_review 

comment:14 Changed 8 years ago by
Cc:  Rudi added; rudi removed 

comment:15 Changed 8 years ago by
Commit:  c54b4b34b51b5e5fcce1ecb341dd5e4afedf055b → d4cde3eb18d86b533582e4882dd0408e71c55a22 

Branch pushed to git repo; I updated commit sha1. New commits:
d4cde3e  put shifting into lean_matrix

comment:16 Changed 7 years ago by
Status:  needs_review → 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 7 years ago by
Commit:  d4cde3eb18d86b533582e4882dd0408e71c55a22 → acfe0f1955ff081cc0241022283357672b005a25 

comment:18 Changed 7 years ago by
Commit:  acfe0f1955ff081cc0241022283357672b005a25 → 095e37273835694971d2232271d55273fb7a54e0 

comment:19 Changed 7 years ago by
Status:  needs_work → needs_review 

I made a new merge, that strange problem seems to go away.
Fixed other problems.
comment:20 Changed 7 years ago by
Authors:  → Chao Xu 

Reviewers:  → Stefan van Zwam 
Status:  needs_review → positive_review 
I'm happy with this code now. Positive review from me.
comment:21 Changed 7 years ago by
Branch:  u/chaoxu/shifting_algorithm → 095e37273835694971d2232271d55273fb7a54e0 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
add testing for 4 connectivity