Opened 10 years ago
Closed 10 years ago
#9350 closed enhancement (fixed)
Python max flow method
Reported by: | ncohen | Owned by: | jason, mvngu, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.6.alpha1 | |
Authors: | Nathann Cohen | Reviewers: | Dmitrii Pasechnik, David Joyner |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Implementation of a max-flow algorithm which does not use Linear Programming. A tad faster than the current LP implementation.
This ticket also updates several other methods which formerly used flows (or could be made to), so that they may use the speedup !
sage: g = graphs.PetersenGraph() sage: %timeit g.flow(0,1, method = "LP") 125 loops, best of 3: 2.85 ms per loop sage: %timeit g.flow(0,1) 625 loops, best of 3: 1.19 ms per loop
sage: g = graphs.RandomGNP(200,0.1) sage: %timeit g.flow(0,1, method = "LP") 5 loops, best of 3: 322 ms per loop sage: %timeit g.flow(0,1) 5 loops, best of 3: 73.5 ms per loop
sage: %timeit g.edge_cut(0,1, method="LP") 5 loops, best of 3: 377 ms per loop sage: %timeit g.edge_cut(0,1) 5 loops, best of 3: 72.5 ms per loop
g = graphs.RandomGNP(50,0.2) sage: %timeit g.gomory_hu_tree() 5 loops, best of 3: 4.22 s per loop sage: %timeit g.gomory_hu_tree(method="LP") 5 loops, best of 3: 5.38 s per loop
I expected a much better speedup for gomory_hu, by the way.... It's odd, it sounds like the bottleneck is somewhere else... O_o
_This patch is dedicated to anybody who ever refused one of my patches for lack of doctests. I wouldn't have noticed half of the bugs in this patch without the help of those doctests in the functions that use flow... I won't ever complain anymore because of that ! :-D_
Nathann
Attachments (1)
Change History (13)
comment:1 Changed 10 years ago by
- Description modified (diff)
comment:2 Changed 10 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:3 follow-up: ↓ 4 Changed 10 years ago by
- Status changed from needs_review to needs_info
This applies okay to 4.5.2.a1 and seems to pass all tests, except for some unrelated failures. However, there are no examples in edge_cut with vertices=True, eg
sage: g = graphs.PetersenGraph() sage: g.edge_cut(0, 3, method="FF", vertices=True) [3, [(0, 1, None), (0, 4, None), (0, 5, None)], [[0], [1, 2, 3, 4, 5, 6, 7, 8, 9]]]
Why is this?
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 10 years ago by
Why is this?
What do you think of line 3652 of the generic_graph.py file ? :-)
sage: value,edges,[set1,set2] = g.edge_cut(0, 14, use_edge_labels=True, vertices=True)
Nathann
comment:5 in reply to: ↑ 4 Changed 10 years ago by
Replying to ncohen:
Why is this?
What do you think of line 3652 of the generic_graph.py file ?
:-)
sage: value,edges,[set1,set2] = g.edge_cut(0, 14, use_edge_labels=True, vertices=True)Nathann
The value isn't returned, so the potential user cannot see examples of how the output changes for different choices of the input. I'm just wondering if there was a good reason for omitting the edges in the output. An example with value_only=False would be equally nice. Finally, to be extremely picky, the description
``vertices`` -- boolean (default: ``False``). When set to ``True``, also returns the two sets of vertices that are disconnected by the cut. Implies ``value_only=False``.
should probably read
``vertices`` -- boolean (default: ``False``). When set to ``True``, returns a list of edges in the edge cut and the two sets of vertices that are disconnected by the cut. Note: ``vertices=True`` implies ``value_only=False``.
Does this seem reasonable?
Changed 10 years ago by
comment:6 follow-up: ↓ 7 Changed 10 years ago by
- Status changed from needs_info to needs_review
It does ! I just updated the patch with you example and the corrected docstring :-)
There was, indeed, a reason for never showing directly the output of all these methods : it formerly used Linear Programming, and the results of LP, eve though correct, can vary depending on the time of the day and the solver used. So showing it is asking for trouble, though one can perfectly check some relations... But this Python implementation being deterministic, it's fine now !
Nathann
comment:7 in reply to: ↑ 6 Changed 10 years ago by
Replying to ncohen:
It does ! I just updated the patch with you example and the corrected docstring
:-)
There was, indeed, a reason for never showing directly the output of all these methods : it formerly used Linear Programming, and the results of LP, even though correct, can vary depending on the time of the day and the solver used. So showing it is asking for trouble, though one can perfectly check some relations... But this Python implementation being deterministic, it's fine now !
Nathann
Excellent. Passed tested for me (except for unrelated doctest failures on a mac 10.6.4).
Thanks Nathann!!
comment:8 Changed 10 years ago by
- Status changed from needs_review to positive_review
I also tested this, and it looks OK. Wdj, have you forgotten to give it positive review?
Dima
comment:9 Changed 10 years ago by
Thanksssss ! :-)
comment:10 Changed 10 years ago by
- Reviewers set to Dmitrii Pasechnik, David Joyner
comment:11 Changed 10 years ago by
Please remember to fill in the "Author(s)" and "Reviewer(s)" fields.
comment:12 Changed 10 years ago by
- Merged in set to sage-4.6.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
Updated, and now needs review :-)