Mastering Algorithms With C - Kyle Loudon [210]
* *
*****************************************************************************/
list_init(tour, NULL);
/*****************************************************************************
* *
* Initialize all of the vertices in the graph. *
* *
*****************************************************************************/
found = 0;
for (element = list_head(vertices); element != NULL; element =
list_next(element)) {
tsp_vertex = list_data(element);
if (match(tsp_vertex, start)) {
/***********************************************************************
* *
* Start the tour at the start vertex. *
* *
***********************************************************************/
if (list_ins_next(tour, list_tail(tour), tsp_vertex) != 0) {
list_destroy(tour);
return -1;
}
/***********************************************************************
* *
* Save the start vertex and its coordinates. *
* *
***********************************************************************/
tsp_start = tsp_vertex;
x = tsp_vertex->x;
y = tsp_vertex->y;
/***********************************************************************
* *
* Color the start vertex black. *
* *
***********************************************************************/
tsp_vertex->color = black;
found = 1;
}
else {
/***********************************************************************
* *
* Color all other vertices white. *
* *
***********************************************************************/
tsp_vertex->color = white;
}
}
/*****************************************************************************
* *
* Return if the start vertex was not found. *
* *
*****************************************************************************/
if (!found) {
list_destroy(tour);
return -1;
}
/*****************************************************************************
* *
* Use the nearest-neighbor heuristic to compute the tour. *
* *
*****************************************************************************/
i = 0;
while (i < list_size(vertices) - 1) {
/**************************************************************************
* *
* Select the white vertex closest to the previous vertex in the tour. *
* *
**************************************************************************/
minimum = DBL_MAX;
for (element = list_head(vertices); element != NULL; element =
list_next(element)) {
tsp_vertex = list_data(element);
if (tsp_vertex->color == white) {
distance = sqrt(pow(tsp_vertex->x-x,2.0) + pow(tsp_vertex->y-y,2.0));
if (distance < minimum) {
minimum = distance;
selection = tsp_vertex;
}
}
}
/**************************************************************************
* *
* Save the coordinates of the selected vertex. *
* *
**************************************************************************/
x = selection->x;
y = selection->y;
/**************************************************************************
* *
* Color the selected vertex black. *
* *
**************************************************************************/
selection->color = black;
/**************************************************************************
* *
* Insert the selected vertex into the tour. *
* *
**************************************************************************/
if (list_ins_next(tour, list_tail(tour), selection) != 0) {
list_destroy(tour);
return -1;
}
/**************************************************************************
* *
* Prepare to select the next vertex. *
* *
**************************************************************************/
i++;
}
/*****************************************************************************
* *
* Insert the start vertex again to complete the tour. *
* *
*****************************************************************************/
if (list_ins_next(tour, list_tail(tour), tsp_start) != 0) {
list_destroy(tour);
return -1;