graph - How can I cluster points which are connected in MATLAB? -

graph - How can I cluster points which are connected in MATLAB? -

imagine have many points of them connected , want cluster them.

please take @ next figure.

if have "connectivity matrix" of points, how can cluster them in 2 grouping (groups of connected points)?

connectivitymatrix= [1 2 1 3 2 4 2 3 2 1 3 1 3 2 3 4 4 3 4 2 5 8 5 7 5 6 6 5 6 7 7 6 7 5 7 8 8 7 8 5]

the final result should nodes of 1,2,3,4 in first group(cluster) , nodes of 5,6,7,8 in sec grouping (cluster).

here code started. implemented depth first search... rough implementation of anyway.

depth first search algorithm used traversal of trees. graphs special case of trees there leaf nodes connect root. basic algorithm depth first search so:

start @ root of tree , add together stack for each node connected root, add together onto stack , place in list of visited nodes while there still node on stack... pop off node off stack check visited nodes list. if node have visited, skip. else, visit nodes connected node popped off , add together stack

if have disconnected graphs have above, run depth first search multiple times. each time 1 cluster. after 1 depth first search result, find nodes belong 1 cluster. restart depth first search 1 time again node have not touched yet, node cluster have not visited. have 2 clusters in graph structure, have run depth first search 2 times. commonly referred finding connected components in overall graph.

to find connected components, here steps did:

create connectivity matrix initialize boolean list tells whether or not have visited node in graph initialize empty cluster list initialize empty stack contains nodes should visit. while there @ to the lowest degree 1 node need visit... find such node initialize our stack contain node while our stack not empty pop off node stack if have visited node, continue else mark visited retrieve nodes connected node remove nodes not on stack in (4) add these nodes stack , cluster list once stack empty, have list of of nodes contained in single cluster. add together cluster final list. repeat 1 - 6 until visit nodes

without farther ado, code. bear in mind not battle tested. if have graph structures generate error, that'll on own prepare :)

connectivitymatrix = [1 2 1 3 2 4 2 3 2 1 3 1 3 2 3 4 4 3 4 2 5 8 5 7 5 6 6 5 6 7 7 6 7 5 7 8 8 7 8 5]; %// find possible node ids nodeids = unique(connectivitymatrix(:)); %// flag tells if there nodes should visit nodeidlist = false(1,numel(nodeids)); %// stores our list of clusters clusterlist = {}; %// keeps track of how many clusters have counter = 1; %// stack - initialize empty stacknodes = []; %// while there @ to the lowest degree 1 node need visit while (~all(nodeidlist)) % find node stacknodes = find(nodeidlist == false, 1); % initialize our stack contain node nodescluster = stacknodes; %// while our stack not empty while (~isempty(stacknodes)) % grab node off stack , pop off node = stacknodes(end); stacknodes(end) = []; %// if have marked node visited, skip if (nodeidlist(node)) continue; end %// mark visited nodeidlist(node) = true; %// retrieve nodes connected node connectednodes = connectivitymatrix(connectivitymatrix(:,1) == node, :); nodestovisit = unique(connectednodes(:,2).'); %// remove visited visitednodes = ~nodeidlist(nodestovisit); finalnodestovisit = nodestovisit(visitednodes); %// add together cluster nodescluster = unique([nodescluster finalnodestovisit]); %// add together stack stacknodes = unique([stacknodes finalnodestovisit]); end %// add together connected components own cluster clusterlist{counter} = nodescluster; counter = counter + 1; end

once have run code, can display our clusters so:

celldisp(clusterlist) clusterlist{1} = 1 2 3 4 clusterlist{2} = 5 6 7 8

as such, cluster #1 contains nodes 1,2,3,4 while cluster #2 contains nodes 5,6,7,8.

bear in mind code work if sequentially label nodes did in diagram. can't skip label numbers (i.e. can't 1,2,4,6,9, etc. should 1,2,3,4,5).

good luck!

matlab graph connect points