%% Minimum Cut Computation
% Create and plot a weighted graph. The edge weights represent flow capacities.

s = [1 1 2 3 3 4 4 5 5];
t = [2 3 3 2 5 5 6 4 6];
weights = [0.77 0.44 0.67 0.69 0.73 2 0.78 1 1];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight,'Layout','layered')

%
% Find the maximum flow and minimum cut of the graph.

[mf,~,cs,ct] = maxflow(G,1,6)

%
% Plot the minimum cut, using the cs nodes as sources and the ct nodes as sinks. Highlight the cs nodes as red and the ct nodes as green. Note that the weight of the edge that connects these two sets of nodes is equal to the maximum flow.

H = plot(G,'Layout','layered','Sources',cs,'Sinks',ct, ...
    'EdgeLabel',G.Edges.Weight);
highlight(H,cs,'NodeColor','red')
highlight(H,ct,'NodeColor','green')

% Copyright 2015 The MathWorks, Inc.