Opened 11 years ago
Closed 11 years ago
#8166 closed enhancement (fixed)
Expose max_weight_matching from NetworkX
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.4.4 |
Component: | graph theory | Keywords: | |
Cc: | ylchapuy, jason, mvngu | Merged in: | sage-4.4.4.alpha0 |
Authors: | Nathann Cohen | Reviewers: | Minh Van Nguyen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Since the new version of NetworkX is being merged into Sage #7608, we could use their max matching algorithm. We already have one, though it uses Linear Programming and is optional :
The efficiency of these two algorithms have to be compared !
Based upon this, the default behaviour could be :
- To always use NetworkX
- Only use it if there is no LP available
- Not to use it if not asked explicitely
Apply:
Attachments (3)
Change History (11)
comment:1 Changed 11 years ago by
- Description modified (diff)
comment:2 Changed 11 years ago by
- Type changed from defect to enhancement
comment:3 Changed 11 years ago by
- Cc jason mvngu added
- Status changed from new to needs_review
Changed 11 years ago by
comment:4 Changed 11 years ago by
- Description modified (diff)
- Reviewers set to Minh Van Nguyen
I have attached a rebase of ncohen's patch, rebased on top of #8364. Based upon that, I did some clean-ups of the changes proposed by ncohen. My changes are mainly cosmetic clean-ups along the lines of PEP 008. Both ncohen's patch and my changes are folded into one patch to make it easier for anyone to give a final review.
comment:5 Changed 11 years ago by
Oh, but then it means I can not review it myself ? :-)
Nathann
comment:6 Changed 11 years ago by
reviewer.diff contains the changes I folded into ncohen's patch. This should make it easier to review trac_8166-rebase.patch.
Changed 11 years ago by
comment:7 Changed 11 years ago by
- Status changed from needs_review to positive_review
Nice, perfect, no error anywhere and many spelling/syntax mistakes fixed... Thank you again Minh ! :-)
Nathann
comment:8 Changed 11 years ago by
- Merged in set to sage-4.4.4.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
As max_weight_matching had been exposed while I wasn't looking, this ticket now merges the two function into only one, for the better I hope ! :-)
From now on, maximum matching are not optional anymore, and are way faster !
The two different ways to solve matchings are kept, just in case.... But network'x version is now the default one, obviously :-)
Requires #8364
Nathann