Opened 6 years ago

Closed 6 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:

Status badges

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 6 years ago by chaoxu

  • Branch set to u/chaoxu/shifting_algorithm

comment:2 Changed 6 years ago by git

  • Commit set to a81e5ceffa65c5a284157415349ee199c4104afe

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

​a81e5ceadd testing for 4 connectivity

comment:3 Changed 6 years ago by git

  • Commit changed from a81e5ceffa65c5a284157415349ee199c4104afe to 4aa5dc25df720100bbb3041d9f60051b18d81d18

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

​4aa5dc2The algorithm seems to fail when 2*r(E) > E, so take the dual

comment:4 Changed 6 years ago by git

  • Commit changed from 4aa5dc25df720100bbb3041d9f60051b18d81d18 to 8b7c0328066729a6c99ba579bf9b52fd1f921b61

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

​8b7c032Fixed the bug

comment:5 Changed 6 years ago by git

  • Commit changed from 8b7c0328066729a6c99ba579bf9b52fd1f921b61 to bef6a5651f41f89b904f0e1e64e9b0f413a65e1e

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

​bef6a56Only use edges in a spanning tree for computing 3 connectivity

comment:6 Changed 6 years ago by git

  • Commit changed from bef6a5651f41f89b904f0e1e64e9b0f413a65e1e to 14cdee9deac316c53af63229aea06678ef6eb979

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

​14cdee9use reduced representation for linear matroids

comment:7 Changed 6 years ago by git

  • Commit changed from 14cdee9deac316c53af63229aea06678ef6eb979 to e5f519576e8ea761f2716fcca8122b5063f67788

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

​e5f5195optimized 4_connected_shifting

comment:8 Changed 6 years ago by git

  • Commit changed from e5f519576e8ea761f2716fcca8122b5063f67788 to 95edcb0729deef502184b3a2d342a7087372b89c

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

​cfc248dshould use non-zero instead of 1
​3dfdb43Merge branch 'develop' into t/18687/shifting_algorithm
​95edcb0fixed the bug

comment:9 Changed 6 years ago by git

  • Commit changed from 95edcb0729deef502184b3a2d342a7087372b89c to 378fb37e1873f92117c8881cc0e3e7c29a63067c

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

​dd7b56flinear time for single shifting
​28ebcb8fixed bug: the representation might change between calls
​378fb37polish up, add tests

comment:10 Changed 6 years ago by chaoxu

  • Status changed from new to needs_review

comment:11 Changed 6 years ago by yomcat

  • Status changed from needs_review to needs_work

Needs rebasing.

comment:12 Changed 6 years ago by git

  • Commit changed from 378fb37e1873f92117c8881cc0e3e7c29a63067c to c54b4b34b51b5e5fcce1ecb341dd5e4afedf055b

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

​c54b4b3Merge branch 'develop' into t/18687/shifting_algorithm

comment:13 Changed 6 years ago by chaoxu

  • Status changed from needs_work to needs_review

comment:14 Changed 6 years ago by Rudi

  • Cc Rudi added; rudi removed

comment:15 Changed 6 years ago by git

  • Commit changed from c54b4b34b51b5e5fcce1ecb341dd5e4afedf055b to d4cde3eb18d86b533582e4882dd0408e71c55a22

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

​d4cde3eput shifting into lean_matrix

comment:16 Changed 6 years ago by Stefan

  • 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 user-facing is_4connected that can benefit from the shifting algorithm.

comment:17 Changed 6 years ago by git

  • Commit changed from d4cde3eb18d86b533582e4882dd0408e71c55a22 to acfe0f1955ff081cc0241022283357672b005a25

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

​8a57453Merge branch 'develop' into t/18687/shifting_algorithm
​acfe0f1clean up

comment:18 Changed 6 years ago by git

  • Commit changed from acfe0f1955ff081cc0241022283357672b005a25 to 095e37273835694971d2232271d55273fb7a54e0

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

​9fc24efrm build files
​095e372update docs

comment:19 Changed 6 years ago by chaoxu

  • 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 Stefan

  • Authors set to Chao Xu
  • 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 vbraun

  • Branch changed from u/chaoxu/shifting_algorithm to 095e37273835694971d2232271d55273fb7a54e0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.