| /* #define DEBUG */ |
| #include "route.h" |
| #include "23tree.h" |
| extern int bareMinimum ; |
| extern int doCompaction ; |
| extern int finalShot ; |
| |
| extern void tinsert( TNODEPTR *root , int value , int property ); |
| extern void tpop( TNODEPTR *root , TNODEPTR *node , int *value , |
| int *property); |
| extern void tdelete( TNODEPTR *root , int value , int property ); |
| extern int prestrict( short int *ptr, int p , int source , int target ); |
| extern void tmax( TNODEPTR *root , TNODEPTR *node , int *value , |
| int *property); |
| |
| void greduce(short int *ptr,int p,int ex0,int ex1,int ex2,int ex3,int ex4 ); |
| void gunreduce(short int *ptr,int p,int ex0,int ex1,int ex2,int ex3,int ex4 ); |
| |
| /*ARGSUSED*/ |
| int mshortest( int source , int soleTarget ) |
| { |
| |
| int target , i , j , k , d , t , distance , from , index , pindex , c ; |
| int numberPaths , p , q , *eptr , exnum , tree2size ; |
| int ex[5] , number , junk , treeSize , value , count , targetLimit ; |
| int wasInactive , node1 , xindex , targetCount , foo ; |
| int initialCount , initialLimit ; |
| short int dummy[2] ; |
| short int *ptr ; |
| NNODEPTR nptr ; |
| TNODEPTR root1 , node , rsave , junkptr , indexRoot , targetRoot ; |
| TNODEPTR initialRoot ; |
| GNODEPTR gptr , gptr1 ; |
| |
| rsave = (TNODEPTR) NULL ; |
| indexRoot = (TNODEPTR) NULL ; |
| targetRoot = (TNODEPTR) NULL ; |
| initialRoot = (TNODEPTR) NULL ; |
| |
| for( i = 1 ; i <= 2 + 2 * Mpaths ; i++ ) { |
| tinsert( &indexRoot , i , 0 ) ; |
| } |
| treeSize = 0 ; |
| tree2size = 0 ; |
| wasInactive = 0 ; |
| nptr = pnodeArray[ source - numnodes ].nodeList ; |
| |
| for( t = 1 ; t <= targetPtr ; t++ ) { |
| target = targetList[t] ; |
| tinsert( &initialRoot , nptr[target].distance , t ) ; |
| } |
| |
| initialCount = 0 ; |
| initialLimit = ((int)(0.1 * (double) targetPtr) + 1) + 2 * Mpaths ; |
| |
| if( initialLimit > targetPtr ) { |
| initialLimit = targetPtr ; |
| } |
| if( bareMinimum ) { |
| if( finalShot == doCompaction ) { |
| initialLimit = 2 ; |
| } else { |
| initialLimit = 1 ; |
| } |
| } |
| |
| while( initialCount < initialLimit ) { |
| tpop( &initialRoot , &junkptr , &foo , &t ) ; |
| if( junkptr == (TNODEPTR) NULL ) { |
| break ; |
| } |
| target = targetList[t] ; |
| gptr = gnodeArray[target] ; |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == target ) { |
| if( gptr1->einactive == 1 ) { |
| gptr1->einactive = 0 ; |
| wasInactive = 1 ; |
| gptr = gptr->next ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == target ) { |
| gptr1->einactive = 0 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| } |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| dummy[1] = source ; |
| d = prestrict( dummy , 1 , source , target ) ; |
| if( wasInactive == 1 ) { |
| gptr = gnodeArray[target] ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == target ) { |
| gptr1->einactive = 1 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| wasInactive = 0 ; |
| } |
| if( d >= 0 ) { |
| tinsert( &targetRoot , nptr[target].temp , t ) ; |
| initialCount++ ; |
| } |
| } |
| if( initialRoot != (TNODEPTR) NULL ) { |
| for( ; ; ) { |
| tpop( &initialRoot , &junkptr , &foo , &t ) ; |
| if( junkptr == (TNODEPTR) NULL ) { |
| break ; |
| } |
| } |
| } |
| targetLimit = Mpaths ; |
| targetCount = 0 ; |
| |
| while( targetCount < targetLimit ) { |
| |
| tpop( &targetRoot , &junkptr , &foo , &t ) ; |
| if( junkptr == (TNODEPTR) NULL ) { |
| break ; |
| } |
| |
| numberPaths = 0 ; |
| root1 = (TNODEPTR) NULL ; |
| |
| |
| target = targetList[t] ; |
| gptr = gnodeArray[target] ; |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == target ) { |
| if( gptr1->einactive == 1 ) { |
| gptr1->einactive = 0 ; |
| wasInactive = 1 ; |
| gptr = gptr->next ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == target ) { |
| gptr1->einactive = 0 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| } |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| dummy[1] = source ; |
| d = prestrict( dummy , 1 , source , target ) ; |
| if( d < 0 ) { |
| if( wasInactive == 1 ) { |
| gptr = gnodeArray[target] ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == target ) { |
| gptr1->einactive = 1 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| wasInactive = 0 ; |
| } |
| continue ; |
| } |
| distance = nptr[target].temp ; |
| |
| targetCount++ ; |
| from = nptr[target].from2 ; |
| number = 1 ; |
| tempArray[1] = target ; |
| while( from != 0 ) { |
| tempArray[++number] = from ; |
| from = nptr[from].from2 ; |
| } |
| tpop( &indexRoot , &junkptr , &pindex , &junk ) ; |
| |
| #ifdef DEBUG |
| printf("pindex:%d\n",pindex); |
| fflush(stdout); |
| #endif |
| |
| pathArray[pindex].p = 1 ; |
| pathArray[pindex].q = number - 1 ; |
| pathArray[pindex].excluded = 0 ; |
| for( j = 1 ; j <= number ; j++ ) { |
| pathArray[pindex].nodeset[ number - j + 1 ] = tempArray[j] ; |
| } |
| tinsert( &root1 , distance , pindex ) ; |
| treeSize++ ; |
| |
| for( ; ; ) { |
| tpop( &root1 , &node , &distance , &index ) ; |
| treeSize-- ; |
| if( node == (TNODEPTR) NULL ) { |
| break ; |
| } |
| tinsert( &rsave , distance , index ) ; |
| tree2size++ ; |
| if( ++numberPaths >= Mpaths ) { |
| break ; |
| } |
| ptr = pathArray[index].nodeset ; |
| p = pathArray[index].p ; |
| q = pathArray[index].q ; |
| exnum = pathArray[index].excluded ; |
| eptr = pathArray[index].exlist ; |
| if( p == q ) { |
| ex[0] = exnum + 1 ; |
| for( i = 1 ; i <= exnum ; i++ ) { |
| ex[i] = eptr[i] ; |
| } |
| ex[ ex[0] ] = ptr[ p + 1 ] ; |
| |
| greduce( ptr, p, ex[0], ex[1], ex[2], ex[3], ex[4] ) ; |
| d = prestrict( ptr, p , source , target ) ; |
| gunreduce( ptr, p, ex[0], ex[1], ex[2], ex[3], ex[4] ) ; |
| if( d < 0 ) { |
| continue ; |
| } |
| distance = nptr[target].temp + d ; |
| from = nptr[target].from2 ; |
| number = 1 ; |
| tempArray[1] = target ; |
| while( from != 0 ) { |
| tempArray[++number] = from ; |
| from = nptr[from].from2 ; |
| } |
| for( i = p - 1 ; i >= 1 ; i-- ) { |
| tempArray[++number] = ptr[i] ; |
| } |
| tpop( &indexRoot , &junkptr , &pindex , &junk ) ; |
| |
| #ifdef DEBUG |
| printf("pindex:%d\n",pindex); |
| fflush(stdout); |
| #endif |
| |
| pathArray[pindex].p = p ; |
| pathArray[pindex].q = number - 1 ; |
| pathArray[pindex].excluded = ex[0] ; |
| for( i = 1 ; i <= ex[0] ; i++ ) { |
| pathArray[pindex].exlist[i] = ex[i] ; |
| } |
| for( j = 1 ; j <= number ; j++ ) { |
| pathArray[pindex].nodeset[number - j + 1] = tempArray[j]; |
| } |
| tinsert( &root1 , distance , pindex ) ; |
| treeSize++ ; |
| |
| |
| count = treeSize - (Mpaths - numberPaths) ; |
| if( count > 0 ) { |
| for( c = 1 ; c <= count ; c++ ) { |
| tmax( &root1, &node, &value, &xindex ) ; |
| tdelete( &root1, value, xindex ) ; |
| tinsert( &indexRoot, xindex, 0 ) ; |
| } |
| treeSize -= count ; |
| } |
| |
| } else { |
| for( k = 1 ; k <= q - p + 1 ; k++ ) { |
| if( k == 1 ) { |
| ex[0] = exnum + 1 ; |
| for( i = 1 ; i <= exnum ; i++ ) { |
| ex[i] = eptr[i] ; |
| } |
| ex[ ex[0] ] = ptr[ p + 1 ] ; |
| } else { |
| ex[ ex[0] = 1 ] = ptr[ p + k ] ; |
| } |
| greduce( ptr, p + k - 1, |
| ex[0], ex[1], ex[2], ex[3], ex[4] ) ; |
| d = prestrict( ptr, p + k - 1 , source , target ) ; |
| gunreduce( ptr, p + k - 1, |
| ex[0], ex[1], ex[2], ex[3], ex[4] ) ; |
| if( d < 0 ) { |
| continue ; |
| } |
| distance = nptr[target].temp + d ; |
| from = nptr[target].from2 ; |
| number = 1 ; |
| tempArray[1] = target ; |
| while( from != 0 ) { |
| tempArray[++number] = from ; |
| from = nptr[from].from2 ; |
| } |
| for( i = p + k - 2 ; i >= 1 ; i-- ) { |
| tempArray[++number] = ptr[i] ; |
| } |
| tpop( &indexRoot , &junkptr , &pindex , &junk ) ; |
| treeSize++ ; |
| |
| #ifdef DEBUG |
| printf("pindex:%d\n",pindex); |
| fflush(stdout); |
| #endif |
| |
| pathArray[pindex].p = p + k - 1 ; |
| pathArray[pindex].q = number - 1 ; |
| pathArray[pindex].excluded = ex[0] ; |
| for( i = 1 ; i <= ex[0] ; i++ ) { |
| pathArray[pindex].exlist[i] = ex[i] ; |
| } |
| for( j = 1 ; j <= number ; j++ ) { |
| pathArray[pindex].nodeset[number - j + 1] = |
| tempArray[j]; |
| } |
| tinsert( &root1 , distance , pindex ) ; |
| |
| |
| count = treeSize - (Mpaths - numberPaths) ; |
| if( count > 0 ) { |
| for( c = 1 ; c <= count ; c++ ) { |
| tmax( &root1, &node, &value, &xindex ) ; |
| tdelete( &root1, value, xindex ) ; |
| tinsert( &indexRoot, xindex, 0 ) ; |
| } |
| treeSize -= count ; |
| } |
| |
| } |
| } |
| } |
| count = tree2size - Mpaths ; |
| if( count > 0 ) { |
| for( c = 1 ; c <= count ; c++ ) { |
| tmax( &rsave, &node, &value, &xindex ) ; |
| tdelete( &rsave, value, xindex ) ; |
| tinsert( &indexRoot, xindex, 0 ) ; |
| } |
| tree2size -= count ; |
| } |
| |
| if( root1 != (TNODEPTR) NULL ) { |
| for( ; ; ) { |
| tpop( &root1 , &node , &distance , &index ) ; |
| if( node == (TNODEPTR) NULL ) { |
| break ; |
| } |
| } |
| } |
| treeSize = 0 ; |
| if( wasInactive == 1 ) { |
| gptr = gnodeArray[target] ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == target ) { |
| gptr1->einactive = 1 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| wasInactive = 0 ; |
| } |
| } |
| numberPaths = 0 ; |
| for( ; ; ) { |
| tpop( &rsave , &node , &distance , &index ) ; |
| if( node == (TNODEPTR) NULL ) { |
| break ; |
| } |
| ptr = pathArray[index].nodeset ; |
| k = pathArray[index].q + 1 ; |
| pathList[++numberPaths][0] = k ; |
| pathList[numberPaths][k + 1] = distance ; |
| for( i = 1 ; i <= k ; i++ ) { |
| pathList[numberPaths][i] = ptr[i] ; |
| } |
| if( numberPaths >= Mpaths ) { |
| break ; |
| } |
| } |
| if( indexRoot != (TNODEPTR) NULL ) { |
| for( ; ; ) { |
| tpop( &indexRoot , &node , &distance , &index ) ; |
| if( node == (TNODEPTR) NULL ) { |
| break ; |
| } |
| } |
| } |
| if( targetRoot != (TNODEPTR) NULL ) { |
| for( ; ; ) { |
| tpop( &targetRoot , &junkptr , &foo , &t ) ; |
| if( junkptr == (TNODEPTR) NULL ) { |
| break ; |
| } |
| } |
| } |
| |
| return( numberPaths ) ; |
| } |
| |
| |
| |
| |
| void greduce(short int *ptr,int p,int ex0,int ex1,int ex2,int ex3,int ex4 ) |
| { |
| |
| int l , node , node1 , node2 , exl[5] ; |
| GNODEPTR gptr , gptr1 , gptr2 ; |
| |
| exl[1] = ex1 ; |
| exl[2] = ex2 ; |
| exl[3] = ex3 ; |
| exl[4] = ex4 ; |
| node1 = ptr[p] ; |
| gptr1 = gnodeArray[ node1 ] ; |
| for( l = 1 ; l <= ex0 ; l++ ) { |
| node2 = exl[l] ; |
| gptr2 = gnodeArray[ node2 ] ; |
| gptr = gptr1 ; |
| for( ; ; ) { |
| if( gptr->node == node2 ) { |
| gptr->cost = VLARGE ; |
| break ; |
| } |
| gptr = gptr->next ; |
| } |
| gptr = gptr2 ; |
| for( ; ; ) { |
| if( gptr->node == node1 ) { |
| gptr->cost = VLARGE ; |
| break ; |
| } |
| gptr = gptr->next ; |
| } |
| } |
| for( l = 1 ; l < p ; l++ ) { |
| node = ptr[l] ; |
| gptr = gnodeArray[node] ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == node ) { |
| gptr1->inactive = 1 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| } |
| return ; |
| } |
| |
| |
| |
| |
| |
| void gunreduce(short int *ptr,int p,int ex0,int ex1,int ex2,int ex3,int ex4 ) |
| { |
| |
| int l , node , node1 , node2 , exl[5] ; |
| GNODEPTR gptr , gptr1 , gptr2 ; |
| |
| exl[1] = ex1 ; |
| exl[2] = ex2 ; |
| exl[3] = ex3 ; |
| exl[4] = ex4 ; |
| node1 = ptr[p] ; |
| gptr1 = gnodeArray[ node1 ] ; |
| for( l = 1 ; l <= ex0 ; l++ ) { |
| node2 = exl[l] ; |
| gptr2 = gnodeArray[ node2 ] ; |
| gptr = gptr1 ; |
| for( ; ; ) { |
| if( gptr->node == node2 ) { |
| gptr->cost = gptr->length ; |
| break ; |
| } |
| gptr = gptr->next ; |
| } |
| gptr = gptr2 ; |
| for( ; ; ) { |
| if( gptr->node == node1 ) { |
| gptr->cost = gptr->length ; |
| break ; |
| } |
| gptr = gptr->next ; |
| } |
| } |
| for( l = 1 ; l < p ; l++ ) { |
| node = ptr[l] ; |
| gptr = gnodeArray[node] ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == node ) { |
| gptr1->inactive = 0 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| } |
| return ; |
| } |