如何在Matlab中找到连接的组件? [英] How to find connected components in Matlab?
问题描述
数组 A =
2 3
2 5
4 8
5 6
7 8
我想得到'conidx = [2 3 5 6] and [4 7 8]'的结果.
I'd like to get the result as 'conidx = [2 3 5 6] and [4 7 8]'.
[2 3] 的值之一存在于第 2 行,
One of the values of [2 3] exists in the 2nd row,
[2 5] 的值之一存在于第 4 行,
One of the values of [2 5] exists in the 4th row,
所以[2 3]、[2 5]和[5 6]是连通的,
so [2 3], [2 5] and [5 6] are connected,
最后我可以得到 [2 3 5 6] 的连接索引.
finally I can get the connected indices as [2 3 5 6].
否则,[4 8] 的值之一存在于第 5 行,
Otherwise, one of the values of [4 8] exists in the 5th row,
所以 [4 8] 和 [7 8] 是连接的,最后我可以得到连接的索引为 [4 7 8].
so [4 8] and [7 8] are connected, finally I can get the connected indices as [4 7 8].
[3]<-->[2]<-->[5]<-->[6] 和 [4]<-->[8]<-->[7]
[3]<-->[2]<-->[5]<-->[6] and [4]<-->[8]<-->[7]
推荐答案
构建图形并使用 graphconncomp
G = sparse( A(:,1), A(:,2), 1, max(A(:)), max(A(:)) );
G = G + G.'; %' make graph undirected
[S C] = graphconncomp( G ); % find connected components
<小时>
对于那些没有生物信息学工具箱的人
我在墨西哥的 graphconncomp
实现:
graph_conn_comp.m
function [l c] = graph_conn_comp(sA)
%
% Computing connected components of an undirected graph - assuming sA is symmetric
%
% Usage:
% [l c] = graph_conn_comp(sA);
%
% Inputs:
% sA - sparse adjacency matrix (for directed graph - does not have to be symmetric)
%
% Outputs:
% l - components labels
% c - number of connected components
%
%
% Compile using:
% >> mex -O -largeArrayDims graph_conn_comp_mex.cpp
%
%
sA = spfun(@(x) ones(size(x)),sA);
if ~isequal(sA, sA')
[ii jj] = find(sA);
sA = sparse([ii jj],[jj ii], ones(1, 2*numel(ii)), size(sA,1), size(sA,2));
end
[l c] = graph_conn_comp_mex(sA);
l = double(l); % make it compatible of the rest of Matlab
<小时>
graph_conn_comp_mex.cpp
使用
>> mex -largeArrayDims -O graph_conn_comp_mex.cpp
#include "mex.h"
#include <string.h> // for memset
/*
* Computing connected components of an undirected graph - assuming sA is symmetric
*
* Usage:
* [l c] = graph_conn_comp_mex(sA);
*
* Inputs:
* sA - sparse adjacency matrix (for directed graph - does not have to be symmetric)
*
* Outputs:
* l - components labels
* c - number of connected components
*
*
* Compile using:
* >> mex -O -largeArrayDims graph_conn_comp_mex.cpp
*
*/
#line __LINE__ "graph_conn_comp_mex"
#define STR(s) #s
#define ERR_CODE(a,b) a ":" "line_" STR(b)
// inputs
enum {
AIN = 0,
NIN };
// outputs
enum {
LOUT = 0,
COUT,
NOUT };
void
ConnComp(const mxArray* sA, unsigned int* pl, const double* pnc, mwIndex start_node);
mwIndex
FindUnLabeled(unsigned int* pl, mwIndex n);
void mexFunction(
int nout,
mxArray* pout[],
int nin,
const mxArray* pin[]) {
if ( nin != NIN )
mexErrMsgIdAndTxt(ERR_CODE(__FILE__, __LINE__),"must have %d inputs", NIN);
if (nout==0)
return;
if (nout != NOUT )
mexErrMsgIdAndTxt(ERR_CODE(__FILE__, __LINE__),"must have exactly %d output", NOUT);
if ( mxIsComplex(pin[AIN]) || !mxIsSparse(pin[AIN]) )
mexErrMsgIdAndTxt(ERR_CODE(__FILE__, __LINE__),"sA must be real sparse matrix");
if ( mxGetM(pin[AIN]) != mxGetN(pin[AIN]) )
mexErrMsgIdAndTxt(ERR_CODE(__FILE__, __LINE__),"sA must be square matrix");
mwIndex n = mxGetM(pin[AIN]); // number of variables
mwIndex ii(0);
// allocate outputs
pout[LOUT] = mxCreateNumericMatrix(1, n, mxUINT32_CLASS, mxREAL);
unsigned int* pl = (unsigned int*)mxGetData(pout[LOUT]);
memset(pl, 0, n*sizeof(unsigned int)); // set initial labels to zero
unsigned int cl = 0;
// number of components
pout[COUT] = mxCreateDoubleMatrix(1, 1, mxREAL);
double* pnc = mxGetPr(pout[COUT]);
pnc[0] = 0; // number of components
ii = 0;
do {
ConnComp(pin[AIN], pl, pnc, ii); // find conn comp
pnc[0]++;
ii = FindUnLabeled(pl, n);
} while ( ii < n );
}
mwIndex
FindUnLabeled(unsigned int* pl, mwIndex n) {
for ( mwIndex ii(0); ii<n ; ii++ ){
if ( pl[ii]==0 ) {
return ii;
}
}
return n+1;
}
void
ConnComp(const mxArray* sA, unsigned int* pl, const double* pnc, mwIndex start_node) {
mwIndex n = mxGetM(sA);
unsigned int curr_label = (unsigned int)(pnc[0]+1);
mwIndex *stack = (mwIndex*)mxMalloc( (n)*sizeof(mwIndex) );
memset(stack, 0, (n)*sizeof(mwIndex));
mwIndex sp(0); // stack pointer
// put start_node on top of stack after labeling it
pl[start_node]=curr_label;
stack[sp] = start_node;
sp++;
mwIndex* pir = mxGetIr(sA);
mwIndex* pjc = mxGetJc(sA);
mwIndex ii(0), neighbor(0);
while ( sp > 0 ) {
// pop start_label from stack
sp--;
start_node = stack[sp];
for ( ii = pjc[start_node] ; ii < pjc[start_node+1] ; ii++ ) {
neighbor = pir[ii];
if (pl[neighbor]==0) { // unlabeled
pl[neighbor] = curr_label; // label it
// push it into stack
stack[sp] = neighbor;
sp++;
} else {
if (pl[neighbor]!=curr_label)
mexErrMsgIdAndTxt(ERR_CODE(__FILE__, __LINE__),"Got mixed labeling %d <-> %d",pl[neighbor], curr_label);
}
}
}
mxFree(stack);
}
这篇关于如何在Matlab中找到连接的组件?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!