This is functions.m in view mode; [Download] [Up]
#include <math.h>
#include <limits.h>
#include <stdio.h>
#include "TwoDView.h"
#include "tspheaders.h"
#include "prototypes.h"
/********************************************************************/
/* This file contains a number of miscellaneous functions used in all
of the TSP algorithms.
*/
/********************************************************************/
/********************************************************************/
/* Function: kfrom
given i and j, figure out what the k coordinate is.
*/
/********************************************************************/
int kfrom(int l, int m, int n)
{
int i,j,k;
if (l < m) {
i = l;
j = m;
}
else {
i = m;
j = l;
}
k = i*n - i*(i+1)/2+j-i-1;
return(k);
}
/********************************************************************/
/* Function: ClosestCities
given a list of cities, figure out which two are closest, and
return the distance between them.
From and To will contain the indices of the cities.
The function returns the distance between them.
*/
/********************************************************************/
float ClosestCities(float *Distance, int *From, int *To, int NumberOfCities) {
int i,j,k;
float MinDistance;
MinDistance = INT_MAX;
for(i=0;i<NumberOfCities;i++) {
for(j=(i+1);j<NumberOfCities;j++) {
k = kfrom(i,j,NumberOfCities);
if (Distance[k] < MinDistance) {
#ifdef DEBUGMYDIR
printf("k is %d i is %d j is %d \n",k,i,j);
printf("changing mindistance from %f to %f \n",MinDistance,Distance[k]);
#endif
MinDistance = Distance[k];
*From = i;
*To = j;
}
}
}
return(MinDistance);
}
/********************************************************************/
/* Function: FarthestCities
given a list of cities, figure out which two are farthest, and
return the distance between them.
From and To will contain the indices of the cities.
The function returns the distance between them.
*/
/********************************************************************/
float FarthestCities(float *Distance, int *From, int *To, int NumberOfCities) {
int i,j,k;
float BigDistance;
BigDistance = 0;
for(i=0;i<NumberOfCities;i++) {
for(j=(i+1);j<NumberOfCities;j++) {
k = kfrom(i,j,NumberOfCities);
if (Distance[k] > BigDistance) {
#ifdef DEBUGMYDIR
printf("k is %d i is %d j is %d \n",k,i,j);
printf("changing bigdistance from %f to %f \n",BigDistance,Distance[k]);
#endif
BigDistance = Distance[k];
*From = i;
*To = j;
}
}
}
return(BigDistance);
}
/********************************************************************/
/* Function: ValidTour
given a tour and 2 edges to exchange, figure out if the tour is
valid if the two edges are exchanged.
*/
/********************************************************************/
int ValidTour(int *Tour, int Edge1, int Edge2, int Reverse,
int NumberOfCities) {
int i,To1,BeginningCity,CurrentCity,GoingThroughTour,IsATour,
StillLooking,AtEdge,NextEdge,NumberOfCitiesVisited;
int *TestingTour;
/* allocate space for TestingTour */
TestingTour = (int *)malloc(2*NumberOfCities*sizeof(int));
if (TestingTour == (int *) 0)
printf("Malloc for TestingTour failed. \n");
for (i=0;i<2*NumberOfCities;i+=2) {
TestingTour[i] = Tour[i];
TestingTour[i+1] = Tour[i+1];
}
/* exchange the edges in the tour. */
/* if Reverse == 1, then make To From and From To. */
if (Reverse) {
To1 = TestingTour[2*Edge1+1];
TestingTour[2*Edge1+1] = TestingTour[2*Edge2+1];
TestingTour[2*Edge2+1] = To1;
}
else {
/* if Reverse == 0, then take the second edge as is. */
To1 = TestingTour[2*Edge1+1];
TestingTour[2*Edge1+1] = TestingTour[2*Edge2];
TestingTour[2*Edge2] = To1;
}
GoingThroughTour = 1;
IsATour = 0;
BeginningCity = TestingTour[0];
CurrentCity = TestingTour[1];
NumberOfCitiesVisited = 0;
AtEdge = 0;
while (GoingThroughTour) {
/* set NextEdge to be the next edge after AtEdge in the tour. */
if (AtEdge >= (NumberOfCities-1)) {
NextEdge = 0;
}
else {
NextEdge = AtEdge + 1;
}
StillLooking = 1;
while ((StillLooking) && (GoingThroughTour)) {
/* look to see if the To of NextEdge is the city we want. */
if (TestingTour[2*NextEdge] == CurrentCity) {
NumberOfCitiesVisited+=1;
if (CurrentCity == BeginningCity) {
if (NumberOfCitiesVisited == NumberOfCities) {
/* then we have found a valid tour. */
IsATour = 1;
GoingThroughTour = 0;
}
else {
/* otherwise, this tour has subtours. */
GoingThroughTour = 0;
}
}
CurrentCity = TestingTour[2*NextEdge+1];
AtEdge = NextEdge;
StillLooking = 0;
}
else {
/* look to see if the From of NextEdge is the city we want. */
if (TestingTour[2*NextEdge+1] == CurrentCity) {
NumberOfCitiesVisited+=1;
if (CurrentCity == BeginningCity) {
if (NumberOfCitiesVisited == NumberOfCities) {
/* then we have found a valid tour. */
IsATour = 1;
GoingThroughTour = 0;
}
else {
/* otherwise, this tour has subtours. */
GoingThroughTour = 0;
}
}
CurrentCity = TestingTour[2*NextEdge];
AtEdge = NextEdge;
StillLooking = 0;
}
}
/* get ready to look at the next edge. */
if (AtEdge >= (NumberOfCities-1)) {
if (NextEdge == (AtEdge-1)) {
StillLooking = 0;
GoingThroughTour = 0;
}
else {
NextEdge+=1;
}
}
else {
if (NextEdge >= (NumberOfCities - 1)) {
NextEdge = 0;
}
else {
NextEdge+=1;
}
}
}
}
free(TestingTour);
return(IsATour);
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.