Opened 9 years ago

Closed 9 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 ncohen)

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)

trac_9350.patch (23.1 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 9 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

Updated, and now needs review :-)

comment:3 follow-up: Changed 9 years ago by wdj

  • 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: Changed 9 years ago by 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

comment:5 in reply to: ↑ 4 Changed 9 years ago by wdj

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 9 years ago by ncohen

comment:6 follow-up: Changed 9 years ago by ncohen

  • 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 9 years ago by wdj

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 9 years ago by dimpase

  • 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 9 years ago by ncohen

Thanksssss ! :-)

comment:10 Changed 9 years ago by mpatel

  • Authors set to Nathann Cohen
  • Reviewers set to Dmitrii Pasechnik, David Joyner

comment:11 Changed 9 years ago by mpatel

Please remember to fill in the "Author(s)" and "Reviewer(s)" fields.

comment:12 Changed 9 years ago by mpatel

  • Merged in set to sage-4.6.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.