# gaimc : Graph Algorithms In Matlab Code

### David Gleich (view profile)

Efficient pure-Matlab implementations of graph algorithms to complement MatlabBGL's mex functions.

test_bipartite_matching
```function test_bipartite_matching
%% Info
% David F. Gleich

% 2009-05-15: Initial version

%% empty input
val = bipartite_matching([]);

A = [5 1 1 1 1;
1 5 1 1 1;
1 1 5 1 1;
1 1 1 5 1;
1 1 1 1 5;
1 1 1 1 1];
[val m1 m2] = bipartite_matching(A);
if val ~= 25 || any(m1 ~= m2)
end

%% test triple input/output
A = ones(6,5); A = A-spdiags(diag(A),0,size(A,1),size(A,2));
[ai aj av] = find(A);
ai = [(1:5)';ai];
aj = [(1:5)';aj];
av = [5*ones(5,1);av];
[val m1 m2 mi] = bipartite_matching(av,ai,aj);
mitrue = zeros(length(av),1); mitrue(1:5)=1;
if val ~= 25 || any(m1 ~= m2) || sum(mi) ~= 5 || any(mi~=mitrue)
end

%% 100 random trials against dmperm
for t=1:100
A = sprand(500,400,5/500); % 5 nz per row
A = spones(A);
p = dmperm(A);
val = bipartite_matching(A);
if sum(p>0)~=val
error('gaimc:test_bipartite_matching','failed unweighted dmperm test');
end
end

```