This Â
level-5 vital article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
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)
The middle arrow from should point from C to B, not from B to C.
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)
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  : 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)
Svend 11:36, 03 September 2011 (UTC)
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)
Isn't this more like the EdmondsâKarp algorithm? I thought the Ford Fulkerson keeps the selection of the paths unspecified... â Preceding unsigned comment added by 2001:9E8:1120:8C00:386F:F73E:7DE:BE89 ( talk) 19:34, 3 April 2024 (UTC)
The python code is useless without an example call. In particular, it is not clear how to instantiate the class (and why should it be a class anyway). â Preceding unsigned comment added by 2001:9E8:1120:8C00:386F:F73E:7DE:BE89 ( talk) 09:31, 3 April 2024 (UTC)
An anon made the following comment on the python program. Someone should check it.
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)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)
The following example demonstrates a bug in the code:
g=FlowNetwork()
map(g.add_vertex, 's','n','t'])
g.add_edge('s','n',4)
g.add_edge('s','n',4)
g.add_edge('s','t',4)
g.add_edge('s','t',4)
print g.max_flow('s','t')
The code incorrectly gives the flow value 12. The problem is that the self.flow variable can only handle one edge between any two nodes, whereas this is often not the case. When adding an arc (i,j) the code also adds the arc (j,i). If now the arc (j,i) is added by the user there is a problem. -- Petter ( talk) 15:20, 21 April 2010 (UTC)
The problem noted above that find_path
doesn't return a simple path can lead to a huge performance loss. In my application it took about 16 minutes to find some maximum flows in a graph. To force simple paths I added the following function:
def edgeinpath(self,edge, path):
for (pedge, presidual) in path:
if pedge == edge or pedge == edge.redge:
return True
return False
and replaced
if residual > 0 and not (edge,residual) in path:
with
if residual > 0 and not self.edgeinpath(edge, path):
This reduced the running time to under 3 seconds. Wouter - 12:40, 18 August 2010 (UTC) âPreceding unsigned comment added by 212.19.199.55 ( talk)
Is it just me or does this code look more like Erlang than Python? There's lots of tail recursion, pattern matching, list concatenation, etc, in this code. All of which are common programming practice in Erlang. â Preceding unsigned comment added by 75.92.222.10 ( talk) 04:37, 3 November 2010 (UTC)
I wonder why all my citations were placed in the "Notes" section. Is this an error that needs to be fixed? 09:21, 27 March 2015 (UTC) Kapil.xerox ( talk) 09:21, 27 March 2015 (UTC)
The EdmondsâKarp algorithm is merely an implementation of Ford-Fulkerson that specifies that the augmenting path should be found by breadth-first search. The article on Edmonds-Karp is WP:Semi-duplicate and contains largely similar content, all of which really should be in this article. Merge Edmonds-Karp into this article? IntGrah ( talk) 22:51, 12 April 2024 (UTC)
This Â
level-5 vital article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
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)
The middle arrow from should point from C to B, not from B to C.
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)
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  : 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)
Svend 11:36, 03 September 2011 (UTC)
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)
Isn't this more like the EdmondsâKarp algorithm? I thought the Ford Fulkerson keeps the selection of the paths unspecified... â Preceding unsigned comment added by 2001:9E8:1120:8C00:386F:F73E:7DE:BE89 ( talk) 19:34, 3 April 2024 (UTC)
The python code is useless without an example call. In particular, it is not clear how to instantiate the class (and why should it be a class anyway). â Preceding unsigned comment added by 2001:9E8:1120:8C00:386F:F73E:7DE:BE89 ( talk) 09:31, 3 April 2024 (UTC)
An anon made the following comment on the python program. Someone should check it.
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)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)
The following example demonstrates a bug in the code:
g=FlowNetwork()
map(g.add_vertex, 's','n','t'])
g.add_edge('s','n',4)
g.add_edge('s','n',4)
g.add_edge('s','t',4)
g.add_edge('s','t',4)
print g.max_flow('s','t')
The code incorrectly gives the flow value 12. The problem is that the self.flow variable can only handle one edge between any two nodes, whereas this is often not the case. When adding an arc (i,j) the code also adds the arc (j,i). If now the arc (j,i) is added by the user there is a problem. -- Petter ( talk) 15:20, 21 April 2010 (UTC)
The problem noted above that find_path
doesn't return a simple path can lead to a huge performance loss. In my application it took about 16 minutes to find some maximum flows in a graph. To force simple paths I added the following function:
def edgeinpath(self,edge, path):
for (pedge, presidual) in path:
if pedge == edge or pedge == edge.redge:
return True
return False
and replaced
if residual > 0 and not (edge,residual) in path:
with
if residual > 0 and not self.edgeinpath(edge, path):
This reduced the running time to under 3 seconds. Wouter - 12:40, 18 August 2010 (UTC) âPreceding unsigned comment added by 212.19.199.55 ( talk)
Is it just me or does this code look more like Erlang than Python? There's lots of tail recursion, pattern matching, list concatenation, etc, in this code. All of which are common programming practice in Erlang. â Preceding unsigned comment added by 75.92.222.10 ( talk) 04:37, 3 November 2010 (UTC)
I wonder why all my citations were placed in the "Notes" section. Is this an error that needs to be fixed? 09:21, 27 March 2015 (UTC) Kapil.xerox ( talk) 09:21, 27 March 2015 (UTC)
The EdmondsâKarp algorithm is merely an implementation of Ford-Fulkerson that specifies that the augmenting path should be found by breadth-first search. The article on Edmonds-Karp is WP:Semi-duplicate and contains largely similar content, all of which really should be in this article. Merge Edmonds-Karp into this article? IntGrah ( talk) 22:51, 12 April 2024 (UTC)