Opened 10 years ago

Closed 9 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 mvngu)

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:

  1. #8364
  2. trac_8166-rebase.patch

Attachments (3)

trac_8166.patch (5.8 KB) - added by ncohen 9 years ago.
trac_8166-rebase.patch (10.2 KB) - added by mvngu 9 years ago.
reviewer.diff (10.1 KB) - added by mvngu 9 years ago.
diff patch showing changes proposed by reviewer

Download all attachments as: .zip

Change History (11)

comment:1 Changed 10 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 9 years ago by jason

  • Type changed from defect to enhancement

comment:3 Changed 9 years ago by ncohen

  • Cc jason mvngu added
  • Status changed from new to needs_review

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 !

sage: g = graphs.RandomGNP(50,.3)
sage: %timeit g.matching(algorithm="LP",solver="GLPK")
5 loops, best of 3: 248 ms per loop
sage: %timeit g.matching()
25 loops, best of 3: 16.9 ms per loop

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

Changed 9 years ago by ncohen

comment:4 Changed 9 years ago by mvngu

  • Authors set to Nathann Cohen
  • 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 9 years ago by ncohen

Oh, but then it means I can not review it myself ? :-)

Nathann

comment:6 Changed 9 years ago by mvngu

reviewer.diff contains the changes I folded into ncohen's patch. This should make it easier to review trac_8166-rebase.patch.

Changed 9 years ago by mvngu

Changed 9 years ago by mvngu

diff patch showing changes proposed by reviewer

comment:7 Changed 9 years ago by ncohen

  • 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 9 years ago by mhansen

  • Merged in set to sage-4.4.4.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.