Opened 11 years ago

Closed 11 years ago

#7274 closed enhancement (duplicate)

graphs: Maximum flow algorithms

Reported by: tombuc Owned by: rlm
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: Merged in:
Authors: Tomasz Buchert, Michal Bulant Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

This is work from Sage Days 16 in Barcelona.

First patch implements Edmonds-Karp and Dinic algorithm for DiGraph?. Second one uses this implementation to find maximum matching in bipartite graphs.

I also include worksheet with simple usage example.

Please review.

Attachments (3)

maxflowsolver.patch (16.4 KB) - added by tombuc 11 years ago.
Maximum flow algorithms
marriage.patch (2.2 KB) - added by tombuc 11 years ago.
Maximum matching in bipartite graphs
MaxflowTest.sws (44.7 KB) - added by tombuc 11 years ago.
Example usage

Download all attachments as: .zip

Change History (11)

Changed 11 years ago by tombuc

Maximum flow algorithms

Changed 11 years ago by tombuc

Maximum matching in bipartite graphs

Changed 11 years ago by tombuc

Example usage

comment:1 Changed 11 years ago by tombuc

  • Status changed from new to needs_review

comment:2 Changed 11 years ago by ncohen

I wrote a patch at ticket #6680 including flows and (possibly weighted) matchings ( in the general case ). This patch still hasn't been reviewed, but it could be interesting to compare the performances before merging any of them :-)

comment:3 Changed 11 years ago by mvngu

  • Milestone changed from sage-wishlist to sage-4.3

comment:4 Changed 11 years ago by rlm

  • Authors changed from tombuc to Tomasz Buchert, Michal Bulant
  • Report Upstream set to N/A
  • Reviewers set to Robert Miller
  • Status changed from needs_review to needs_work

Patch applies cleanly and passes tests, and I'm ready to approve except for:

  1. def path_iterator(P) This function needs a docstring. The 100% rule applies here too. Just a simple sentence saying what it does and an example or two will do.

comment:5 Changed 11 years ago by ncohen

As #7592 and #7593 just got reviewed, this patch can not be directly added to sage : there are now functions Graph.flow and Graph.matching available in Sage ( well, in the next version.. )

The problem with these functions is that they still depend on GLPK or CBC, two optional packages that can not be made standard are their licenses are not compatible, so it would be good to have pure Python equivalent.

Several remarks

  • In #7600 and in Graph.coloring, the user can chose which algorithm he would like to use to solve the problem. Maybe the best way is to copy this behaviour in the case of flows and matching to have the two algorithms available.
  • It could be very useful to know how these algorithms compare in terms of performances. This will be much easier to test when flow and matching will be natively in Sage
  • #7634 may not be ready, but time could come soon : with this update the efficiency of the shortest_path method will be improved, and the speed of this implementation too.
  • Somwhere in the code, I saw a call to
    path = R.shortest_path(source, sink,by_weight=False, bidirectional=False)
    
    I wondered why you chosed not to use the bidirectional version of the algorithm, as it is expected to be faster.. :-)

Thank you for your work !!!

comment:6 Changed 11 years ago by jason

Apparently #3930 should be closed when this is merged.

comment:7 Changed 11 years ago by ncohen

We have a Python version for max flow through #9350 ... So as this ticket has been here for 10 months now..

Nathann

comment:8 Changed 11 years ago by mvngu

  • Milestone changed from sage-4.6 to sage-duplicate/invalid/wontfix
  • Resolution set to duplicate
  • Status changed from needs_work to closed

Close as duplicate of #9350.

Note: See TracTickets for help on using tickets.