_THE DETRIMENTAL WIRE EXCLUSION HEURISTIC_
by Paul J. Martino

Listing One

/***** 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 );


Listing Two

/***** 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 );
    }