/* findInodes2.c */
#include "../MSMD.h"
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------
purpose -- to find indistinguishable nodes in the reach set
flag = 0 --> return
flag = 1 --> check out nodes that are 2-adj
flag = 2 --> check out nodes that are both 2-adj and not
note: the reach set is not changed.
created -- 96feb15, cca
modified -- 97feb07, cca
very tricky "bug"
was : sum += ip->val for subtrees
sum += IVsum(nvedge, vedges) for uncovered edges
now : sum += ip->val + 1 for subtrees
sum += IVsum(nvedge, vedges) + nvedge for uncovered edges
checksums were "wrong" due to vertex 0 adding nothing
to the checksum. beware 0-indexing.
------------------------------------------------------------------
*/
void
MSMD_findInodes (
MSMD *msmd,
MSMDinfo *info
) {
int first, flag, i, ierr, iv, iw, j, k, keepon, nlist,
nreach, nvedge, sum, vid, vchk, vcount, wid ;
int *chk, *list, *reach, *vedges, *wedges ;
IP *ip, *ipv, *ipw, *vsubtrees ;
MSMDvtx *v, *w ;
/*
---------------
check the input
---------------
*/
if ( msmd == NULL || info == NULL ) {
fprintf(stderr, "\n fatal error in MSMD_findInodes(%p,%p)"
"\n bad input\n", msmd, info) ;
exit(-1) ;
}
if ( (flag = info->compressFlag % 4) == 0 ) {
/*
---------------------------------------
no compression requested, simple return
---------------------------------------
*/
return ;
}
/*
---------------------------------
if the reach set is empty, return
---------------------------------
*/
if ( (nreach = IV_size(&msmd->reachIV)) == 0 ) {
return ;
}
/*
reach = msmd->reach ;
*/
reach = IV_entries(&msmd->reachIV) ;
if ( info->msglvl > 3 ) {
fprintf(info->msgFile, "\n inside MSMD_findInodes(%p)"
"\n reach(%d) :", msmd, nreach) ;
IVfp80(info->msgFile, nreach, reach, 10, &ierr);
fflush(info->msgFile) ;
}
/*
-------------------------------------------------------
load the front of the reach set with nodes to be tested
-------------------------------------------------------
*/
chk = IV_entries(&msmd->ivtmpIV) ;
list = reach ;
if ( flag == 1 ) {
/*
-------------------------------------------
work only with nodes adjacent to 2 subtrees
-------------------------------------------
*/
i = 0 ; j = nreach - 1 ;
while ( i <= j ) {
vid = list[i] ;
v = msmd->vertices + vid ;
if ( v->nadj != 0 || (ip = v->subtrees) == NULL
|| (ip = ip->next) == NULL || ip->next != NULL ) {
/*
--------------------------------
vertex is not 2-adj, swap to end
--------------------------------
*/
list[i] = list[j] ;
list[j] = vid ;
j-- ;
} else {
/*
--------------------------
vertex is 2-adj, keep here
--------------------------
*/
i++ ;
}
}
nlist = j + 1 ;
} else {
/*
---------------------------------
put all reached nodes in the list
---------------------------------
*/
nlist = nreach ;
}
if ( nlist == 0 ) {
return ;
}
/*
-----------------------------------------------------
compute the the checksums and count adjacent subtrees
for all vertices in the list
-----------------------------------------------------
*/
for ( k = 0 ; k < nlist ; k++ ) {
vid = list[k] ;
v = msmd->vertices + vid ;
vcount = 0 ;
sum = 0 ;
if ( info->msglvl > 4 ) {
fprintf(info->msgFile, "\n vertex %d", vid) ;
fflush(info->msgFile) ;
}
for ( ipv = v->subtrees ; ipv != NULL ; ipv = ipv->next ) {
/*
------------------------------------
add adjacent subtree to the checksum
------------------------------------
*/
sum += ipv->val + 1 ;
if ( info->msglvl > 4 ) {
fprintf(info->msgFile, "\n adjacent subtree %d, sum = %d",
ipv->val, sum) ;
fflush(info->msgFile) ;
}
vcount++ ;
}
if ( (nvedge = v->nadj) > 0 && (vedges = v->adj) != NULL ) {
sum += IVsum(nvedge, vedges) + nvedge ;
if ( info->msglvl > 4 ) {
fprintf(info->msgFile, "\n %d adjacent edges :",
nvedge) ;
IVfp80(info->msgFile, nvedge, vedges, 20, &ierr) ;
fprintf(info->msgFile, " : sum = %d", sum) ;
fflush(info->msgFile) ;
}
IVqsortUp(nvedge, vedges) ;
}
/*
-----------------
save the checksum
-----------------
*/
chk[k] = sum ;
}
if ( info->msglvl > 3 ) {
fprintf(info->msgFile, "\n before sort, list array") ;
fflush(info->msgFile) ;
IVfp80(info->msgFile, nlist, list, 80, &ierr) ;
fflush(info->msgFile) ;
fprintf(info->msgFile, "\n chk array") ;
fflush(info->msgFile) ;
IVfp80(info->msgFile, nlist, chk, 80, &ierr) ;
fflush(info->msgFile) ;
}
/*
-----------------------------------------------------
sort the vertices in the reach set by their checksums
-----------------------------------------------------
*/
IV2qsortUp(nlist, chk, list) ;
if ( info->msglvl > 3 ) {
fprintf(info->msgFile, "\n after sort, reach array") ;
IVfp80(info->msgFile, nlist, list, 80, &ierr) ;
fprintf(info->msgFile, "\n chk array") ;
IVfp80(info->msgFile, nlist, chk, 80, &ierr) ;
fflush(info->msgFile) ;
}
/*
----------------------------------------
detect and purge indistinguishable nodes
----------------------------------------
*/
for ( iv = 0 ; iv < nlist ; iv++ ) {
vid = list[iv] ;
v = msmd->vertices + vid ;
if ( v->status == 'I' ) {
/*
-----------------------------------------------------
vertex has been found indistinguishable, skip to next
-----------------------------------------------------
*/
continue ;
}
/*
---------------------------
test against other vertices
---------------------------
*/
vchk = chk[iv] ;
nvedge = v->nadj ;
vedges = v->adj ;
vsubtrees = v->subtrees ;
if ( info->msglvl > 3 ) {
fprintf(info->msgFile,
"\n checking out v = %d, vchk = %d, status = %c",
v->id, vchk, v->status) ;
fflush(info->msgFile) ;
}
/*
---------------------------------------------------
check v against all vertices with the same checksum
---------------------------------------------------
*/
if ( info->msglvl > 3 ) {
fprintf(info->msgFile, "\n checking out v = %d, status = %d",
v->id, v->stage) ;
fflush(info->msgFile) ;
}
first = 1 ;
for ( iw = iv + 1 ; iw < nlist && chk[iw] == vchk ; iw++ ) {
wid = reach[iw] ;
w = msmd->vertices + wid ;
if ( info->msglvl > 3 ) {
fprintf(info->msgFile,
"\n w = %d, status = %c, status = %d",
w->id, w->status, w->stage) ;
fflush(info->msgFile) ;
}
if ( w->status == 'I'
|| v->stage != w->stage
|| nvedge != w->nadj ) {
/*
------------------------------------
w has been found indistinguishable
or
v and w do not lie on the same stage
or
edge counts are not the same
------------------------------------
*/
continue ;
}
/*
----------------------------------------
w and v check out so far, check to see
if all vertices adjacent to w are marked
----------------------------------------
*/
if ( info->msglvl > 3 ) {
fprintf(info->msgFile,
"\n checking %d against %d", wid, vid) ;
fflush(info->msgFile) ;
}
/*
---------------------------------------------------------------
check to see if the subtree lists and edge lists are indentical
---------------------------------------------------------------
*/
info->stageInfo->ncheck++ ;
keepon = 1 ;
ipv = vsubtrees ;
ipw = w->subtrees ;
while ( ipv != NULL && ipw != NULL ) {
if ( ipv->val != ipw->val ) {
keepon = 0 ;
break ;
}
ipv = ipv->next ;
ipw = ipw->next ;
}
if ( keepon == 1 ) {
wedges = w->adj ;
for ( k = 0 ; k < nvedge ; k++ ) {
if ( vedges[k] != wedges[k] ) {
keepon = 0 ;
break ;
}
}
}
if ( keepon == 1 ) {
/*
---------------------------------------------
w and v are indistinguishable, merge w into v
---------------------------------------------
*/
if ( info->msglvl > 1 ) {
fprintf(info->msgFile,
"\n %d absorbs %d, wght = %d, status[%d] = %c",
v->id, w->id, w->wght, w->id, w->status) ;
fflush(info->msgFile) ;
}
v->wght += w->wght ;
w->wght = 0 ;
w->status = 'I' ;
w->nadj = 0 ;
w->adj = NULL ;
w->par = v ;
if ( (ipw = w->subtrees) != NULL ) {
while ( ipw->next != NULL ) {
ipw = ipw->next ;
}
ipw->next = msmd->freeIP ;
msmd->freeIP = ipw ;
w->subtrees = NULL ;
}
info->stageInfo->nindst++ ;
}
}
}
if ( info->msglvl > 4 ) {
fprintf(info->msgFile,
"\n MSMD_findInodes(%p), all done checking the nodes", msmd) ;
fflush(info->msgFile) ;
}
return ; }
/*--------------------------------------------------------------------*/
syntax highlighted by Code2HTML, v. 0.9.1