Goals:

1)Understanding of network flow techniques as applied to undirected graphs.

2)Understanding of minimum cuts, which are particularly easy to obtain from most Ford-Fulkerson code. For push/relabel code you will need to traverse unsaturated edges from the source in the final residual network to determine S.

3)Understanding of cut-trees, a compact representation for cut information regardless of the chosen source and sink. For

small instances, this will be easy to check by inspection.

Requirements:

1. Write a C/C++ program to determine a cut tree for an undirected graph:

The input graph may be treated simply as a symmetric directed graph, i.e. each input edge must be represented in both directions. The provided input graphs are guaranteed to be connected. (If not, then some calls to the network flow routine would have a maxflow of zero.)

In the output cut tree, the smallest capacity on the unique path between vertices s and t gives the capacity of the minimum cut when s and t are used as the source and sink for a network flow algorithm.

The cut tree is to be found using the following algorithm

You will need maxflow code that allows arbitrary vertices as the source and sink.

2. The input will be formatted as:

The first line will have two values, n and m, giving the numbers of vertices and edges. n will not exceed 3000. m will not exceed 10000.

The next m lines will each contain three integers. The first two, the vertices incident to an edge, will be in the range 0 . . . n - 1. They must be different and the file will not contain parallel edges. The third value will be a positive capacity no larger than 10000. (As an undirected graph, each line corresponds to a pair of symmetric edges.)

The input will be a connected graph.

3. The output from your program should go to standard output, not a file:

The number of output lines will be n - 1.

Each line will have the two vertices incident to an an edge in the computed cut tree, followed by its capacity.

CuT TREE PrOGRAM MGH for s:= 2 to n do begin Compute a minimum cut between nodes s and t pls] in G; let X be the set of nodes on the s side of the cut. Output the maximum s, t flow value f(s, t) f1 [s]:= f (s, t); for i:=1 to n do if (iOS and i is in X and p[i]=t) then p[i] :=s; if (plt] is in X) then begin pls-plt] p[t] := s ; t); f1[t]:= f (s, end end