travel.c

Travelling saleman by C++

/*
 *  travel.c
 *  
 * Phil Cox, B00XXXXXX
 * Login: pcox
 * CSCI2132: Assignment 3
 *
 */

#include <math.h>
#include <stdlib.h>
#include "list.h"

double travel(struct node **done)
{
	/* Construct a tour using the nearest neighbour heuristic
	   and return its length */
	
	struct node *toDo, *start, *previous, *p;
	double x, y, min, d, tourlen=0;
	
	/* If the list of points is empty or consists of a single
	   point, the tour length os 0 */
	if((start = *done) == NULL || (toDo = (*done)->next) == NULL)
		return(tourlen);

	(*done)->next = NULL;	
	while (toDo->next != NULL)
	{
		previous = NULL;
		x = (*done)->x;
		y = (*done)->y;
		min = pow(x-toDo->x,2)+pow(y-toDo->y,2);
		
		/* Look for an unvisited point which is closer to the most
		   recently visited point than the first point on the
		   unvisited list */
		for (p=toDo ; p->next != NULL; p=p->next)
			if (min > (d=pow(x-p->next->x,2)+pow(y-p->next->y,2))) {
				min = d;
				previous = p;
			}
		if (previous != NULL) {     /* The first unvisited point is the closest  */
			p = previous->next;
			previous->next = p->next;
		}
		else {                      /* Some other unvisited point is the closest */
			p = toDo;
			toDo = toDo->next;
		}
		p->next = *done;           /* Move the point to the visited list        */
		*done = p;
		tourlen += sqrt(min);      /* Update the tour length                    */
	}
	
	/* One unvisited point remains: add it the the visited list and add the
	   tour length its distances from the last and first visited points */
	toDo->next = *done;
	tourlen += sqrt(pow((*done)->x-toDo->x,2)+pow((*done)->y-toDo->y,2)) 
		+ sqrt(pow(start->x-toDo->x,2)+pow(start->y-toDo->y,2));
	*done = toDo;
	
	return(tourlen);
}