Re: [Tcllib-devel] FordFulkerson

[Lars H. <Lar...@re...>]

Andreas Kupries skrev:
> Micha? Antoniewski wrote:
>> We are given graph (weighted, directed) G, and nodes s and t, which are 
>> source and sink for that graph.
> 
> Give the suggestive naming of these two nodes, do they have special 
> requirements / constraints ?
> 
> Like, for example:
> 	"source must not have incoming arcs".
> 	"sink   must not have outgoing arcs".
> ?

No, the source is just where the flow comes from, and the sink is where 
it must go.

> Regarding the weights the wikipedia reference tells us that the
> algorithm may not converge for irrational weights ... Oh, ok, is not a
> problem for an implementation on a computer. Our 'float/double' values
> are always rational, due to finite precision.

Yes, but note that this is one of the cases where complexity estimates 
must take into account the size of the numbers given as input... But on 
second though, this probably doesn't apply here, because what has been 
implemented may well be the Edmonds--Karp algorithm rather than the 
Ford--Fulkerson algorithm! (See below.)

>  > 1311:	#s - the node that is a source for graph G
>  > 1312:	#t - the node that is a sink for graph G
>  > 1313:	#
>  > 1314:	#Output:
>  > 1315:	#Procedure returns the dictionary contaning throughputs for all edges. For
>  > 1316:	#each key ( the edge between nodes u and v in the for of list u v ) 
> there is
>  > 1317:	#a value that is a throughput for that key. Edges where throughput values
>  > 1318:	#are equal to 0 are not returned ( it is like there was no link in the 
> flow network
>  > 1319:	#between nodes connected by such edge).
>  > 1320:	#
>  > 1321:	#Reference: http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm
>  > 1322:	
>  > 1323:	proc ::struct::graph::op::FordFulkerson {G s t} {
> 
> Missing checks: Are s and t nodes of G ?
> Also, should the source s have incoming arcs ?
> Further, should sink t have outgoing arcs ?

There is no reason to limit the arcs around source or sink.

>  > 1343:		#the main loop - works till the path between source and the sink can 
> be found
>  > 1344:		while {[dict exists [struct::graph::op::dijkstra $residualG $s 
> -arcmode directed] $t]} {
> 
> 'struct::graph::op::dijkstra' can be shortened to 'dijkstra', we are in the 
> right namespace.
> 
>  > 1345:		
>  > 1346:			#setting the path from source to sink
>  > 1347:			set path [lreverse [dict get [struct::graph::op::dijkstra $residualG 
> $s -arcmode directed] $t]]

Using [dijkstra] for computing the augmenting path /probably/ means it 
will be a shortest path (though it depends on how weights are assigned 
in $residualG), and the simple choice of always using a shortest path 
is all that is needed to turn Ford--Fulkerson into Edmonds--Karp! It 
also has the effect of making the algorithm polynomial, regardless of 
the capacity sizes.

There's really no reason for tcllib to house a Ford--Fulkerson 
implementation that is not an Edmonds--Karp; were it not for historical 
factors (e.g. that Ford and Fulkerson also proved the max-flow-min-cut 
theorem), the former algorithm would just be regarded as a broken form 
of the latter, which terminates more by luck than by merit.

Lars Hellström

PS: On the matter of picking a new problem to implement an algorithm 
for, I would like to suggest Min-cost-flow 
(http://en.wikipedia.org/wiki/Minimum_cost_flow_problem).