Opened 8 years ago
Closed 7 years ago
#18687 closed enhancement (fixed)
Implement the shifting algorithm for 3 and 4-connectivity
Reported by: | chaoxu | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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 4-connectivity. (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/TR90-15.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 user-facing 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