Re: [Tcllib-devel] FordFulkerson

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

 Hello.

About flow problems:
- Edmond's Karp algorithm, like Lars has written, is indeed extension of
Ford's Fulkerson. The difference is as it was said, in Edmond's Karp we
search for shortest paths between s and t. Just to mention, those shortest
paths are chosen considering the smallest amount of edges between s and t,
not throughputs. So, it's like running Dijkstra on residual graph, with all
weights at edges set to 1, just for that one operation. After some thinking,
I don't see any way to omit using Dijkstra or any other path finding method
( Bellman-Ford's is worser to use in that case than Dijkstra ). However,
I've found some info saying that there is algorithm (path finding), which
suits best for flow problems - it's faster than Dijkstra for rare networks
and for typical flow problems even for complete networks. It was called PDM,
so I have to review it and find some more info about it to say more about is
it worth implementing it....

Maybe Lars knows anything about it? I would guess, it can be some improved
version of e.g. Dijkstra, adapted for flow problems.

So, I think I'm going to extend Ford-Fulkerson into Edmond's Karp (
actually, it's already done ).

- min cost flow problems - actually, we've got one algorithm in timeline for
that: Busacker-Gowen ( already implemented,just have to do some more tests )

- another extension is Dinic method combined with Malhotra-Kumar-Maheshwari
algorithm ( which finds blocking flow ). It's another way for finding max
flow in flow networks. As far as I know, there is also Dinic's algorithm for
finding blocking flows, so actually, that also can be chosen... Both
algorithms (Dinic and Malhotra-Kumar-Maheshwari) are now in timeline, but
regarding situation with doubling algorithms that solve the same problems, I
proposed something other ( Set Cover, SSS ). Another option, if you don't
like to have another max-flow algorithm, can be just doing blocking flow
algorithm ( on the other hand, doing the max flow when we've got blocking
flows won't take long...). Or doing all of flow problems, and maybe
replacing something else with Set Cover and SSS. So anyway there can be a
lot of combinations:)


Tomorrow, I'm going to send the code containing all corrections mentioned in
previous mails , Busacker Gowen Implementaion , extension to Edmond's Karp
and also some more test cases.


Best Regards,
Michal Antoniewski