[Tcllib-devel] FordFulkerson

[Michał A. <ant...@gm...>]

Hello.

After some fights with it, Ford-Fulkerson is finally working.... I think the
rest of flow problems will now go quicker.

Code is at SVN with new revision. It surely still needs some optimizations
and changes, but I'm going to add now more test cases, so those
optimizations should go smoothly now. And also I think it will be easier to
get familiar with whole problem, when code is availiable.

A little description:

We are given graph (weighted, directed) G, and nodes s and t, which are
source and sink for that graph.

The goal is to find the maximum flow for a flow network -> the max possible
sum of weights for edges coming out from the source node s.

I arranged it like this:
- input graph G : weights at edges are max possible throughputs for each
single edge
- of course nodes s and t at input
- there is dictionary f, which holds all currently used throghputs for each
edge ( e.g, for edge 'uv' which has maximum throughput 20, f will
hold information, that 12 of this 20 is already used ).
- subprocedure createResidualGraph: it takes at input graph G ( we need
maximum throughputs for all particular edges) and current state of
used throughputs f ( dictionary I meant line above)
This subprocedure creates a residual graph used by FordFulkerson.

In each iteration of main loop, FordFulkerson checks, if there is any
augmenting path ( just any path from source to sink ).
If there is one, it selects the maximum throughtput for that path - the
minimum value of throughtput ( weight of an edge ) considering
all edges that are contained in the path.
When maximum throughput for a path is found, we can update the dictionary f
( we increase the value of throughput for each edge in the path, by the
value we just found).

When f is found, we can create new residual graph (createResidualGraph proc)
and proceed to next iteration -> check if for that graph, any augmenting
path does exists.


Generally, algorithm looks easy, but there are some cases, I run into during
implementation, that surely must be included in test cases....

Here is the link that can be useful....there is a applet where it's possible
to run algorithm step by step for any graph:
http://links.math.rpi.edu/applets/appindex/graphtheory.html


Best Regards,
Michal Antoniewski