Talk:Ford–Fulkerson algorithm

After 1998 more steps …

I'm new to this, so I didnt change it directly because I'm not 100% sure. But the flow isn't increased by 1 but by min{capacies of edges on the found path}, so it should only take 1 step to fill one path up. —Preceding unsigned comment added by 85.180.69.27 (talk) 12:19, 20 February 2009 (UTC)

Algorithms by nature terminate. this article is full of references to "whether the algorithm terminates" and "a variation which is guaranteed to terminate". these phrases are problematic! is F-F not an algorithm at all, but an approach/procedure? Aaronbrick 04:34, 12 May 2006 (UTC)

This is a valid point. This entry should actually be called the Ford-Fulkerson Method. It's not called an algorithm, because there is some part in the procedure which is left unspecified. The Ford-Fulkerson Method says that you need to keep finding augmenting paths in the residual graph, but does not limit you to any specific way of finding those augmenting paths. That is exactly why the procedure may never terminate, as described in the body of the article. On the other hand, an algorithm should always terminate with an answer, or with announcing that no answer can be found. That is the basic criteria for decidability, and an algorithm is formally defined to be a procedure for testing membership for decidable languages. —Preceding unsigned comment added by 128.227.179.104 (talk) 02:58, 11 October 2007 (UTC)

We should use the name most commonly used in the field, regardless of whether it may be technically inaccurate accordingly to a particular definition of "algorithm." I have seen it called "the Ford-Fulkerson method" though, so this may be justified. Dcoetzee 00:10, 3 October 2008 (UTC)

As I know the term algorithm it doesnt have to terminate.

"We should use the name most commonly used in the field" Why? If it's an incorrect, but common term then just let that term redirect to the correct term. Wikipedia is enormously responsible for the terms people use "in the field", so it would just be responsible for perpetuating an incorrect term "in the field". As for "As I know the term algorithm it doesnt have to terminate", it seems you know it differently than the rest of us. Mangledorf (talk) 00:15, 13 November 2009 (UTC)

Error in example_2.svg

The middle arrow from should point from C to B, not from B to C.

Errors in the Algorithm Section

There seems to be a slight error in the "Algorithm" section. There are three formulas with three informal descriptions next to them. The informal descriptions for the second and third seem to have been interchanged. In short, it is:

2. f(u,v)=-f(v,u) - We maintain the net flow.
3. sum(f(u,v))=0 for all nodes except s and t - The amount of flow into a node equals the flow out of the node.

whereas it should be:

2. f(u,v)=-f(v,u) - The amount of flow into a node equals the flow out of the node.
3. sum(f(u,v))=0 for all nodes except s and t - We maintain the net flow.

I would also suggest replacing "for all nodes" with "for all nodes u" for clarity.

Viridium 03:27, 10 April 2007 (UTC)

The wording is perhaps a bit unclear. By "maintaining the net flow", it is meant that if there are in reality going for example 5 trucks from $u$ to $v$, and 3 trucks from $v$ to $u$, then we maintain $f(u,v)=2$ and $f(v,u)=-2$, such that $f(u,v)=-f(v,u)$. For the third invariant, it might get clearer if written

$\sum _{v}f(u,v)=0\Longleftrightarrow \sum _{v}f_{-}(u,v)+\sum _{v}f_{+}(u,v)=0\Longleftrightarrow \sum _{v}f_{-}(u,v)=\sum _{v}f_{+}(u,v)\Longleftrightarrow f_{in}(u)=f_{out}(u)$

where $f_{-}$ is only the negative values, and $f_{+}$ only the positive. Klem fra Nils Grimsmo 05:39, 11 April 2007 (UTC

Nice clarification but some detail is wrong there (in equation above). There is a minus sign missing. Where this minus sign should go depends on which convention you use for the defintion of $f_{-}(u,v)$ : Is it the absolute value of the negative flow, or is it the actual negative flow complete with its numerical negativity?

In the example, I don't see how the possibility of flow directly along ABD is skipped at the second step, given that this example of bad behaviour is claiming to result from depth first search. Surely, in an alphabetic "depth first search", path ABD should be tried next -- before ACBD is tried! --Preceding unsigned comment left by 128.227.179.104 02:58, 11 October 2007 (UTC)

The depth-first search must not be alphabetic - it seems to be actively worst-case. That sort of thing can happen if the edges are stored in a nondeterministic, unordered set instead of a matrix. It's pretty unlikely, but that's what worst-case means. --Brilliand 22:58, 26 October 2007 (UTC)

counterexample

It would be nice to have the counterexample of when it doesn't terminate and converges to the wrong value.--MarSch (talk) 15:43, 2 October 2008 (UTC)

I found a likely reference for this (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.2479), but I don't know if I'll have time to write it up. --MarSch (talk) 15:50, 2 October 2008 (UTC)

The book "Matching Theory" by Plummer and Lovasz has it. Zero^talk 12:27, 15 October 2009 (UTC)

I added the counterexample. Svick (talk) 01:38, 16 October 2009 (UTC)

Thanks, but can you describe it more, please? The algorithm only converges to the wrong value if a particular sequence of augmenting paths is chosen. Zero^talk

I expanded that section. Do you think it is understandable and correct? (Like you pointed out, it wasn't before.) Svick (talk) 23:34, 9 November 2009 (UTC)

The flow converges to 3+2r, not 3. Also, I made the computations and I think that it's enough that M is at least 2 (not that it's important). —Preceding unsigned comment added by Mkonva (talk • contribs) 04:37, 2 December 2009 (UTC)

I checked the source I cited and it says that the flow converges to $\textstyle 1+2\sum _{i=2}^{\infty }r^{i}=3$. But I think you are right and it should be $3+2r$, but maybe I misunderstood something. Could somebody read the paper and confirm that it's really wrong? If that is the case, we should find another source.

I think that you are correct that $M=2$ is sufficient, but again, the source says it's $4$. Again, we should find another source.

Thanks for finding the (possible) errors. Svick (talk) 18:54, 2 December 2009 (UTC)

Python example

An anon made the following comment on the python program. Someone should check it.

"The code is incomplete and does not work at all. The understanding of language features of Python is very good. But the understanding of the Ford-Fulkerson algorithm is very poor. The DFS in find_path is not even correct." Zero^talk 12:23, 15 October 2009 (UTC)

I can see some problems in the find_path code (the path it returns isn't a simple path when it should and it doesn't run in optimal time), that sould be corrected, but I think that the whole code nevertheless works correctly. Svick (talk) 23:37, 15 October 2009 (UTC)

I may be wrong, but I see at least one more problem: why is adj[u] not the same as adj[v] in add_edge? Should both the edges not have the same capacity w instead of one being 0? musically_ut (talk) 07:04, 5 November 2009 (UTC)

No, this version is also correct. In directed network, edge from $u$ to $v$ with capacity $c$ doesn't mean that there is an edge from $v$ to $u$ with the same capacity. If your network is undirected (similar to real pipes), you have to add each edge twice, once for every direction. Your version would work too, but only for undirected networks. Svick (talk) 23:42, 9 November 2009 (UTC)

Application to hypergraphs

Is the Ford–Fulkerson algorithm extensible to hypergraphs?--134.68.140.60 (talk) 17:05, 29 January 2010 (UTC)