#9350: Python max flow method
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: jason, mvngu, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.5
Component: graph theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Changes (by ncohen):
* status: new => needs_review
Old description:
> Implementation of a max-flow algorithm which does not use Linear
> Programming.
>
> I will update it right after #8870 is merged
>
> TODO: compare the speeds of functions like edge connectivity, gomory-hu,
> etc ....
>
> Nathann
New description:
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
--
Comment:
Updated, and now needs review :-)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9350#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
