How to group connected pairs

Hi, I have a serie of recording instruments and I compute the correlation between the measurements of each instrument pair. This gives a square upper-triangular matrix of correlation coefficients (call it "cc"). I want to select the instruments that corresponds to correlation coefficients over some threshold "T".

[ir,ic]=find(cc>T);

This gives the row and column index of all the pairs of instrument that satisfy my condition. However, I want to add a consistency constraint, namely, I want to identify only the "connected pairs". For example, if I have the pairs (1,2), (2,3), (5,8),(8,10),(8,11),(11,6), (14,15), then I have the following groups of connected instruments: [1,2,3], [5,6,8,10,11] and [14,15].

I tried something like this, as a start:

pp=[ir,ic];
ccpairs=zeros(length(ir),length(ir));
for ip1=1:size(pp,1)-1   
    for ip2=ip1+1:size(pp,1)        
        if ~isempty(intersect(pp(ip1,:),pp(ip2,:)))
            ccpairs(ip1,ip2)=1
        end
    end
end

However, if I have more than 1 group with more than 2 connected instruments, then I would need to set ccpairs(ip1,ip2) to a different index so I can identify the groups. This double for loop is also very slow for the number of pairs I usually get (>100).

Does anybody have an idea of how to do this efficiently?

Answer 1

[Kelly Kearney]

There are several graph theory-related entries on the FEX that provide connected components algorithms. This one is a nice, self-contained version that I've used before.

% Example data

sub = [1 2; 2 3; 5 8; 8 10; 8 11; 11 6; 14 15]; 
ir = sub(:,1);
ic = sub(:,2);

% Find the connected components

nval = length(ir);
nnode = max([ir; ic]);

adj = sparse(ir, ic, ones(nval,1), nnode, nnode);

lbl = graph_connected_components(adj);

grp = accumarray(lbl', (1:nnode)', [max(lbl) 1], @(x) {x});

[Genevieve]

Elegant solution. It does exactly what I need. Thank you very much!