% capacity(M,z,d) expects a network's incidence matrix M, the vector of arc
% capacities z, and a demand vector d.
%
% The function returns the value the max-flow (sum over all flows in case of
% multiple flows)

function [N x val] = capacity_small(M,z,d)

% read dimensions
[n m] = size(M);

% n = number of nodes
% m = number of arcs

A = []
A = eye(m,m)
B = []
B = (eye(n) - d*d'/(d'*d))*M

f = M'*d/(d'*d)

lb = zeros(7,1);
b = zeros(6,1);

[x val] = linprog(-f,A,z,B,b,lb,[]);
val = -val
x
