Graph mining matlab

Question

Hi guys,

I have written some matlab code for image analysis that searches for clusters in an image and that builds an adjacency matrix for those clusters, discribing which clusters are touiching eachother in the image.

I can use this adjacency matrix to derive a graph.

For completion of my algorithm I would now have to mine that graph for all nodes of a maximum degree of 2 where the node index is either higher than that of its neigbor (when the degree is 1) or between the indexes of its two neighbors.

Basically as in the image here:

I need to do so in matlab and it is important to know that my try is available as an adjacency matrix looking like:

1 2 3 4

1 0 0 1 1

2 0 0 0 1

3 1 0 0 1

4 1 1 1 0

Probably its quite simple but I just don't see the solution...

Answer 1

Here's my attempt at this:

%# adjacency matrix
M = [0 0 1 1; 0 0 0 1; 1 0 0 1; 1 1 1 0];

%# degree == 1
N = find(sum(M,2) == 1);            %# nodes with degree(N)==1
nodes1 = N(N>find(M(N,:)));         %# nodes where its index is higher than that of its neigbor

%# degree == 2
N = find(sum(M,2) == 2);            %# nodes with degree(N)==2
Nb = zeros(numel(N),2);
for i=1:numel(N)
    Nb(i,:) = find( M(N(i),:) );    %# two-neighbors of node N(i)
end
%#Nb = sort(Nb,2);
nodes2 = N(Nb(:,1)<N & N<Nb(:,2));  %# nodes where its index is between indices of its two neighbors

%# combine both results
nodes = unique([nodes1(:);nodes2(:)]);