Doxygen Source Code Documentation
Main Page Alphabetical List Data Structures File List Data Fields Globals Search
graph_compon.c
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007 #include "mrilib.h"
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 void GRAPH_find_components( int npt, int ** gmat, int * ncom, int *** cmat )
00030 {
00031 int ** cm ;
00032 int ncm ;
00033 int cmall , cmuse ;
00034 byte * used ;
00035 int ijk , ijk_last , ncon , ii,kk,pkk,nkk,pii , *tcm ;
00036
00037 if( ncom == NULL ) return ;
00038 *ncom = 0 ;
00039 if( npt <= 0 || gmat == NULL || cmat == NULL ) return ;
00040
00041 cm = (int **) malloc( sizeof(int *) * 1 ) ;
00042 ncm = 0 ;
00043
00044 used = (byte *) calloc( npt , sizeof(byte) ) ;
00045
00046
00047
00048
00049
00050 ijk_last = 0 ;
00051 do {
00052 for( ijk=ijk_last ; ijk < npt ; ijk++ )
00053 if( gmat[ijk] != NULL && gmat[ijk][0] > 0 && !used[ijk] ) break ;
00054
00055 if( ijk == npt ) break ;
00056
00057 ijk_last = ijk+1 ;
00058
00059
00060
00061 used[ijk] = 1 ;
00062 ncon = gmat[ijk][0] ;
00063
00064 ncm++ ;
00065 cm = (int **) realloc( cm , sizeof(int *) * ncm ) ;
00066 cm[ncm-1] = (int *) malloc( sizeof(int) * (ncon+8) ) ;
00067 cmuse = 1 ;
00068 cm[ncm-1][1] = ijk ;
00069 cmall = (ncon+8) ;
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079 for( kk=1 ; kk <= cmuse ; kk++ ){
00080 pkk = cm[ncm-1][kk] ;
00081 nkk = (gmat[pkk] == NULL) ? 0
00082 : gmat[pkk][0] ;
00083
00084 for( ii=1 ; ii <= nkk ; ii++ ){
00085 pii = gmat[pkk][ii] ;
00086 if( pii >= 0 && !used[pii] ){
00087
00088
00089 if( ++cmuse >= cmall ){
00090 cmall = cmuse+32 ;
00091 cm[ncm-1] = (int *) realloc( cm[ncm-1], sizeof(int)*cmall ) ;
00092 }
00093
00094 cm[ncm-1][cmuse] = pii ;
00095 used[pii] = 1 ;
00096 }
00097 }
00098 }
00099
00100 cm[ncm-1][0] = cmuse ;
00101
00102 if( cmall > cmuse+1 )
00103 cm[ncm-1] = (int *) realloc( cm[ncm-1], sizeof(int)*(cmuse+1) ) ;
00104
00105 } while( 1 ) ;
00106
00107
00108
00109 free(used) ;
00110
00111 if( ncm == 0 ){ free(cm) ; cm = NULL ; }
00112
00113
00114
00115 for( kk=0 ; kk < ncm ; kk++ ){
00116 for( ijk=0,ii=1 ; ii < ncm ; ii++ ){
00117 if( cm[ii-1][0] < cm[ii][0] ){
00118 tcm = cm[ii-1] ; cm[ii-1] = cm[ii] ; cm[ii] = tcm ; ijk++ ;
00119 }
00120 }
00121 if( !ijk ) break ;
00122 }
00123
00124 *ncom = ncm ; *cmat = cm ; return ;
00125 }