Ticket #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: | Work issues: | ||
| Report Upstream: | N/A | Reviewers: | Robert Miller |
| Authors: | Tomasz Buchert, Michal Bulant | Merged in: | |
| 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
-
maxflowsolver.patch
(16.4 KB) -
added by tombuc 4 years ago.
- Maximum flow algorithms
-
marriage.patch
(2.2 KB) -
added by tombuc 4 years ago.
- Maximum matching in bipartite graphs
-
MaxflowTest.sws
(44.7 KB) -
added by tombuc 4 years ago.
- Example usage
Change History
Changed 4 years ago by tombuc
-
attachment
maxflowsolver.patch
added
comment:2 Changed 4 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:4 Changed 3 years ago by rlm
- Status changed from needs_review to needs_work
- Reviewers set to Robert Miller
- Report Upstream set to N/A
- Authors changed from tombuc to Tomasz Buchert, Michal Bulant
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 3 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 !!!
Maximum flow algorithms