| /* #define DEBUG1 */ |
| /* #define DEBUG2 */ |
| #include "route.h" |
| #include "23tree.h" |
| extern TNODEPTR netRoot ; |
| TNODEPTR indexRoot ; |
| int treeSize ; |
| int pathIndex ; |
| extern int bareMinimum ; |
| |
| extern void tinsert( TNODEPTR *root , int value , int property ); |
| extern void recursePath( int dsptr , int atptr , int attachPt, int addEquivs); |
| extern void tpop( TNODEPTR *root , TNODEPTR *node , int *value , |
| int *property); |
| extern int mshortest( int source , int soleTarget ); |
| extern void tdelete( TNODEPTR *root , int value , int property ); |
| extern void tmax( TNODEPTR *root , TNODEPTR *node , int *value , |
| int *property); |
| |
| void routenet( int segments , int numpnodes ) |
| { |
| |
| int i , j , savei , min , count , node , node1 , bareflag ; |
| GNODEPTR gptr , gptr1 ; |
| NNODEPTR nptr ; |
| LIST2PTR lptr ; |
| TNODEPTR tptr ; |
| |
| |
| if( segments > 2 ) { |
| |
| i = MAXPATHS / (segments - 1) ; |
| Mpaths = ( i > 1 ) ? i : 1 ; |
| |
| while( (pow( (double) Mpaths , (double)(segments - 1) ) > |
| 80.0 * (double) MAXPATHS ) && (Mpaths > 1) ) { |
| Mpaths-- ; |
| } |
| } else { |
| Mpaths = 1 ; |
| } |
| |
| bareflag = 0 ; |
| if( Mpaths == 1 && segments > 19 ) { |
| if( bareMinimum == 0 ) { |
| bareMinimum = 1 ; |
| bareflag = 1 ; |
| } |
| } |
| |
| indexRoot = (TNODEPTR) NULL ; |
| treeSize = 0 ; |
| for( i = 1 ; i <= 2 * MAXPATHS ; i++ ) { |
| tinsert( &indexRoot , i , 0 ) ; |
| } |
| |
| for( i = 1 ; i <= numpnodes ; i++ ) { |
| sourceList[i] = i + numnodes ; |
| delSourceList[i] = 0 ; |
| } |
| sourcePtr = numpnodes ; |
| for( i = 1 ; i <= numnodes + numpnodes ; i++ ) { |
| targetList[i] = 0 ; |
| addTargetList[i] = 0 ; |
| } |
| targetPtr = 0 ; |
| segPtr = 0 ; |
| |
| min = VLARGE ; |
| for( i = 1 + numnodes ; i <= numpnodes + numnodes ; i++ ) { |
| nptr = pnodeArray[ i - numnodes ].nodeList ; |
| for( j = 1 + numnodes ; j <= numpnodes + numnodes ; j++ ) { |
| if( i == j ) { |
| continue ; |
| } |
| if( (pnodeArray[i - numnodes].eptr != 0) && |
| (pnodeArray[j - numnodes].eptr != 0) ) { |
| if( pnodeArray[i - numnodes].eptr == |
| pnodeArray[j - numnodes].eptr ) { |
| continue ; |
| } |
| } else if( (pnodeArray[i - numnodes].eptr == 0) && |
| (pnodeArray[j - numnodes].eptr == 0) ) { |
| } else { |
| if( pnodeArray[i - numnodes].eptr != 0 ) { |
| if( pnodeArray[i - numnodes].eptr == j - numnodes ) { |
| continue ; |
| } |
| } else { |
| if( pnodeArray[j - numnodes].eptr == i - numnodes ) { |
| continue ; |
| } |
| } |
| } |
| |
| if( nptr[j].distance < min ) { |
| min = nptr[j].distance ; |
| savei = i ; |
| } |
| } |
| } |
| pathLength = 0 ; |
| pathIndex = 0 ; |
| delSourceList[1] = savei ; |
| addTargetList[1] = savei ; |
| |
| count = 0 ; |
| if( pnodeArray[ savei - numnodes ].eptr != 0 ) { |
| count = 1 ; |
| node = pnodeArray[ savei - numnodes ].eptr + numnodes ; |
| delSourceList[2] = node ; |
| addTargetList[2] = node ; |
| lptr = pnodeArray[ pnodeArray[ savei - numnodes ].eptr ].equiv ; |
| while( lptr != (LIST2PTR) NULL ) { |
| node = lptr->node + numnodes ; |
| if( node == savei ) { |
| lptr = lptr->next ; |
| continue ; |
| } |
| delSourceList[ ++count + 1 ] = node ; |
| addTargetList[ count + 1 ] = node ; |
| lptr = lptr->next ; |
| } |
| } else { |
| lptr = pnodeArray[ savei - numnodes ].equiv ; |
| while( lptr != (LIST2PTR) NULL ) { |
| node = lptr->node + numnodes ; |
| delSourceList[ ++count + 1 ] = node ; |
| addTargetList[ count + 1 ] = node ; |
| lptr = lptr->next ; |
| } |
| } |
| |
| for( i = 1 ; i <= count + 1 ; i++ ) { |
| node = addTargetList[i] ; |
| gptr = gnodeArray[node] ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == node ) { |
| gptr1->einactive = 1 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| } |
| |
| recursePath( count + 1 , 0 , 0 , count + 1 ) ; |
| |
| for( i = 1 ; i <= count + 1 ; i++ ) { |
| node = addTargetList[i] ; |
| gptr = gnodeArray[node] ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == node ) { |
| gptr1->einactive = 0 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| } |
| if( indexRoot != (TNODEPTR) NULL ) { |
| for( ; ; ) { |
| tpop( &indexRoot , &tptr , &i , &j ) ; |
| if( tptr == (TNODEPTR) NULL ) { |
| break ; |
| } |
| } |
| } |
| |
| if( bareflag == 1 ) { |
| bareMinimum = 0 ; |
| } |
| return ; |
| } |
| |
| |
| |
| void recursePath( int dsptr , int atptr , int attachPt, int addEquivs ) |
| { |
| |
| int i , j , k , l , min , dnode , savei , node , node1 , node2 , t ; |
| int numberPaths , count , numadd ; |
| int numdelete , junk , c , value , index , found , savej ; |
| int extraS , numExtra , s , *extraSlist , x ; |
| short int *dslist , *atlist ; |
| int **tempPL , pathExists , targ , from ; |
| NNODEPTR nptr ; |
| TNODEPTR junkptr , extraRoot ; |
| GNODEPTR gptr , g1ptr , gptr1 , gptr2 ; |
| LIST2PTR lptr ; |
| |
| #ifdef DEBUG1 |
| printf("\n\nTarget List:\n"); |
| for( i = 1 ; i <= targetPtr ; i++ ) { |
| printf(" %d ", targetList[i] ) ; |
| } |
| printf("\n"); |
| printf("add to targets:\n"); |
| for( i = 1 ; i <= atptr + addEquivs ; i++ ) { |
| printf(" %d ", addTargetList[i] ) ; |
| } |
| printf("\n"); |
| fflush(stdout); |
| #endif |
| |
| if( sourcePtr - dsptr == 0 ) { |
| tpop( &indexRoot , &junkptr , &pathIndex , &junk ) ; |
| savePaths[pathIndex][0] = segPtr ; |
| for( i = 1 ; i <= segPtr ; i++ ) { |
| savePaths[pathIndex][i] = segList[i] ; |
| } |
| #ifdef DEBUG1 |
| printf("pathLength:%d pathIndex:%d\n", pathLength, pathIndex); |
| for( i = 1 ; i <= segPtr ; i++ ) { |
| printf(" %d ", savePaths[pathIndex][i] ); |
| } |
| printf("\n"); |
| fflush(stdout); |
| #endif |
| tinsert( &netRoot , pathLength , pathIndex ) ; |
| treeSize++ ; |
| return ; |
| } |
| |
| extraRoot = (TNODEPTR) NULL ; |
| |
| extraSlist = (int *) malloc( (1 + EXTRASOURCES) * sizeof(int) ) ; |
| tempPL = (int **) malloc((1 + EXTRASOURCES * MAXPATHS) * sizeof(int *)); |
| for( i = 1 ; i <= EXTRASOURCES * MAXPATHS ; i++ ) { |
| tempPL[i] = (int *) malloc( 21 * sizeof(int)); |
| for( j = 0 ; j <= 20 ; j++ ) { |
| tempPL[i][j] = 0 ; |
| } |
| } |
| |
| dslist = (short int *) malloc( (1 + dsptr) * sizeof(short int) ) ; |
| for( i = 1 ; i <= dsptr ; i++ ) { |
| dslist[i] = delSourceList[i] ; |
| } |
| atlist = (short int *) malloc( (1 + atptr + addEquivs) * |
| sizeof(short int) ) ; |
| for( i = 1 ; i <= atptr + addEquivs ; i++ ) { |
| atlist[i] = addTargetList[i] ; |
| } |
| |
| |
| #ifdef DEBUG2 |
| printf("Deleted Source Node List:\n"); |
| for( i = 1 ; i <= dsptr ; i++ ) { |
| printf(" %d ", dslist[i] ) ; |
| } |
| printf("\nSource Node List (BEFORE):\n"); |
| for( i = 1 ; i <= sourcePtr ; i++ ) { |
| printf(" %d ", sourceList[i] ) ; |
| } |
| fflush(stdout); |
| #endif |
| |
| for( j = 1 ; j <= dsptr ; j++ ) { |
| dnode = dslist[j] ; |
| for( i = 1 ; i <= sourcePtr ; i++ ) { |
| if( sourceList[i] == dnode ) { |
| sourceList[i] = sourceList[sourcePtr--] ; |
| break ; |
| } |
| } |
| } |
| |
| #ifdef DEBUG2 |
| printf("\nSource Node List (AFTER):\n"); |
| for( i = 1 ; i <= sourcePtr ; i++ ) { |
| printf(" %d ", sourceList[i] ) ; |
| } |
| fflush(stdout); |
| #endif |
| |
| |
| for( j = 1 ; j <= atptr + addEquivs ; j++ ) { |
| targetList[++targetPtr] = atlist[j] ; |
| } |
| |
| if( attachPt > 0 ) { |
| for( j = 1 ; j <= atptr ; j++ ) { |
| node1 = atlist[j] ; |
| if( j == atptr ) { |
| node2 = attachPt ; |
| } else { |
| node2 = atlist[ j + 1 ] ; |
| } |
| gptr1 = gnodeArray[ node1 ] ; |
| gptr2 = gnodeArray[ node2 ] ; |
| gptr = gptr1 ; |
| while( gptr != (GNODEPTR) NULL ) { |
| if( gptr->node == node2 ) { |
| gptr->cost = VLARGE ; |
| break ; |
| } |
| gptr = gptr->next ; |
| } |
| gptr = gptr2 ; |
| while( gptr != (GNODEPTR) NULL ) { |
| if( gptr->node == node1 ) { |
| gptr->cost = VLARGE ; |
| break ; |
| } |
| gptr = gptr->next ; |
| } |
| } |
| } |
| /* ************************************************************** */ |
| |
| numExtra = 0 ; |
| numberPaths = 0 ; |
| for( extraS = 1 ; extraS <= EXTRASOURCES ; extraS++ ) { |
| if( extraS > 1 && bareMinimum ) { |
| break ; |
| } |
| min = VLARGE ; |
| found = 0 ; |
| for( i = 1 ; i <= sourcePtr ; i++ ) { |
| for( s = 1 ; s <= numExtra ; s++ ) { |
| if( extraSlist[s] == sourceList[i] ) { |
| break ; |
| } |
| } |
| if( s <= numExtra ) { |
| continue ; |
| } |
| found = 1 ; |
| node = sourceList[i] - numnodes ; |
| nptr = pnodeArray[node].nodeList ; |
| for( j = 1 ; j <= targetPtr ; j++ ) { |
| targ = targetList[j] ; |
| if( nptr[ targ ].distance < min ) { |
| |
| from = nptr[targ].from ; |
| pathExists = 0 ; |
| g1ptr = gnodeArray[ targ ] ; |
| for( ; pathExists == 0 && g1ptr != (GNODEPTR) NULL ; |
| g1ptr = g1ptr->next ){ |
| node = g1ptr->node ; |
| if( node != from ) { |
| continue ; |
| } |
| gptr = gnodeArray[node] ; |
| for( ; ; ) { |
| if( gptr->node == targ ) { |
| if( gptr->cost < VLARGE ) { |
| pathExists = 1 ; |
| } |
| break ; |
| } |
| gptr = gptr->next ; |
| } |
| } |
| |
| if( pathExists ) { |
| min = nptr[ targ ].distance ; |
| savei = sourceList[i] ; |
| savej = j ; |
| } |
| } |
| } |
| } |
| if( found == 1 ) { |
| extraSlist[ ++numExtra ] = savei ; |
| |
| #ifdef DEBUG2 |
| printf("\nselected source node: %d\n", savei ) ; |
| fflush(stdout); |
| #endif |
| |
| i = numberPaths ; |
| numberPaths += mshortest( savei , savej ) ; |
| for( i++, l = 1 ; i <= numberPaths ; i++, l++ ) { |
| if( pathList[l][0] + 1 > 20 ) { |
| free( (int *) tempPL[i] ) ; |
| tempPL[i] = (int *) malloc( (pathList[l][0] + 2) * |
| sizeof(int)); |
| } |
| for( j = 0 ; j <= pathList[l][0] + 1 ; j++ ) { |
| tempPL[i][j] = pathList[l][j] ; |
| } |
| tinsert( &extraRoot , tempPL[i][j - 1] , i ) ; |
| } |
| } |
| } |
| /* ************************************************************** */ |
| s = ( numberPaths >= Mpaths ) ? Mpaths : numberPaths ; |
| for( l = 1 ; l <= s ; l++ ) { |
| tpop( &extraRoot , &junkptr , &junk , &j ) ; |
| k = tempPL[j][0] ; |
| |
| #ifdef DEBUG2 |
| printf("Spill it: "); |
| for( i = 1 ; i < k ; i++ ) { |
| addTargetList[i] = tempPL[j][i] ; |
| printf(" %d ", tempPL[j][i] ) ; |
| } |
| printf("\n"); |
| fflush(stdout); |
| #else |
| for( i = 1 ; i < k ; i++ ) { |
| addTargetList[i] = tempPL[j][i] ; |
| } |
| #endif |
| |
| numdelete = 0 ; |
| numadd = k - 1 ; |
| for( i = 1 ; i < k ; i++ ) { |
| if( addTargetList[i] > numnodes ) { |
| delSourceList[ ++numdelete ] = addTargetList[i] ; |
| } |
| } |
| count = 0 ; |
| for( i = 1 ; i <= numdelete ; i++ ) { |
| savei = delSourceList[i] ; |
| if( pnodeArray[ savei - numnodes ].eptr != 0 ) { |
| node = pnodeArray[ savei - numnodes ].eptr + numnodes ; |
| for( t = 1 ; t <= numdelete + count ; t++ ) { |
| if( node == delSourceList[t] ) { |
| break ; |
| } |
| } |
| if( t > numdelete + count ) { |
| delSourceList[ numdelete + ++count ] = node ; |
| addTargetList[ numadd + count ] = node ; |
| } |
| lptr = pnodeArray[ pnodeArray[savei - numnodes].eptr ].equiv; |
| } else { |
| lptr = pnodeArray[savei - numnodes].equiv; |
| } |
| while( lptr != (LIST2PTR) NULL ) { |
| node = lptr->node + numnodes ; |
| for( t = 1 ; t <= numdelete + count ; t++ ) { |
| if( node == delSourceList[t] ) { |
| break ; |
| } |
| } |
| if( t > numdelete + count ) { |
| delSourceList[ numdelete + ++count ] = node ; |
| addTargetList[ numadd + count ] = node ; |
| } |
| lptr = lptr->next ; |
| } |
| } |
| pathLength += tempPL[j][k + 1] ; |
| numdelete += count ; |
| numadd += count ; |
| for( i = 1 ; i <= k ; i++ ) { |
| segList[ i + segPtr ] = tempPL[j][i] ; |
| } |
| segList[ i + segPtr ] = 0 ; |
| segPtr += k + 1 ; |
| |
| for( x = numadd - count + 1 ; x <= numadd ; x++ ) { |
| node = addTargetList[x] ; |
| gptr = gnodeArray[node] ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == node ) { |
| gptr1->einactive = 1 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| } |
| |
| recursePath( numdelete , numadd - count , tempPL[j][k] , count ) ; |
| |
| segPtr -= k + 1 ; |
| pathLength -= tempPL[j][k + 1] ; |
| |
| for( x = numadd - count + 1 ; x <= numadd ; x++ ) { |
| node = addTargetList[x] ; |
| gptr = gnodeArray[node] ; |
| for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) { |
| node1 = gptr->node ; |
| gptr1 = gnodeArray[node1] ; |
| for( ; ; ) { |
| if( gptr1->node == node ) { |
| gptr1->einactive = 0 ; |
| break ; |
| } |
| gptr1 = gptr1->next ; |
| } |
| } |
| } |
| } |
| count = treeSize - MAXPATHS ; |
| if( count > 0 ) { |
| for( c = 1 ; c <= count ; c++ ) { |
| tmax( &netRoot , &junkptr , &value , &index ) ; |
| tdelete( &netRoot , value , index ) ; |
| tinsert( &indexRoot , index , 0 ) ; |
| } |
| treeSize -= count ; |
| } |
| if( extraRoot != (TNODEPTR) NULL ) { |
| for( ; ; ) { |
| tpop( &extraRoot , &junkptr , &junk, &j ) ; |
| if( junkptr == (TNODEPTR) NULL ) { |
| break ; |
| } |
| } |
| } |
| |
| |
| for( j = 1 ; j <= dsptr ; j++ ) { |
| sourceList[++sourcePtr] = dslist[j] ; |
| } |
| |
| #ifdef DEBUG2 |
| printf("\nSource Node List (AFTER End of Recurse):\n"); |
| for( i = 1 ; i <= sourcePtr ; i++ ) { |
| printf(" %d ", sourceList[i] ) ; |
| } |
| printf("\n"); |
| fflush(stdout); |
| #endif |
| |
| |
| targetPtr -= atptr + addEquivs ; |
| |
| |
| if( attachPt > 0 ) { |
| for( j = 1 ; j <= atptr ; j++ ) { |
| node1 = atlist[j] ; |
| if( j == atptr ) { |
| node2 = attachPt ; |
| } else { |
| node2 = atlist[ j + 1 ] ; |
| } |
| gptr1 = gnodeArray[ node1 ] ; |
| 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 ; |
| } |
| } |
| } |
| free( (short int *) atlist ) ; |
| free( (short int *) dslist ) ; |
| free( extraSlist ) ; |
| for( i = 1 ; i <= EXTRASOURCES * MAXPATHS ; i++ ) { |
| free( (int *) tempPL[i] ) ; |
| } |
| free( (int **) tempPL ) ; |
| |
| return ; |
| } |
