← Back to branch summary

~dgleich/matlab-bgl/master

« back to all changes in this revision

Viewing changes to max_flow.m

  • Committer: David Gleich
  • Date: 2008-09-29 22:06:39 UTC
  • mfrom: (1.1.19 work)
  • Revision ID: dgleich@stanford.edu-20080929220639-4ic8mxd20lu81dla
Incorporated misc. fixes and graph layout algorithms.

Show diffs side-by-side

added added

removed removed

Lines of Context:
max_flow.m
29
29
%    load graphs/max_flow_example.mat
30
30
%    max_flow(A,1,8)
31
31
 
32
 
%
33
32
% David Gleich
34
 
% Copyright, Stanford University, 2006-2007
35
 
%
 
33
% Copyright, Stanford University, 2006-2008
36
34
 
37
 
%
38
 
% 16 April 2006
39
 
% Initial version
40
 
%
41
 
% 31 May 2006
42
 
% Added full2sparse check
43
 
%
44
 
% 8 July 2007
45
 
% Added additional algname
46
 
% Fixed transpose option to implement the pretranspose
47
 
% Fixed documentation bug
48
 
%
49
 
% 9 July 2007
50
 
% Added non-negative edge capacities check
51
 
%
 
35
%% History
 
36
%  2006-04-16: Initial version
 
37
%  2006-05-31: Added full2sparse check
 
38
%  2007-07-08: Added additional algname
 
39
%    Fixed transpose option to implement the pretranspose
 
40
%    Fixed documentation bug
 
41
%  2007-07-09: Added non-negative edge capacities check
 
42
%  2008-09-23: Fixed "check" changing the input (Bug #273796)
 
43
%%
52
44
 
53
45
[trans check full2sparse] = get_matlab_bgl_options(varargin{:});
54
 
if full2sparse && ~issparse(A)
55
 
    A = sparse(A); 
56
 
end
 
46
if full2sparse && ~issparse(A), A = sparse(A); end
57
47
 
58
48
options = struct('algname', 'push_relabel');
59
 
if ~isempty(varargin)
60
 
    options = merge_structs(varargin{1}, options);
61
 
end;
62
 
 
63
 
if check
64
 
    % the matrix cannot have nonnegative capacities
65
 
    check_matlab_bgl(A,struct('noneg',1));
66
 
end
67
 
 
 
49
if ~isempty(varargin), options = merge_structs(varargin{1}, options); end
 
50
 
 
51
% no negative capacities and no diagonal entries allowed
 
52
if check, check_matlab_bgl(A,struct('noneg',1,'nodiag',1)); end 
68
53
 
69
54
% max_flow will transpose the data inside
70
 
if ~trans
71
 
    % but that means they are passing the transposed data, so we need to
72
 
    % pre-transpose... 
73
 
    A = A';
74
 
end
75
55
 
76
 
if (check)
77
 
    % remove any non-zero diagonals
78
 
    A = A - diag(diag(A));
79
 
end
 
56
% but ~trans means the input is already transposed, so pre-transpose
 
57
if ~trans, A = A'; end
80
58
 
81
59
n = size(A,1);
82
60
 
83
 
 
84
61
if nargout == 2
85
62
    [flowval cut] = max_flow_mex(A,u,v,lower(options.algname));
86
63
elseif nargout >= 3