Python max flow method

[nathanncohen]

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

Component: graph theory

Author: Nathann Cohen

Reviewer: Dmitrii Pasechnik, David Joyner

Merged: sage-4.6.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/9350

[nathanncohen]

comment:2

Updated, and now needs review :-)

[wdjoyner]

comment:3

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?

[nathanncohen]

comment:4

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

[wdjoyner]

comment:5

Replying to @nathanncohen:

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?

[nathanncohen]

Attachment: trac_9350.patch.gz

[nathanncohen]

comment:6

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

[wdjoyner]

comment:7

Replying to @nathanncohen:

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!!

[dimpase]

comment:8

I also tested this, and it looks OK.
Wdj, have you forgotten to give it positive review?

Dima

[nathanncohen]

comment:9

Thanksssss ! :-)

[qed777]

Author: Nathann Cohen

[qed777]

Reviewer: Dmitrii Pasechnik, David Joyner

[qed777]

comment:11

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

[qed777]

Merged: sage-4.6.alpha1