Paul is a computer-science major at Lehigh University and president of Ahpah Software, a company working on the upcoming graphics adventure game, "Vengeance." Paul can be contacted on CompuServe at 73340,3456.
The problem of computer wiring belongs to the field of combinatorial optimization. It is analogous to the shortest-Hamiltonian-path problem except that a source/terminator rule dictates where the tour must begin and end. The computer-wiring problem is classified as NP-Hard (Lawler et al.). In order to find the optimal solution with 100 percent assurance, branching and bounding techniques must typically be used. These processes usually require inordinate program run times and are prohibitive for large numbers of pins. Therefore, heuristics that create good tours are desirable, even if the tours are sometimes suboptimal.
The two main classes of heuristics for combinatorial-optimization problems are tour creation and tour improvement. The first produces a tour without having a tour as a starting point (nearest neighbor, for example); the second improves upon an initial tour (like Lin-Kernighan). Some heuristics, such as Krolak, Felts, and Marble's man-machine approach, incorporate both classes of heuristics. This is the type of heuristic I present in this article. This new heuristic can be applied to combinatorial-optimization problems, including the traveling-salesman and vehicle-routing problems.
Underlying the computer-wiring problem is the assumption that, given a set of n pins, there are n(n--1)/2 distances between any two pins in the set. These individual distances are referred to as "wires" or "edges." The nxn matrix of wires is called the "cost matrix" and represents any notion of distance such as time, length, or cost. The value of the wire between locations i and j is noted as Cij. The objective of the computer-wiring problem is to find the set of n-1 wires in C that creates the minimum-valued serial tour through all pins. Symmetric problems have Cij=Cji for all i and j and Cii=0 for all i.
The concept of this heuristic is that although a wire is short, it is not necessarily effective to use in the tour. This notion was derived through numerous runs of the nearest-neighbor heuristic, which works as follows:
Many of the short but detrimental wires are part of a minimum spanning tree (MST) for the set of pins. The MST is the set of the shortest n-1 wires that form a jointed net that includes all pins; see Figure 2. The lengths of the edges in this figure are a measure of the Cij values.
Kruskal proves a polynomial algorithm for the MST problem. This and other algorithms do not enforce the restriction that each pin can touch a maximum of two others. To enforce this restriction, Held and Karp and Christofides use Lagrangian multipliers. Later work with Lagrangian multipliers is done by Volgenant and Jonker. Note that an MST is not always unique--problems with several wires of the same length typically have a few MSTs.
To find a pattern in the short but detrimental wires, we examined both classic and new, randomly generated problems. We found that many of the detrimental wires are MST wires that include multiply connected pins (those which have more than one wire attached to them). Wires A, B, E, G, H, J, and K in Figure 2 are examples of these.
The concepts I've discussed lead to the following heuristic for the computer-wiring problem:
Figure 3 illustrates the use of the detrimental-wire-exclusion heuristic on a set of six pins labeled p1 through p6. The 15 wires are noted as w1 through w15, where w1 is the shortest wire and w15 is the longest. Tables 1 and 2 list the pins and wires used in this example. Distances in this example are computed by the Manhattan metric (discussed on the following page.) Figure 3(a) shows a minimum spanning that uses wires w1, w2, w3, w4, and w7 to include all 6 of the pins. The number in brackets at the bottom left of the diagrams is the total length of all the wires used in the diagram. After a tree is found, all wires are marked as eligible and the subheuristic is called. The resulting tour is shown in Figure 3(b).
Since p1 is not multiply connected, move to p2. Exclude w1, w4, and w7 one at a time because they all multiply connect to p2. Figure 3(c) is the tour created without w1. Since this tour is shorter than any seen previously, w1 is permanently marked as ineligible. Figure 3(d) is the tour created without the use of w4 or w1. Since it is longer than the shortest tour, w4 is again made eligible. Figure 3(e) is the tour created without w7 or w1. Since it is the same length as the shortest seen tour, the conditions prior to the exclusion of w7 are restored. All the wires that multiply connect p2 have been tested; since p3 is not multiply connected, move to p4. Now exclude w1, w2, and w3 one at a time because they all multiply connect to p4. Since w1 is already permanently marked as ineligible, there is no need to create a new tour. Move to the next wire. Figure 3(f) is the tour created without w2 or w1. It is longer than the shortest tour, so w2 is again made eligible. Figure 3(g) is the tour created without w3 or w1. Since this tour is longer than the best tour seen, w3 is again made eligible. Since p5 and p6 are not multiply connected and p6 is the last pin, end the heuristic and return the best tour.
This example is typical of the behavior of the heuristic. A fairly good starting point, Figure 3(b), is improved upon by deleting wire w1. The more pins, the greater the improvement that can be expected, because the accuracy of the starting tour decreases as the number of pins increases.
When implementing this new heuristic, you must consider several points. For instance, when given a set of pins to connect, the pin location should be stored in the pin-data structure (when minimizing a cost matrix, this is unnecessary). The first component of the pin-data structure is a three-dimensional coordinate system for routing multilayer circuit boards. The second component should be an array of wire indexes to which each pin is connected in the minimum tree. Storing this information directly in the pin structure avoids look-up time and decreases program run time. The third component of the structure should be a ring index.
To prevent short circuits in the connection order, assign each pin its own ring index at the beginning of the heuristic. Now each wire connects to two pins, and each pin has an index. When a wire is selected, all pins with a ring index the same as that of the pin with the lower ring index of the two are set equal to the higher ring index. Prior to a wire being selected, enforce the rule that pins with the same ring index cannot be connected.
The wire structure should contain the indexes of the two pins that the wire connects, the cost of the wire, a permanent-ineligibility flag, and a temporary-ineligibility flag. Placing these flags here will avoid look-up time.
Listings One and Two provide a C implementation of this algorithm. The program compiles with Borland C without any modifications using bcc -ml -etspheur *.c. Changing <alloc.h> to <malloc.h> allows you to compile with Microsoft C. Provided electronically are the files PROB56.CTY, problem #56, and TSPHEUR.C and TSPHEUR.H, the command-line interface to the algorithm; see "Availability," page 3.
In many combinatorial-optimization problems, the cost matrix is known. In others, only a set of locations is given. The simplest way to build the cost matrix for a set of points is to use the traditional distance formula on all point pairs. In many cases, this is not an accurate indicator of the cost of traveling between the two points. Therefore, other techniques for building cost matrices are needed.
One technique is the Manhattan distance. Given any two points in three-dimensional space, the Manhattan distance between (x1, y1, z1) and (x2, y2, z2) is defined as M(p1, p2)=|x1-x2|+|y1-y2|+|z1-z2|.
This calculation is frequently used in the routing of multilayer circuit boards. In order to restrict the usage of vias (movement from one layer to another), a sufficiently large coefficient must be used on the |z1-z2| term.
Another technique involves weighted bitmaps. Given two locations on a bitmap in which each cell of the map indicates the cost and/or plausibility of using that cell, the distance between those points can be found by using a minimum-cost routing algorithm. A routing algorithm is needed when the locations to be connected have blockages between them or if certain places on the bitmap are inherently more expensive than others. For example, certain parts of a circuit board are made of more expensive material than others. Therefore, placing an etch on the less expensive space lowers the total cost of the etch.
Lower- and upper-bounding techniques are used to quantify the usefulness of the heuristic. The minimum spanning distance is the absolute lower bound; that is, a tour can never be shorter than the minimum spanning distance. The nearest-neighbor heuristic is used as an upper bound for two reasons: First, a heuristic that creates tours longer than those of the nearest-neighbor heuristic is usually not effective. Second, many circuit boards are designed so that pins that need to be connected are placed sufficiently close to one another; hence, tours created by the nearest neighbor are normally ample solutions.
In addition to the problems listed in Table 3, a series of 945 trials has been performed that includes varying densities of cities. Half of the trials include the enforcement of a source/terminator rule. Half of the trials used the Manhattan-distance calculation, and the other half used the traditional distance formula. In addition, several trials use air mileage between cities in the United States. On average, the tours generated by the detrimental-wire-exclusion heuristic were 19.1 percent longer than the minimum spanning distance; the tours generated by the nearest neighbor were 16.4 percent longer than those created by the new heuristic.
The pin locations for the listed problems have been randomly generated with an X and Y range of 30 to 830 in multiples of 10. The pin locations used in problem 56 are listed in Table 4. The tour generated for problem 56 has a length of 6161. In this problem, distances between cities are computed by the traditional distance formula.
The problems listed in Table 3 were computed on an Intel 386/25 CPU. The complete list of data indicates a run-time growth with about n2.6. This can be explained by the fact that the creation of a tour by the subheuristic usually does not require O(n2) time. Our research indicates that, typically, only the first n1.6 wires of a n2 wire list need to be examined to create a connection order for Euclidean and real-world problems.
The heuristic as described thus far excludes one wire at a time. In some cases, however, multiple-wire exclusion may lead to a slight improvement in tour length, and it can be incorporated easily. Once all wires have been excluded one at a time, they can be excluded two at a time and so forth. A loop around the calling of the subheuristic makes for a simple implementation.
The main problem with multiple-wire exclusion is that run time increases dramatically. Excluding wires one at a time has a worst case run time of O(n3). If the maximum wires to be excluded at one time is k, then there will be at least nCk calls to the subheuristic. For a fixed k of less than half of n, the worst-case run time will be O(nk+2). For instance, excluding two wires at a time leads to the number of calls to the subheuristic in Example 1. Since the worst-case run time of the subheuristic is O(n2), the total run time will be O(n4).
Although problems with only 175 pins or less were tackled, the heuristic presented here is portable and can be implemented on more powerful machines. Therefore, problems with thousands of pins can be quickly solved. Since the computer-wiring problem is similar to other combinatorial optimization problems, the heuristic can be applied to many other optimization applications.
Acknowledgments
I'd like to thank John and Charles Martino for their assistance in writing this paper.
Christofides, N. "The Shortest Hamiltonian Chain of a Graph." SIAM Journal of Applied Mathematics. Vol. 19, 1970.
Felts, W., P. Krolak, and G. Marble. "A Man-Machine Approach Toward Solving the Traveling Salesman Problem." Communications of the ACM. Vol. 14, 1971.
Held, M. and R.M. Karp. "The Traveling-Salesman Problem and Minimum Spanning Trees." Operations Research. Vol. 18, 1970.
------. "The Traveling-Salesman Problem and Minimum Spanning Trees: Part II." Operations Research. Vol. 19, 1971.
Kruskal, J.B., Jr. "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proceedings of the American Mathematical Society. Vol. 7, 1956.
Lawler, E.L., J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys (eds.). The Traveling Salesman Problem: A Guided Tour of Combinatory Optimization. New York, NY: John Wiley, 1990.
Lin, S. and B.W. Kernighan. "An Effective Heuristic Algorithm for the Traveling Salesman Problem." Operations Research. Vol. 21, 1973.
Volgenant, T. and R. Jonker. "A Branch and Bound Algorithm for the Symmetric Traveling Salesman Problem Base on the 1-Tree Relaxation." European Journal of Operations Research. Vol 9, 1982.
Figure 1 (a) A nearest-neighbor tour; (b) a much more effective tour.
Figure 2 A minimum-spanning tree.
Figure 3 (a) A minimum-spanning tree; (b) all wires are eligible; (c) exclude w1; (d) exclude w4 and w1; (e) exclude w7 and w1; (f) exclude w2 and w1; (g) exclude w3 and w1.
Num X Y 1 46 28 2 33 16 3 7 9 4 31 29 5 45 4 6 18 34
Num Pins Len 1 2--4 15 2 1--4 16 3 4--6 18 4 2--5 24 5 1--2 25 6 1--5 25 7 2--3 33 8 2--6 33 9 1--6 34 10 3--6 36 11 4--5 39 12 3--5 43 13 3--4 44 14 5--6 57 15 1--3 58
Problem Pin Min-Tree DWE Heuristic Nearest Neighbor Number Count Time Length Time Length Time Length 1 50 0.39 4103 2.97 4717 0.55 5293 2 50 0.33 4131 2.80 4698 0.49 5682 3 50 0.33 3618 3.24 4328 0.50 4583 4 50 0.33 3661 2.86 3948 0.49 4585 55 100 1.48 5202 23.56 5941 2.20 7091 56 100 1.54 5571 20.43 6161 2.04 6846 57 100 1.54 5459 19.33 6175 2.14 6871 58 100 1.54 5662 20.66 6428 2.14 7531 117 150 3.74 6709 64.65 7728 5.17 8605 118 150 3.74 6885 61.19 7774 5.39 9188 119 150 3.68 6550 60.15 7452 5.66 9086 120 150 3.68 6756 57.95 7702 5.49 9375
Num X Y 1 370 820 2 610 360 3 260 220 4 120 70 5 490 30 6 770 280 7 540 70 8 690 560 9 260 470 10 300 240 11 570 250 12 490 510 13 610 530 14 230 470 15 810 170 16 600 700 17 70 690 18 50 740 19 620 280 20 680 390 21 790 370 22 570 400 23 70 80 24 270 770 25 730 450 26 70 110 27 370 410 28 80 360 29 680 260 30 400 250 31 210 220 32 540 620 33 770 470 34 410 770 35 580 570 36 520 290 37 410 310 38 420 190 39 410 30 40 190 90 41 320 530 42 640 790 43 280 690 44 280 800 45 280 280 46 670 230 47 800 240 48 390 650 49 140 70 50 170 210 51 70 230 52 370 170 53 410 740 54 570 540 55 220 310 56 550 550 57 530 630 58 800 770 59 70 220 60 200 310 61 290 350 62 800 320 63 90 810 64 70 100 65 660 220 66 200 420 67 270 600 68 300 270 69 380 140 70 290 80 71 370 380 72 760 440 73 810 690 74 160 120 75 630 660 76 80 560 77 320 220 78 380 130 79 710 70 80 770 140 81 160 680 82 260 50 83 320 320 84 400 40 85 560 190 86 150 490 87 770 460 88 130 340 89 130 450 90 70 680 91 740 810 92 330 30 93 750 630 94 130 530 95 200 30 96 810 710 97 820 90 98 120 770 99 600 290 100 580 190
Example 1 Excluding two wires at a time.
/***** CONORDER.H (TSPHEUR.EXE) Connection order routines in this unit. *****/
/* connection order pin record type */
typedef struct {
INT x, y, z;
INT conns[9];
INT ring, level;
INT srctrm;
} CON_CITYTYPE;
/* connection order wire record type */
typedef struct {
INT cfrom, cto;
INT distance;
CHAR eligible, exclude;
} CON_WIRETYPE;
/* length macros */
#define CON_CITYMAX 150
#define CON_WIREMAX 12000
#define CON_MAXLEN 9999999L
/* prototypes */
VOID con_alloc( VOID );
VOID con_dealloc( VOID );
LONG con_heuristic( INT );
LONG con_hookup( INT );
VOID con_initcities( INT );
INT con_levelok( INT, INT );
VOID con_makewires( VOID );
LONG con_mintree( VOID );
LONG con_neighbor( VOID );
VOID con_randcities( VOID );
VOID con_reset( VOID );
VOID con_setring( INT, INT );
VOID con_sortwires( VOID );
VOID con_sortshift( INT, INT );
INT con_wireok( INT, INT, INT );
/***** CONORDER.C (TSPHEUR.EXE) Connection order routines in this unit. *****/
#include <stdio.h>
#include <math.h>
#include "defs.h"
#include "conorder.h"
#include "tspheur.h"
/* variables */
CON_CITYTYPE *con_cities[CON_CITYMAX + 1]; /* city records */
CON_WIRETYPE *con_wires[CON_WIREMAX + 1]; /* wire records */
INT con_citycount, con_wirecount; /* number of cities and wires */
INT con_numexclude; /* number of excluded wires */
INT con_wireorder[CON_CITYMAX + 1]; /* global order of wires */
INT con_order[CON_CITYMAX + 1]; /* order of wires */
INT con_sterm[3]; /* source term vars */
FLOAT con_lwtot = 0; /* total of wires used in hookup */
INT con_hookcount = 0; /* number of calls to hookup */
/* imports */
EXTERN INT tsp_stflag;
EXTERN INT tsp_disttype;
EXTERN INT tsp_3d;
EXTERN INT tsp_randx;
EXTERN INT tsp_randy;
EXTERN INT tsp_randz;
/* con_alloc() allocates memory for the connection order algorithm */
VOID con_alloc( VOID )
{
INT ws, ps;
LONG i;
ps = sizeof( CON_CITYTYPE );
for( i = 0; i < CON_CITYMAX + 1; i++ )
con_cities[i] = (CON_CITYTYPE *) mem_alloc( ps );
ws = sizeof( CON_WIRETYPE );
for( i = 0; i < CON_WIREMAX + 1; i++ )
con_wires[i] = (CON_WIRETYPE *) mem_alloc( ws );
}
/* con_dealloc() deallocates memory from the connection order algorithm */
VOID con_dealloc()
{
LONG i, li;
for( i = 0; i <= con_citycount; i++ )
mem_free( (CHAR *) con_cities[i] );
li = con_citycount * (con_citycount - 1L) / 2L + 1L;
for( i = 0; i < li; i++ )
mem_free( (CHAR *) con_wires[i] );
}
/* con_heuristic() creates a net with only clim connects to each city */
LONG con_heuristic( INT clim )
{
LONG templen, newlen;
INT i, k, j;
tsp_printf( "Running heuristic." );
fprintf( stdout, " " );
con_initcities( 0 );
con_numexclude = 0;
templen = 0;
newlen = con_hookup( con_citycount - 1 );
for( i = 1; i <= con_citycount - 1; i++ )
con_wireorder[i] = con_order[i];
for( i = 1; i <= con_citycount; i++ )
{
if( i % 7 == 6 )
fprintf( stdout, "\b\b\b%2d%%", (i * 100) / con_citycount );
if( con_cities[i]->conns[0] >= clim )
{
k = 1;
while( k <= con_cities[i]->conns[0] )
{
con_initcities( 0 );
if( !con_wires[con_cities[i]->conns[k]]->exclude )
{
con_wires[con_cities[i]->conns[k]]->eligible = 0;
templen = con_hookup( con_citycount - 1 );
if( templen < newlen )
{
con_numexclude++;
con_wires[con_cities[i]->conns[k]]->exclude = 1;
newlen = templen;
for( j = 1; j <= con_citycount - 1; j++ )
con_wireorder[j] = con_order[j];
}
}
k++;
}
}
}
fprintf( stdout, "\b\b\b\b" );
return( newlen );
}
/* con_hookup() creates a serial route order and places it in con_order[] */
LONG con_hookup( INT wcount )
{
LONG netlen = 0;
INT i = 1, ti, cf, ct;
con_hookcount++;
while( i <= con_wirecount )
{
if( con_wires[i]->eligible && con_wires[i]->distance != 0 )
{
cf = con_wires[i]->cfrom;
ct = con_wires[i]->cto;
ti = 0;
if( tsp_stflag )
ti = (wcount > 1);
if( con_wireok( cf, ct, ti ) )
{
if( con_levelok( cf, ct ) )
{
con_setring( con_cities[cf]->ring, con_cities[ct]->ring );
con_order[wcount--] = i;
con_wires[i]->eligible = 0;
con_cities[cf]->level++;
con_cities[ct]->level++;
netlen += con_wires[i]->distance;
if( wcount < 1 )
{
con_lwtot += i;
i = con_wirecount;
}
}
}
}
i++;
}
if( wcount > 0 )
{
con_lwtot += con_wirecount;
return( CON_MAXLEN );
}
else
return( netlen );
}
/* con_initcities() reinitializes the all the cities in the net */
VOID con_initcities( INT unc )
{
INT j;
for( j = 1; j <= con_wirecount; j++ )
{
if( unc )
con_wires[j]->exclude = 0;
if( !con_wires[j]->exclude )
con_wires[j]->eligible = 1;
}
for( j = 1; j <= con_citycount; j++ )
{
con_cities[j]->ring = j;
con_cities[j]->level = 0;
}
}
/* con_levelok() insures that no city has more than n connections on it */
INT con_levelok( INT cf, INT ct )
{
INT cfl, ctl, ret;
cfl = con_cities[cf]->level;
ctl = con_cities[ct]->level;
if( con_cities[cf]->srctrm == 0 && con_cities[ct]->srctrm == 0 )
{
if( cfl < 2 && ctl < 2 )
return( 1 );
}
else
{
if( con_cities[cf]->srctrm )
if( con_cities[ct]->srctrm )
ret = ((cfl < 1) && (ctl < 1));
else
ret = ((cfl < 1) && (ctl < 2));
else
ret = ((cfl < 2) && (ctl < 1));
return( ret );
}
return( 0 );
}
/* con_makewires() creates a sorted list of interconnection wire lengths */
VOID con_makewires()
{
FLOAT tf;
LONG i, j;
INT tlen;
LONG xd, yd, zd;
tsp_printf( "Building cost matrix." );
con_wirecount = 0;
for( i = 1; i <= con_citycount; i++ )
{
for( j = i + 1; j <= con_citycount; j++ )
{
switch( tsp_disttype )
{
case 2: xd = (SIGNED) con_cities[i]->x - (SIGNED) con_cities[j]->x;
yd = (SIGNED) con_cities[i]->y - (SIGNED) con_cities[j]->y;
zd = (SIGNED) con_cities[i]->z - (SIGNED) con_cities[j]->z;
tf = sqrt( xd * xd + yd * yd + zd * zd ) + 0.5;
tlen = (INT) tf;
break;
default: tlen = abs( con_cities[i]->x - con_cities[j]->x ) +
abs( con_cities[i]->y - con_cities[j]->y ) +
abs( con_cities[i]->z - con_cities[j]->z );
break;
}
con_wirecount++;
con_wires[con_wirecount]->cfrom = i;
con_wires[con_wirecount]->cto = j;
con_wires[con_wirecount]->distance = tlen;
con_wires[con_wirecount]->eligible = 1;
con_wires[con_wirecount]->exclude = 0;
}
}
}
/* con_mintree() finds the minimum tree of the sorted list of wires */
LONG con_mintree()
{
LONG len = 0;
INT i = 1, k, w = 0;
tsp_printf( "Creating minimum tree." );
con_initcities( con_citycount );
while( i <= con_wirecount )
{
if( con_wireok( con_wires[i]->cfrom, con_wires[i]->cto, 0 ) &&
con_wires[i]->distance != 0 )
{
con_setring( con_wires[i]->cfrom, con_wires[i]->cto );
len += con_wires[i]->distance;
con_wires[i]->eligible = 0;
k = ++(con_cities[con_wires[i]->cfrom]->conns[0]);
con_cities[con_wires[i]->cfrom]->conns[k] = i;
k = ++(con_cities[con_wires[i]->cto]->conns[0]);
con_cities[con_wires[i]->cto]->conns[k] = i;
w++;
}
if( w == con_citycount - 1 )
i = con_wirecount;
i++;
}
return( len );
}
/* con_neighbor() creates a connect order by nearest city algorithm */
LONG con_neighbor()
{
INT cf = 1, ct = 1, cn = 1;
INT wlim, wc = 0, p, ti;
LONG nlen = 0L;
tsp_printf( "Running neighbor." );
if( tsp_stflag )
cn = con_sterm[1];
con_initcities( 1 );
wlim = con_citycount - 1;
while( wc < wlim )
{
p = 1;
while( p <= con_wirecount )
{
if( con_wires[p]->eligible )
{
cf = con_wires[p]->cfrom;
ct = con_wires[p]->cto;
ti = 1;
if( wc == con_citycount - 2 )
ti = 0;
if( con_wireok( cf, ct, ti ) )
if( con_levelok( cf, ct ) )
{
if( cf == cn || ct == cn )
{
wc++;
con_setring( con_cities[cf]->ring, con_cities[ct]->ring );
con_wireorder[wc] = p;
con_cities[cf]->level++;
con_cities[ct]->level++;
nlen += con_wires[p]->distance;
if( cn == cf )
cn = ct;
else
cn = cf;
p = con_wirecount;
}
}
}
p++;
}
}
return( nlen );
}
/* con_randcities() creates n random cities */
VOID con_randcities()
{
INT i, j, x1, y1, z1, ok, done;
for( i = 1; i <= con_citycount; i++ )
{
done = 0;
while( !done )
{
ok = 1;
x1 = ((INT) rand() % tsp_randx) * 10 + 30;
y1 = ((INT) rand() % tsp_randy) * 10 + 30;
z1 = 0;
if( tsp_3d )
z1 = ((INT) rand() % tsp_randz) * 10;
for( j = 1; j < i; j++ )
if( con_cities[j]->x == x1 && con_cities[j]->y == y1 &&
con_cities[j]->z == z1 )
ok = 0;
if( ok )
{
con_cities[i]->x = x1;
con_cities[i]->y = y1;
con_cities[i]->z = z1;
done = 1;
}
}
}
}
/* con_reset() resets the traveling salesman hueristic */
VOID con_reset()
{
INT i;
for( i = 1; i < CON_CITYMAX + 1; i++ )
{
con_cities[i]->x = 0;
con_cities[i]->y = 0;
con_cities[i]->z = 0;
con_cities[i]->conns[0] = 0;
con_cities[i]->ring = 0;
con_cities[i]->level = 0;
con_cities[i]->srctrm = 0;
}
}
/* con_setring() sets the members of dest ring to src ring */
VOID con_setring( INT src, INT dest )
{
INT sw, i;
sw = con_cities[dest]->ring;
for( i = 1; i <= con_citycount; i++ )
if( con_cities[i]->ring == sw )
con_cities[i]->ring = con_cities[src]->ring;
}
/* con_sortwires() sorts the list of wires via a heap sort */
VOID con_sortwires()
{
CON_WIRETYPE temp;
INT root, last;
tsp_printf( "Sorting wires." );
root = con_wirecount / 2;
last = con_wirecount;
while( root > 0 )
{
con_sortshift( root, last );
root--;
}
root = 1;
while( last > 1 )
{ temp = *con_wires[1];*con_wires[1] = *con_wires[last];
*con_wires[last] = temp; last--; con_sortshift( root, last ); }
}
/* con_sortshift() is needed for the heap sort of the wires */
VOID con_sortshift( INT root, INT last )
{
CON_WIRETYPE temp;
INT ptr, succ, key;
ptr = root;
succ = 2 * root;
if( succ < last )
if( con_wires[succ + 1]->distance > con_wires[succ]->distance )
succ++;
key = con_wires[root]->distance;
temp = *con_wires[root];
while( succ <= last && con_wires[succ]->distance > key )
{
*con_wires[ptr] = *con_wires[succ];
ptr = succ;
succ = 2 * ptr;
if( succ < last )
if( con_wires[succ + 1]->distance > con_wires[succ]->distance )
succ++;
}
*con_wires[ptr] = temp;
}
/* con_wireok() reports if it is ok use a specific wire */
INT con_wireok( INT cf, INT ct, INT doit )
{
INT fr, tr;
fr = con_cities[cf]->ring;
tr = con_cities[ct]->ring;
if( tr != fr )
{
if( tsp_stflag )
if( doit )
if( con_cities[con_sterm[1]]->ring == fr )
if( con_cities[con_sterm[2]]->ring == tr )
return( 0 );
else ;
else
if( con_cities[con_sterm[1]]->ring == tr )
if( con_cities[con_sterm[2]]->ring == fr )
return( 0 );
return( 1 );
}
return( 0 );
}
Copyright © 1995, Dr. Dobb's Journal