Changes between Version 1 and Version 2 of Ticket #9350


Ignore:
Timestamp:
07/08/10 12:41:35 (9 years ago)
Author:
ncohen
Comment:

Updated, and now needs review :-)

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #9350

    • Property Status changed from new to needs_review
  • Ticket #9350 – Description

    v1 v2  
    1 Implementation of a max-flow algorithm which does not use Linear Programming.
     1Implementation of a max-flow algorithm which does not use Linear Programming. A tad faster than the current LP implementation.
    22
    3 I will update it right after #8870 is merged
     3This ticket also updates several other methods which formerly used flows (or could be made to), so that they may use the speedup !
    44
    5 TODO: compare the speeds of functions like edge connectivity, gomory-hu, etc ....
     5{{{
     6sage: g = graphs.PetersenGraph()
     7sage: %timeit g.flow(0,1, method = "LP")
     8125 loops, best of 3: 2.85 ms per loop
     9sage: %timeit g.flow(0,1)
     10625 loops, best of 3: 1.19 ms per loop
     11}}}
     12
     13{{{
     14sage: g = graphs.RandomGNP(200,0.1)
     15sage: %timeit g.flow(0,1, method = "LP")
     165 loops, best of 3: 322 ms per loop
     17sage: %timeit g.flow(0,1)
     185 loops, best of 3: 73.5 ms per loop
     19}}}
     20
     21{{{
     22sage: %timeit g.edge_cut(0,1, method="LP")
     235 loops, best of 3: 377 ms per loop
     24sage: %timeit g.edge_cut(0,1)
     255 loops, best of 3: 72.5 ms per loop
     26}}}
     27
     28{{{
     29g = graphs.RandomGNP(50,0.2)
     30sage: %timeit g.gomory_hu_tree()
     315 loops, best of 3: 4.22 s per loop
     32sage: %timeit g.gomory_hu_tree(method="LP")
     335 loops, best of 3: 5.38 s per loop
     34}}}
     35
     36I expected a much better speedup for gomory_hu, by the way.... It's odd, it sounds like the bottleneck is somewhere else... O_o
     37
     38___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___
    639
    740Nathann