Archived

This topic is now archived and is closed to further replies.

bishop_pass

Dinic algo: max flow of graph; byproduct is min vertex cut

Recommended Posts

Over the course of a year or so, I have been trying (not very hard) to either implement the Dinic algorithm, find a public domain implementation which is clean, robust, and not memory thrashing. It just seems that the older I get, the less motivated I am to really dig deep into these relatively complex algorithms, especially when the research material available on them is not really pervasive. I used to be hardcore when it came to going to the ends of the Earth to find the last detail on implementing something, and then staying glued to the monitor to the early hours in the morning making it work. I just don''t seem to do tht anymore. So, if anyone is interested in helping me, or finding a good robust implementation, feel free to do so. I have found two implementations. One I didn''t like, and the other I am working on getting it to compile as I type this. Given an undirected graph, one can create a directed graph from that by creating a duplicate vertex (a1, a2) for every vertex (a) in the undirected graph. Then create the following links in the directed graph: a1->a2, (call these internal links) and for every link in the undirected from a to b, create b2->a1 and a2->b1 (call these external links). Given the directed graph, use the Dinic algorithm to compute the maximum flow on it. After that, all of the internal links with maximum flow are the vertices which were derived from the undirected graph now represent the minimum vertex cut. Or so it goes something like that... A minimum vertex cut provides a minimal communication conduit between partitions in the graph, having many applications. For one thing, it breaks computation of a global problem into partitions, only requiring communication between the partitions through the vertex separators, which is a subset of the entire graph, and thus reduced data or a reduced language for communication.

Share this post


Link to post
Share on other sites
Apparently, my simple implementation of the Fulkerson-Ford method wasn''t able to solve the particular problem you''re working on?

Oh, well...

Share this post


Link to post
Share on other sites
quote:
Original post by c_wraith
Apparently, my simple implementation of the Fulkerson-Ford method wasn''t able to solve the particular problem you''re working on?

Oh, well...

Umm, not exactly. The Fulkerson-Ford algorithm isn''t nearly as efficient as the Dinic algo.

Magmai, care to elaborate? If you search on the web, you''ll find numerous ways to do a min cut based on links. But min cuts based on vertices are few and far between.

Share this post


Link to post
Share on other sites