This is TwoDTSP.m in view mode; [Download] [Up]
#import "TwoDView.h" /* the main class */
#import "TwoDTSP.h"
#import "prototypes.h"
float simpleTSP(TwoDView *s,float *data,float *distances,int *edges,int n);
#define STATUS(s) [self->statusText setStringValue: s];
#define FROM 0
#define TO 1
static float *distances=0,optimalValue=0; /* file scopr vars */
@implementation TwoDView(TSP)
- doSimpleNearNeighbor
{
if(distances != NULL)
NX_FREE(distances);
/* calculate distances */
NX_MALLOC(distances,float,numPoints*(numPoints-1)/2);
STATUS("Calculating distances");
CalculateDistance(data,distances,numPoints);
/* spaces for edges is allocated in TwoDView in InitGeomerty */
optimalValue = simpleTSP(self,data,distances,tsp_edges,numPoints);
[optimalValueField setFloatValue: optimalValue at: 0];
[optimizeButton setEnabled: YES];
return self ;
}
- doCheapestInsertion
{
if(distances != NULL)
NX_FREE(distances);
/* calculate distances */
NX_MALLOC(distances,float,numPoints*(numPoints-1)/2);
STATUS("Calculating distances");
CalculateDistance(data,distances,numPoints);
/* spaces for edges is allocated in TwoDView in InitGeomerty */
optimalValue = CheapestInsertion(self,data,distances,tsp_edges,numPoints);
[optimalValueField setFloatValue: optimalValue at: 0];
//NX_FREE(distances);
[optimizeButton setEnabled: YES];
return self ;
}
/*--------------------------------------------------------------------
Near Neighbor TSP
Mary Tork Roth/1991-Nov-30
--------------------------------------------------------------------*/
- doNearestNeighbor
{
if(distances != NULL)
NX_FREE(distances);
/* calculate distances */
NX_MALLOC(distances,float,numPoints*(numPoints-1)/2);
STATUS("Calculating distances");
CalculateDistance(data,distances,numPoints);
/* spaces for edges is allocated in TwoDView in InitGeomerty */
optimalValue = NearestNeighbor(self,data,distances,tsp_edges,numPoints);
[optimalValueField setFloatValue: optimalValue at: 0];
//NX_FREE(distances);
[optimizeButton setEnabled: YES];
return self ;
}
/* nearest addition */
- doNearestAddition
{
if(distances != NULL)
NX_FREE(distances);
/* calculate distances */
NX_MALLOC(distances,float,numPoints*(numPoints-1)/2);
STATUS("Calculating distances");
CalculateDistance(data,distances,numPoints);
/* spaces for edges is allocated in TwoDView in InitGeomerty */
optimalValue = NearestAddition(self,data,distances,tsp_edges,numPoints);
[optimalValueField setFloatValue: optimalValue at: 0];
//NX_FREE(distances);
[optimizeButton setEnabled: YES];
return self ;
}
- doFarthestInsertion
{
if(distances != NULL)
NX_FREE(distances);
/* calculate distances */
NX_MALLOC(distances,float,numPoints*(numPoints-1)/2);
STATUS("Calculating distances");
CalculateDistance(data,distances,numPoints);
/* spaces for edges is allocated in TwoDView in InitGeomerty */
optimalValue = FarthestInsertion(self,data,distances,tsp_edges,numPoints);
[optimalValueField setFloatValue: optimalValue at: 0];
[optimizeButton setEnabled: YES];
return self ;
}
/*--------------------------------------------------------------------
Called from within drawSelf:.
Assume that scaling has been setup,
This could be a general drawing routine for TSPs
Bill Roth/1991-Nov-18
--------------------------------------------------------------------*/
- drawTSP
{
int x,from,to;
#ifdef DEBUG
printf("inDrawTSP");
#endif
for(x=0;x<numPoints;x++) {
from = tsp_edges[x*2 + FROM];
to= tsp_edges[x*2 + TO];
if (from >= 0 && from < numPoints && to >= 0 && to < numPoints) {
PSnewpath();
PSmoveto(X(from),Y(from));
PSlineto(X(to),Y(to));
PSstroke();
NXPing();
}
}
return self ;
}
/*--------------------------------------------------------------------
Gets the time from the slider and sets the field to its value.
Bill Roth/1991-Dec-01
--------------------------------------------------------------------*/
- timeValue:sender
{
drawTime = [sender intValue];
[timeField setIntValue: drawTime at: 0];
return self ;
}
/* optimize the edges that exist.
*/
- Optimize
{
optimalValue = TourOptimization(self,data,distances,tsp_edges,
optimalValue,numPoints);
[optimalValueField setFloatValue: optimalValue at: 0];
[optimizeButton setEnabled: NO];
[self display];
return self;
}
/*--------------------------------------------------------------------
End of ObjC section
Bill Roth/1991-Dec-01
--------------------------------------------------------------------*/
#define FROM 0
#define TO 1
/* everything is allocated before it comes in */
extern kfrom(int l,int m,int n);
float simpleTSP(TwoDView *self,float *data,float *distances,int *edges,int n)
{
int x,i;
float opt;
char m[80];
opt =0.0;
for(x=0;x<n-1;x++) {/* calculate the distances*/
sprintf(m,"Doing edge %d",x);
[self->statusText setStringValue:m];
opt += distances[kfrom(x,x+1,n)];
edges[x*2 + FROM] = x; /* connect the first one to the 2nd one ...*/
edges[x*2 + TO] = x+1;
PSnewinstance();
for(i=0;i<=x;i++) {
[self drawEdge:X(i):Y(i):X(i+1):Y(i+1)];
NXPing();
}
[self->optimalValueField setFloatValue: opt at: 0];
usleep(self->drawTime);
}
edges[(n-1)*2+FROM] = n-1;
edges[(n-1)*2+TO] = 0;
opt += distances[kfrom(0,(n-1),n)];
PSnewinstance();
for(i=0;i<n-1;i++) {
[self drawEdge:X(i):Y(i):X(i+1):Y(i+1)];
}
[self drawEdge:X(n-2):Y(n-2):X(0):Y(0)];// connect to the beginning
NXPing();
return opt;
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.