Skip to content

Instantly share code, notes, and snippets.

@cmaes
Created September 27, 2011 00:18
Show Gist options
  • Save cmaes/1243862 to your computer and use it in GitHub Desktop.
Save cmaes/1243862 to your computer and use it in GitHub Desktop.
Compute the condensed graph of A
function [B,compindex,ci]=condense(A)
% CONDENSE Construct the condensed graph of A
%
% [B,compindex,ci] = condense(A) returns the
% condensed graph of A.
%
% Example:
% A = zeros(5,5);
% A(1,2) = 1; A(2,3) = 1; A(3,4) = 1; A(4,2) = 1; A(4,5) = 1;
% [B,compindex] = condense(A)
%
% See also COMPONENT
if ~issparse(A)
B = sparse(A);
else
B = A;
end
num_nodes = size(B,1);
[ci,sizec] = components(B);
if any(sizec >= 2)
num_components = max(ci);
R = sparse(1:num_nodes,ci,1,num_nodes,num_components);
B = R'*A*R;
B = B - diag(diag(B));
% construct component index
% compindex{i} = [u v] if nodes u and v are in component i
compindex = cell(num_components,1);
for c = 1:num_components
compindex{c} = find(ci==c);
end
else
B = A;
compindex = num2cell(1:num_nodes);
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment