# MatlabBGL

### David Gleich (view profile)

30 Apr 2006 (Updated )

MatlabBGL provides robust and efficient graph algorithms for Matlab using native data structures.

max_flow(A,u,v,varargin)
function [flowval cut R F] = max_flow(A,u,v,varargin)
% MAX_FLOW Compute the max flow on A from u to v.
%
% flowval=max_flow(A,u,v) computes the maximum flow on the network defined by
% the adjacency structure A, with source u and sink v.
%
% [flowval cut R F] = max_flow(A,u,v) returns the maximum flow in the
% network A with source u and sink v as well as additional information.
% For each vertex on the source side of the mincut, mincut(i) = 1,
% for each vertex on the sink side, mincut(i) = -1.
% R is the residual graph.  R(i,j) is the amount of unused capacity
% on edge (i,j).  F is the flow graph, F(i,j) is the amount of used
% capacity on edge (i,j).  F, A, and R satisfy the relationship A = F + R.
%
% The optional parameter algname specifies the algorithm used to compute
% the maximum flow.  For reference, the push relabel method is likely the
% best general purpose algorithm.  The Edmunds-Karp algorithm
%
% ... = max_flow(A,...) takes a set of
% key-value pairs or an options structure.  See set_matlab_bgl_options
% for the standard options.
%   options.algname: the max flow/min cut algorithm
%     [{'push_relabel'} | 'edmunds_karp' | 'kolmogorov']
%   options.fix_diag: remove any diagonal entries [0 | {1}]
%
% Note: the values on A are interpreted as integers, please round them
% the values in A.
%
% Example:
%    max_flow(A,1,8)

% David Gleich

%% History
%  2006-04-16: Initial version
%    Fixed transpose option to implement the pretranspose
%    Fixed documentation bug
%  2007-07-09: Added non-negative edge capacities check
%  2008-09-23: Fixed "check" changing the input (Bug #273796)
%  2008-10-07: Changed options parsing
%%

[trans check full2sparse] = get_matlab_bgl_options(varargin{:});
if full2sparse && ~issparse(A), A = sparse(A); end

options = struct('algname', 'push_relabel','fix_diag',1);
options = merge_options(options, varargin{:});

% no negative capacities and no diagonal entries allowed
if options.fix_diag, A = A - diag(diag(A)); end
if check, check_matlab_bgl(A,struct('noneg',1,'nodiag',1)); end

% max_flow will transpose the data inside

% but ~trans means the input is already transposed, so pre-transpose
if ~trans, A = A'; end

n = size(A,1);

if nargout == 2
[flowval cut] = max_flow_mex(A,u,v,lower(options.algname));
elseif nargout >= 3
[flowval cut ri rj rv] = max_flow_mex(A,u,v,lower(options.algname));

% If anyone needs this operation to be more efficient, send me email,
% and I can make max_flow_mex return this more efficiently.
R = sparse(ri,rj,rv,n,n);
if ~trans
R = R';
end
else
flowval = max_flow_mex(A,u,v,lower(options.algname));
end

if nargout >= 4
F = A - R;
end