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: |
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)
Change History (11)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
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
- Milestone changed from sage-wishlist to sage-4.3
comment:4 Changed 11 years ago by
- 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:
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
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
Apparently #3930 should be closed when this is merged.
comment:7 Changed 11 years ago by
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
- 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.
Maximum flow algorithms