MultiSource/Benchmarks/Ptrdist/yacr2/assign.c - third_party/llvm-test-suite - Git at Google

 /*
  *
  * assign.c
  *
  */


 #define ASSIGN_CODE


 /*
  *
  * Includes.
  *
  */

 #include <stdio.h>
 #include <stdlib.h>
 #include <assert.h>
 #include "types.h"
 #include "assign.h"
 #include "channel.h"
 #include "vcg.h"
 #include "hcg.h"


 /*
  *
  * Code.
  *
  */

 void
 AllocAssign(void)
 {
     ulong	net;

     /*
      * Allocate cost matrix.
      */
     costMatrix = (long * *)malloc((channelNets+1) * sizeof(long *));
     for (net = 1; net <= channelNets; net++) {
 	costMatrix[net] = (long *)malloc((channelTracks+2) * sizeof(long));
     }

     /*
      * Allocate structures associated with cost matrix.
      */
     tracksNotPref = (ulong *)malloc((channelTracks+2) * sizeof(ulong));
     tracksTopNotPref = (ulong *)malloc((channelTracks+2) * sizeof(ulong));
     tracksBotNotPref = (ulong *)malloc((channelTracks+2) * sizeof(ulong));
     tracksNoHCV = (ulong *)malloc((channelTracks+2) * sizeof(ulong));
     tracksAssign = (ulong *)malloc((channelTracks+2) * sizeof(ulong));
     netsAssign = (ulong *)malloc((channelNets+1) * sizeof(ulong));
     netsAssignCopy = (ulong *)malloc((channelNets+1) * sizeof(ulong));
 }

 void
 FreeAssign(void)
 {
     ulong	net;

     /*
      * Free cost matrix.
      */
     for (net = 1; net <= channelNets; net++) {
 	free(costMatrix[net]);
     }
     free(costMatrix);

     /*
      * Free structures associated with cost matrix.
      */
     free(tracksNotPref);
     free(tracksTopNotPref);
     free(tracksBotNotPref);
     free(tracksNoHCV);
     free(tracksAssign);
     free(netsAssign);
     free(netsAssignCopy);
 }

 void
 NetsAssign(void)
 {
     ulong	net;

     /*
      * Init.
      */
     for (net = 1; net <= channelNets; net++) {
 	netsAssign[net] = 0;
     }

     /*
      * Assign nets in max density column.
      */
     MaxNetsAssign();

 #ifdef SCOTT
     /*
      * Assign net in columns right of max density column.
      */
     RightNetsAssign();

     /*
      * Assign net in columns left of max density column.
      */
     LeftNetsAssign();
 #else
     /*
      * Assign net in columns left of max density column.
      */
     LeftNetsAssign();

     /*
      * Assign net in columns right of max density column.
      */
     RightNetsAssign();
 #endif
 }

 void
 MaxNetsAssign(void)
 {
     ulong	net;
     ulong	netSelect;
     ulong	netsCrossing;
     ;

 #ifdef VERBOSE
     printf("density = %d\n", channelDensity);
     printf("pivot = %d\n\n", channelDensityColumn);
 #endif

     /*
      * Determine nets crossing column of max channel density.
      */
     netsCrossing = 0;
     for (net = 1; net <= channelNets; net++) {
 	if ((FIRST[net] <= channelDensityColumn) && (LAST[net] >= channelDensityColumn)) {
 	    CROSSING[net] = TRUE;
 	    netsCrossing++;
 	}
 	else {
 	    CROSSING[net] = FALSE;
 	}
     }

     while (netsCrossing > 0) {
 	/*
 	 * Choose net from CROSSING to assign.
 	 */
 	Select(VCG, HCG, netsAssign, &netSelect, CROSSING);

 	/*
 	 * Assign net to a track.
 	 */
 	Assign(VCG, netsAssign, netSelect);

 	/*
 	 * Done net.
 	 */
 	CROSSING[netSelect] = FALSE;
 	netsCrossing--;
     }
     ;
 }

 void
 RightNetsAssign(void)
 {
     ulong	net;
     ulong	col;
     ulong	top;
     ulong	bot;
     ulong	netsCrossing;
     ulong	netSelect;
     ;

     /*
      * Init.
      */
     for (net = 1; net <= channelNets; net++) {
 	CROSSING[net] = FALSE;
     }
     netsCrossing = 0;

     /*
      * Assign nets within channel.
      */
     for (col = channelDensityColumn+1; col <= channelColumns; col++) {
 	/*
 	 * Collection.
 	 */
 	top = TOP[col];
 	bot = BOT[col];
 	if (top != bot) {
 	    if (top && (FIRST[top] == col)) {
 		CROSSING[top] = TRUE;
 		netsCrossing++;
 	    }
 	    if (bot && (FIRST[bot] == col)) {
 		CROSSING[bot] = TRUE;
 		netsCrossing++;
 	    }
 	}
 	else {
 	    if (top && (FIRST[top] == col)) {
 		CROSSING[top] = TRUE;
 		netsCrossing++;
 	    }
 	}

 	/*
 	 * Assignment.
 	 */
 	if ((LAST[top] == col) || (LAST[bot] == col)) {
 	    while (netsCrossing > 0) {
 		/*
 		 * Choose net from CROSSING to assign.
 		 */
 		Select(VCG, HCG, netsAssign, &netSelect, CROSSING);

 		/*
 		 * Assign net to a track.
 		 */
 		Assign(VCG, netsAssign, netSelect);

 		/*
 		 * Done net.
 		 */
 		CROSSING[netSelect] = FALSE;
 		netsCrossing--;
 	    }
 	}
     }
     assert(! netsCrossing);
     ;
 }

 void
 LeftNetsAssign(void)
 {
     ulong	net;
     ulong	col;
     ulong	top;
     ulong	bot;
     ulong	netsCrossing;
     ulong	netSelect;
     ;

     /*
      * Init.
      */
     for (net = 1; net <= channelNets; net++) {
 	CROSSING[net] = FALSE;
     }
     netsCrossing = 0;

     /*
      * Assign nets within channel.
      */
     for (col = channelDensityColumn-1; col >= 1; col--) {
 	/*
 	 * Collection.
 	 */
 	top = TOP[col];
 	bot = BOT[col];
 	if (top != bot) {
 	    if (top && (LAST[top] == col)) {
 		CROSSING[top] = TRUE;
 		netsCrossing++;
 	    }
 	    if (bot && (LAST[bot] == col)) {
 		CROSSING[bot] = TRUE;
 		netsCrossing++;
 	    }
 	}
 	else {
 	    if (top && (LAST[top] == col)) {
 		CROSSING[top] = TRUE;
 		netsCrossing++;
 	    }
 	}

 	/*
 	 * Assignment.
 	 */
 	if ((FIRST[top] == col) || (FIRST[bot] == col)) {
 	    while (netsCrossing > 0) {
 		/*
 		 * Choose net from CROSSING to assign.
 		 */
 		Select(VCG, HCG, netsAssign, &netSelect, CROSSING);

 		/*
 		 * Assign net to a track.
 		 */
 		Assign(VCG, netsAssign, netSelect);

 		/*
 		 * Done net.
 		 */
 		CROSSING[netSelect] = FALSE;
 		netsCrossing--;
 	    }
 	}
     }
     assert(! netsCrossing);
     ;
 }

 void
 Assign(nodeVCGType * VCG,
        ulong * assign,
        ulong select)
 {
     long	dist;
     ulong	ideal;
     ulong	track;
     ulong	tracks;
     ulong	trackAssign;
     ulong	vcv;
     long	vcvDist;
     ulong	vcvAssign;
     long *	costNet;
     ;

 #ifdef VERBOSE
     printf("\n*** Assign %d ***\n", select);
 #endif

     /*
      * Need information for the selected net.
      * (Must recompute...not current for the selected net)
      *
      * tracksNoHCV
      * tracksNotPref
      * tracksTopNotPref
      * tracksBotNotPref
      * cardNotPref
      * cardTopNotPref
      * cardBotNotPref
      */
     LongestPathVCG(VCG, select);
     NoHCV(HCG, select, assign, tracksNoHCV);
     IdealTrack(channelTracks, cardTopNotPref, cardBotNotPref, &ideal);

 #ifdef VERBOSE
     printf("HCV's:\n");
     for (track = 1; track <= channelTracks; track++) {
 	if (tracksNoHCV[track]) {
 	    printf("[%d] no hcv\n", track);
 	}
 	else {
 	    printf("[%d] hcv\n", track);
 	}
     }
     printf("\n");
 #endif

     /*
      * What tracks to consider for assign.
      */
     costNet = costMatrix[select];
     assert((select >= 1) && (select <= channelNets));
     tracks = 0;
     for (track = 1; track <= channelTracks; track++) {
 	tracksAssign[track] = FALSE;
     }

     /*
      * Choice 1.
      */
     for (track = 1; track <= channelTracks; track++) {
 	if (tracksNoHCV[track] && (! tracksNotPref[track])) {
 	    tracksAssign[track] = TRUE;
 	    tracks++;
 	}
     }
 #ifdef VERBOSE
     if (tracks != 0) {
 	printf("using choice 1...\n");
     }
 #endif
     /*
      * Choice 2.
      */
     if (tracks == 0) {
 	for (track = 1; track <= channelTracks; track++) {
 	    if (tracksNoHCV[track] && tracksTopNotPref[track] && tracksBotNotPref[track]) {
 		tracksAssign[track] = TRUE;
 		tracks++;
 	    }
 	}
 #ifdef VERBOSE
 	if (tracks != 0) {
 	    printf("using choice 2...\n");
 	}
 #endif
     }
     /*
      * Choice 3.
      */
     if (tracks == 0) {
 	for (track = 2; track < channelTracks; track++) {
 	    if (tracksNoHCV[track] && tracksNotPref[track]) {
 		tracksAssign[track] = TRUE;
 		tracks++;
 	    }
 	}
 #ifdef VERBOSE
 	if (tracks != 0) {
 	    printf("using choice 3...\n");
 	}
 #endif
     }
     /*
      * Choice 4.
      */
     if (tracks == 0) {
 	if (tracksNoHCV[1]) {
 	    tracksAssign[1] = TRUE;
 	    tracks++;
 	}
 	if (tracksNoHCV[channelTracks]) {
 	    tracksAssign[channelTracks] = TRUE;
 	    tracks++;
 	}
 #ifdef VERBOSE
 	printf("using choice 4...\n");
 #endif
     }
     assert(tracks != 0);

 /*
     costNet = costMatrix[select];
     assert((select >= 1) && (select <= channelNets));
     tracks = 0;
     for (track = 1; track <= channelTracks; track++) {
 	tracksAssign[track] = FALSE;
     }
     for (track = 1; track <= channelTracks; track++) {
 	if ((costNet[track] < HIGH) {
 	    tracksAssign[track] = TRUE;
 	    tracks++;
 	}
     }
     if (tracks == 0) {
 	for (track = 2; track < channelTracks; track++) {
 	    if (costNet[track] < INFINITY) {
 		tracksAssign[track] = TRUE;
 		tracks++;
 	    }
 	}
     }
     if (tracks == 0) {
 	if (costNet[1] < INFINITY) {
 	    tracksAssign[1] = TRUE;
 	    tracks++;
 	}
 	if (costNet[channelTracks] < INFINITY) {
 	    tracksAssign[channelTracks] = TRUE;
 	    tracks++;
 	}
     }
     assert(tracks != 0);
 */

     /*
      * Assign to one of the tracks under consideration.
      */
     trackAssign = 0;
     vcvAssign = INFINITY;
     for (track = 1; track <= channelTracks; track++) {
 	if (tracksAssign[track]) {
 	    vcv = VCV(VCG, select, track, netsAssign);
 	    if (vcv < vcvAssign) {
 		vcvAssign = vcv;
 		trackAssign = track;
 		vcvDist = (long) (track - ideal);
 		if (vcvDist < 0) {
 		    vcvDist *= -1;
 		}
 	    }
 	    else if (vcv == vcvAssign) {
 		assert(trackAssign);
 		dist = (long) (track - ideal);
 		if (dist < 0) {
 		    dist *= -1;
 		}
 		if (dist < vcvDist) {
 		    vcvDist = dist;
 		    vcvAssign = vcv;
 		    trackAssign = track;
 		}
 	    }
 	}
     }
     assert(trackAssign);
     assign[select] = trackAssign;
 #ifdef VERBOSE
     printf("\n*** Assign %d -> %d ***\n", select, trackAssign);
 #endif
     ;
 }

 void
 Select(nodeVCGType * VCG,
        nodeHCGType * HCG,
        ulong * netsAssign,
        ulong * netSelect,
        ulong * CROSSING)
 {
     ulong	net;
     ulong	track;
     ulong	select;
     long *	costNet;
     long	cost;
     long	largest;

     /*
      * Build cost matrix.
      */
     BuildCostMatrix(VCG, HCG, netsAssign, CROSSING);

     /*
      * Select most restricted net.
      * That is, net with greatest column sum in cost matrix.
      */
     largest = -1;
     select = 0;
     for (net = 1; net <= channelNets; net++) {
 	if (CROSSING[net]) {
 	    cost = 0;
 	    costNet = costMatrix[net];
 	    for (track = 1; track <= channelTracks; track++) {
 		cost += costNet[track];
 	    }
 	    if (cost > largest) {
 		largest = cost;
 		select = net;
 	    }
 	}
     }
     assert(select);

     /*
      * Net selected.
      */
     *netSelect = select;
 }

 void
 BuildCostMatrix(nodeVCGType * VCG,
 		nodeHCGType * HCG,
 		ulong * netsAssign,
 		ulong * CROSSING)
 {
     ulong	net;
     ulong	track;
     ulong	ideal;
     long       	dist;
     long	mult;
     long *	costNet;
     ;

     /*
      * Initialize cost matrix.
      */
     for (net = 1; net <= channelNets; net++) {
 	costNet = costMatrix[net];
 	for (track = 1; track <= channelTracks; track++) {
 	    costNet[track] = 0;
 	}
     }

     for (net = 1; net <= channelNets; net++) {
 	if (CROSSING[net]) {
 	    /*
 	     * Compute one column in cost matrix.
 	     * That is, the cost associated with each track for some net.
 	     */
 	    costNet = costMatrix[net];

 	    /*
 	     * Compute measures related to cost.
 	     */
 	    LongestPathVCG(VCG, net);
 	    NoHCV(HCG, net, netsAssign, tracksNoHCV);
 	    IdealTrack(channelTracks, cardTopNotPref, cardBotNotPref, &ideal);

 	    /*
 	     * Compute cost associated with each track.
 	     */
 	    for (track = 1; track <= channelTracks; track++) {
 		if (tracksNoHCV[track]) {
 		    if (cardNotPref != channelTracks) {
 			if (tracksNotPref[track]) {
 			    costNet[track] = HIGH;
 			}
 			else {
 			    costNet[track] = MEDIUM * cardNotPref;
 			}
 		    }
 		    else {
 			if ((track > (channelTracks - cardBotNotPref)) && (track <= cardTopNotPref)) {
 			    mult = cardNotPref - (cardTopNotPref + cardBotNotPref - channelTracks);
 			    assert(mult >= 0);
 			    costNet[track] = MEDIUM * mult;
 			}
 			else {
 			    costNet[track] = HIGH;
 			}
 		    }

 		    if (costNet[track] < INFINITY) {
 			dist = (long) (ideal - track);
 			if (dist < 0) {
 			    dist *= -1;
 			}
 			costNet[track] += LOW * dist;
 		    }
 		}
 		else {
 		    costNet[track] = INFINITY;
 		}
 	    }
 	}
     }
     ;
 }

 void
 IdealTrack(ulong tracks,
 	   ulong top,
 	   ulong bot,
 	   ulong * ideal)
 {
     ulong	num;
     ulong	den;

     num = (top * (tracks - bot)) + (bot * (top + 1));
     den = top + bot;

     if (den != 0) {
 	*ideal = (ulong) ((ulong) num / (ulong) den);
     }
     else {
 	*ideal = 1;
     }
 }
	/*
	*
	* assign.c
	*
	*/


	#define ASSIGN_CODE


	/*
	*
	* Includes.
	*
	*/

	#include <stdio.h>
	#include <stdlib.h>
	#include <assert.h>
	#include "types.h"
	#include "assign.h"
	#include "channel.h"
	#include "vcg.h"
	#include "hcg.h"


	/*
	*
	* Code.
	*
	*/

	void
	AllocAssign(void)
	{
	ulong net;

	/*
	* Allocate cost matrix.
	*/
	costMatrix = (long * )malloc((channelNets+1) sizeof(long *));
	for (net = 1; net <= channelNets; net++) {
	costMatrix[net] = (long )malloc((channelTracks+2) sizeof(long));
	}

	/*
	* Allocate structures associated with cost matrix.
	*/
	tracksNotPref = (ulong )malloc((channelTracks+2) sizeof(ulong));
	tracksTopNotPref = (ulong )malloc((channelTracks+2) sizeof(ulong));
	tracksBotNotPref = (ulong )malloc((channelTracks+2) sizeof(ulong));
	tracksNoHCV = (ulong )malloc((channelTracks+2) sizeof(ulong));
	tracksAssign = (ulong )malloc((channelTracks+2) sizeof(ulong));
	netsAssign = (ulong )malloc((channelNets+1) sizeof(ulong));
	netsAssignCopy = (ulong )malloc((channelNets+1) sizeof(ulong));
	}

	void
	FreeAssign(void)
	{
	ulong net;

	/*
	* Free cost matrix.
	*/
	for (net = 1; net <= channelNets; net++) {
	free(costMatrix[net]);
	}
	free(costMatrix);

	/*
	* Free structures associated with cost matrix.
	*/
	free(tracksNotPref);
	free(tracksTopNotPref);
	free(tracksBotNotPref);
	free(tracksNoHCV);
	free(tracksAssign);
	free(netsAssign);
	free(netsAssignCopy);
	}

	void
	NetsAssign(void)
	{
	ulong net;

	/*
	* Init.
	*/
	for (net = 1; net <= channelNets; net++) {
	netsAssign[net] = 0;
	}

	/*
	* Assign nets in max density column.
	*/
	MaxNetsAssign();

	#ifdef SCOTT
	/*
	* Assign net in columns right of max density column.
	*/
	RightNetsAssign();

	/*
	* Assign net in columns left of max density column.
	*/
	LeftNetsAssign();
	#else
	/*
	* Assign net in columns left of max density column.
	*/
	LeftNetsAssign();

	/*
	* Assign net in columns right of max density column.
	*/
	RightNetsAssign();
	#endif
	}

	void
	MaxNetsAssign(void)
	{
	ulong net;
	ulong netSelect;
	ulong netsCrossing;
	;

	#ifdef VERBOSE
	printf("density = %d\n", channelDensity);
	printf("pivot = %d\n\n", channelDensityColumn);
	#endif

	/*
	* Determine nets crossing column of max channel density.
	*/
	netsCrossing = 0;
	for (net = 1; net <= channelNets; net++) {
	if ((FIRST[net] <= channelDensityColumn) && (LAST[net] >= channelDensityColumn)) {
	CROSSING[net] = TRUE;
	netsCrossing++;
	}
	else {
	CROSSING[net] = FALSE;
	}
	}

	while (netsCrossing > 0) {
	/*
	* Choose net from CROSSING to assign.
	*/
	Select(VCG, HCG, netsAssign, &netSelect, CROSSING);

	/*
	* Assign net to a track.
	*/
	Assign(VCG, netsAssign, netSelect);

	/*
	* Done net.
	*/
	CROSSING[netSelect] = FALSE;
	netsCrossing--;
	}
	;
	}

	void
	RightNetsAssign(void)
	{
	ulong net;
	ulong col;
	ulong top;
	ulong bot;
	ulong netsCrossing;
	ulong netSelect;
	;

	/*
	* Init.
	*/
	for (net = 1; net <= channelNets; net++) {
	CROSSING[net] = FALSE;
	}
	netsCrossing = 0;

	/*
	* Assign nets within channel.
	*/
	for (col = channelDensityColumn+1; col <= channelColumns; col++) {
	/*
	* Collection.
	*/
	top = TOP[col];
	bot = BOT[col];
	if (top != bot) {
	if (top && (FIRST[top] == col)) {
	CROSSING[top] = TRUE;
	netsCrossing++;
	}
	if (bot && (FIRST[bot] == col)) {
	CROSSING[bot] = TRUE;
	netsCrossing++;
	}
	}
	else {
	if (top && (FIRST[top] == col)) {
	CROSSING[top] = TRUE;
	netsCrossing++;
	}
	}

	/*
	* Assignment.
	*/
	if ((LAST[top] == col) \|\| (LAST[bot] == col)) {
	while (netsCrossing > 0) {
	/*
	* Choose net from CROSSING to assign.
	*/
	Select(VCG, HCG, netsAssign, &netSelect, CROSSING);

	/*
	* Assign net to a track.
	*/
	Assign(VCG, netsAssign, netSelect);

	/*
	* Done net.
	*/
	CROSSING[netSelect] = FALSE;
	netsCrossing--;
	}
	}
	}
	assert(! netsCrossing);
	;
	}

	void
	LeftNetsAssign(void)
	{
	ulong net;
	ulong col;
	ulong top;
	ulong bot;
	ulong netsCrossing;
	ulong netSelect;
	;

	/*
	* Init.
	*/
	for (net = 1; net <= channelNets; net++) {
	CROSSING[net] = FALSE;
	}
	netsCrossing = 0;

	/*
	* Assign nets within channel.
	*/
	for (col = channelDensityColumn-1; col >= 1; col--) {
	/*
	* Collection.
	*/
	top = TOP[col];
	bot = BOT[col];
	if (top != bot) {
	if (top && (LAST[top] == col)) {
	CROSSING[top] = TRUE;
	netsCrossing++;
	}
	if (bot && (LAST[bot] == col)) {
	CROSSING[bot] = TRUE;
	netsCrossing++;
	}
	}
	else {
	if (top && (LAST[top] == col)) {
	CROSSING[top] = TRUE;
	netsCrossing++;
	}
	}

	/*
	* Assignment.
	*/
	if ((FIRST[top] == col) \|\| (FIRST[bot] == col)) {
	while (netsCrossing > 0) {
	/*
	* Choose net from CROSSING to assign.
	*/
	Select(VCG, HCG, netsAssign, &netSelect, CROSSING);

	/*
	* Assign net to a track.
	*/
	Assign(VCG, netsAssign, netSelect);

	/*
	* Done net.
	*/
	CROSSING[netSelect] = FALSE;
	netsCrossing--;
	}
	}
	}
	assert(! netsCrossing);
	;
	}

	void
	Assign(nodeVCGType * VCG,
	ulong * assign,
	ulong select)
	{
	long dist;
	ulong ideal;
	ulong track;
	ulong tracks;
	ulong trackAssign;
	ulong vcv;
	long vcvDist;
	ulong vcvAssign;
	long * costNet;
	;

	#ifdef VERBOSE
	printf("\n* Assign %d *\n", select);
	#endif

	/*
	* Need information for the selected net.
	* (Must recompute...not current for the selected net)
	*
	* tracksNoHCV
	* tracksNotPref
	* tracksTopNotPref
	* tracksBotNotPref
	* cardNotPref
	* cardTopNotPref
	* cardBotNotPref
	*/
	LongestPathVCG(VCG, select);
	NoHCV(HCG, select, assign, tracksNoHCV);
	IdealTrack(channelTracks, cardTopNotPref, cardBotNotPref, &ideal);

	#ifdef VERBOSE
	printf("HCV's:\n");
	for (track = 1; track <= channelTracks; track++) {
	if (tracksNoHCV[track]) {
	printf("[%d] no hcv\n", track);
	}
	else {
	printf("[%d] hcv\n", track);
	}
	}
	printf("\n");
	#endif

	/*
	* What tracks to consider for assign.
	*/
	costNet = costMatrix[select];
	assert((select >= 1) && (select <= channelNets));
	tracks = 0;
	for (track = 1; track <= channelTracks; track++) {
	tracksAssign[track] = FALSE;
	}

	/*
	* Choice 1.
	*/
	for (track = 1; track <= channelTracks; track++) {
	if (tracksNoHCV[track] && (! tracksNotPref[track])) {
	tracksAssign[track] = TRUE;
	tracks++;
	}
	}
	#ifdef VERBOSE
	if (tracks != 0) {
	printf("using choice 1...\n");
	}
	#endif
	/*
	* Choice 2.
	*/
	if (tracks == 0) {
	for (track = 1; track <= channelTracks; track++) {
	if (tracksNoHCV[track] && tracksTopNotPref[track] && tracksBotNotPref[track]) {
	tracksAssign[track] = TRUE;
	tracks++;
	}
	}
	#ifdef VERBOSE
	if (tracks != 0) {
	printf("using choice 2...\n");
	}
	#endif
	}
	/*
	* Choice 3.
	*/
	if (tracks == 0) {
	for (track = 2; track < channelTracks; track++) {
	if (tracksNoHCV[track] && tracksNotPref[track]) {
	tracksAssign[track] = TRUE;
	tracks++;
	}
	}
	#ifdef VERBOSE
	if (tracks != 0) {
	printf("using choice 3...\n");
	}
	#endif
	}
	/*
	* Choice 4.
	*/
	if (tracks == 0) {
	if (tracksNoHCV[1]) {
	tracksAssign[1] = TRUE;
	tracks++;
	}
	if (tracksNoHCV[channelTracks]) {
	tracksAssign[channelTracks] = TRUE;
	tracks++;
	}
	#ifdef VERBOSE
	printf("using choice 4...\n");
	#endif
	}
	assert(tracks != 0);

	/*
	costNet = costMatrix[select];
	assert((select >= 1) && (select <= channelNets));
	tracks = 0;
	for (track = 1; track <= channelTracks; track++) {
	tracksAssign[track] = FALSE;
	}
	for (track = 1; track <= channelTracks; track++) {
	if ((costNet[track] < HIGH) {
	tracksAssign[track] = TRUE;
	tracks++;
	}
	}
	if (tracks == 0) {
	for (track = 2; track < channelTracks; track++) {
	if (costNet[track] < INFINITY) {
	tracksAssign[track] = TRUE;
	tracks++;
	}
	}
	}
	if (tracks == 0) {
	if (costNet[1] < INFINITY) {
	tracksAssign[1] = TRUE;
	tracks++;
	}
	if (costNet[channelTracks] < INFINITY) {
	tracksAssign[channelTracks] = TRUE;
	tracks++;
	}
	}
	assert(tracks != 0);
	*/

	/*
	* Assign to one of the tracks under consideration.
	*/
	trackAssign = 0;
	vcvAssign = INFINITY;
	for (track = 1; track <= channelTracks; track++) {
	if (tracksAssign[track]) {
	vcv = VCV(VCG, select, track, netsAssign);
	if (vcv < vcvAssign) {
	vcvAssign = vcv;
	trackAssign = track;
	vcvDist = (long) (track - ideal);
	if (vcvDist < 0) {
	vcvDist *= -1;
	}
	}
	else if (vcv == vcvAssign) {
	assert(trackAssign);
	dist = (long) (track - ideal);
	if (dist < 0) {
	dist *= -1;
	}
	if (dist < vcvDist) {
	vcvDist = dist;
	vcvAssign = vcv;
	trackAssign = track;
	}
	}
	}
	}
	assert(trackAssign);
	assign[select] = trackAssign;
	#ifdef VERBOSE
	printf("\n* Assign %d -> %d *\n", select, trackAssign);
	#endif
	;
	}

	void
	Select(nodeVCGType * VCG,
	nodeHCGType * HCG,
	ulong * netsAssign,
	ulong * netSelect,
	ulong * CROSSING)
	{
	ulong net;
	ulong track;
	ulong select;
	long * costNet;
	long cost;
	long largest;

	/*
	* Build cost matrix.
	*/
	BuildCostMatrix(VCG, HCG, netsAssign, CROSSING);

	/*
	* Select most restricted net.
	* That is, net with greatest column sum in cost matrix.
	*/
	largest = -1;
	select = 0;
	for (net = 1; net <= channelNets; net++) {
	if (CROSSING[net]) {
	cost = 0;
	costNet = costMatrix[net];
	for (track = 1; track <= channelTracks; track++) {
	cost += costNet[track];
	}
	if (cost > largest) {
	largest = cost;
	select = net;
	}
	}
	}
	assert(select);

	/*
	* Net selected.
	*/
	*netSelect = select;
	}

	void
	BuildCostMatrix(nodeVCGType * VCG,
	nodeHCGType * HCG,
	ulong * netsAssign,
	ulong * CROSSING)
	{
	ulong net;
	ulong track;
	ulong ideal;
	long dist;
	long mult;
	long * costNet;
	;

	/*
	* Initialize cost matrix.
	*/
	for (net = 1; net <= channelNets; net++) {
	costNet = costMatrix[net];
	for (track = 1; track <= channelTracks; track++) {
	costNet[track] = 0;
	}
	}

	for (net = 1; net <= channelNets; net++) {
	if (CROSSING[net]) {
	/*
	* Compute one column in cost matrix.
	* That is, the cost associated with each track for some net.
	*/
	costNet = costMatrix[net];

	/*
	* Compute measures related to cost.
	*/
	LongestPathVCG(VCG, net);
	NoHCV(HCG, net, netsAssign, tracksNoHCV);
	IdealTrack(channelTracks, cardTopNotPref, cardBotNotPref, &ideal);

	/*
	* Compute cost associated with each track.
	*/
	for (track = 1; track <= channelTracks; track++) {
	if (tracksNoHCV[track]) {
	if (cardNotPref != channelTracks) {
	if (tracksNotPref[track]) {
	costNet[track] = HIGH;
	}
	else {
	costNet[track] = MEDIUM * cardNotPref;
	}
	}
	else {
	if ((track > (channelTracks - cardBotNotPref)) && (track <= cardTopNotPref)) {
	mult = cardNotPref - (cardTopNotPref + cardBotNotPref - channelTracks);
	assert(mult >= 0);
	costNet[track] = MEDIUM * mult;
	}
	else {
	costNet[track] = HIGH;
	}
	}

	if (costNet[track] < INFINITY) {
	dist = (long) (ideal - track);
	if (dist < 0) {
	dist *= -1;
	}
	costNet[track] += LOW * dist;
	}
	}
	else {
	costNet[track] = INFINITY;
	}
	}
	}
	}
	;
	}

	void
	IdealTrack(ulong tracks,
	ulong top,
	ulong bot,
	ulong * ideal)
	{
	ulong num;
	ulong den;

	num = (top * (tracks - bot)) + (bot * (top + 1));
	den = top + bot;

	if (den != 0) {
	*ideal = (ulong) ((ulong) num / (ulong) den);
	}
	else {
	*ideal = 1;
	}
	}