Re: [Tcllib-devel] FordFulkerson

[Andreas K. <and...@ac...>]

Lars Hellström wrote:
> 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.

Ok. Thanks for the clarification. I guess I was misguided by the examples I 
have seen, or remember to have seen, which all had source only outgoing and 
sink only incoming.

>> 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.)

Heh.

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

Right, per your clarification. This leaves only

	Are s and t nodes of G ?

as check.

>>  > 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),

Can you explain how the weights have to be assigned in the residualG to not 
make this a shortest path ?

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

Interesting.

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

Heh.

> 
> 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).

Will take a look.

Andreas.