Gomory - HU Tree of minimum cuts

Program written by: Eran Sagi. ( 1999 on SunOS)

Supervisor : Prof. Yefim Dinitz.

Describtion

The algorithm finds the minimal cuts betweem any pairs in graph. At the start The algorithm chooses two nodes and calculates the minimal cut between them and the min cut groups. These groupes are beeing separating into two graphs and the algorithm remembers the minimal cut between them. Now in every iteration the algorithm chooses two nodes from the same group and calculates the minimal cut between them, taking in acount the other groups as a single dot (node), which the maximal flow to and from it (dot) is the maximal flow that was found in one of the previous iterations. At the end of the algorithm The Gomory - HU tree is built. That tree represent the maximal flow between all two pairs in the graph, which is the minimal edge capacity of the path between those to edges.


Few figures and explanations:

Figure 1: The max flow is 6 and the min cut is marked as the red edges.

Figure 2: The graph has been separated into two parts by the new blue edge that represents the min cut. The next step is the next iteration.

Figure 3: This is few steps forward. It's equivalent to figue 2. After few more iterations we will get the graph with 5 minimum cuts.

Figure 4: This is few steps forward. The final tree is represented by the green edges.

Figure 5: By selecting nodes 0 and 5 we see that the red edges are the minimal edges in the blue-red path between those nodes. The red edge between nodes 3 and 4 separates the Vertexes into two groups: {3,5} and {0,1,2,4}. The min weight of the red cuts is 6 (This is the reason why the minimum cut between the nodes is 6, check this in figure 1 above).

 


Download

* After download the filename.tar.gz , you need to extract it by:

1. gunzip filename.tar.gz

2. tar xvf filename.tar

3. now you have an executable filename and examples.

* For your knowledge: while executing the program, at certain steps you must press 3 times on the space, to proceed to the next iteration.