¿Cómo encontrar componentes conectados en Matlab?

matriz A =

2 3 2 5 4 8 5 6 7 8 

Me gustaría obtener el resultado como ‘conidx = [2 3 5 6] y [4 7 8]’.


Uno de los valores de [2 3] existe en la segunda fila,

Uno de los valores de [2 5] existe en la 4ª fila,

entonces [2 3], [2 5] y [5 6] están conectados,

finalmente puedo obtener los índices conectados como [2 3 5 6].

De lo contrario, uno de los valores de [4 8] existe en la 5ª fila,

entonces [4 8] y [7 8] están conectados, finalmente puedo obtener los índices conectados como [4 7 8].

[3] [2] [5] [6] y [4] [8] [7]

construir un gráfico y usar graphconncomp

 G = sparse( A(:,1), A(:,2), 1, max(A(:)), max(A(:)) ); G = G + G.'; %' make graph undirected [SC] = graphconncomp( G ); % find connected components 

Para aquellos de ustedes que no tienen caja de herramientas bioinformática

Mi implementación de graphconncomp en mex:


código de graph_conn_comp.m

 function [lc] = graph_conn_comp(sA) % % Computing connected components of an undirected graph - assuming sA is symmetric % % Usage: % [lc] = 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 [lc] = graph_conn_comp_mex(sA); l = double(l); % make it compatible of the rest of Matlab 

código para graph_conn_comp_mex.cpp que se comstackrá en matlab usando

 >> mex -largeArrayDims -O graph_conn_comp_mex.cpp #include "mex.h" #include  // for memset /* * Computing connected components of an undirected graph - assuming sA is symmetric * * Usage: * [lc] = 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 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); } 

Para aquellos de ustedes que no tienen graphconncomp y no quieren comstackr la función mex de Shai. He publicado un reemplazo de matlab puro para graphconncomp como parte de gptoolbox

 function [S,C] = conncomp(G) [p,q,r] = dmperm(G'+speye(size(G))); S = numel(r)-1; C = cumsum(full(sparse(1,r(1:end-1),1,1,size(G,1)))); C(p) = C; end 

También es ~ 10 veces más rápido que graphconncomp para graphconncomp grandes y dispersas.