/**
* An implementation of the algorithms and techniques described in
* Section 6-2 of the second edition of Steven Skiena's
* _The Algorithm Design Manual_.
*
* Author: Samuel A. Rebelsky
*
* Except for the portions taken directly from Skiena, this work is
* released as follows.
*
* Copyright (c) 2015 Samuel A. Rebelsky. All rights reserved.
*
* This code is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This code is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this code. If not, see .
*/
// +-------+---------------------------------------------------------
// | Notes |
// +-------+
/*
This is a "quick and dirty" solution. I have not always looked to
use the optimal or most reusable design. As Skiena suggests, the
running time of this program is likely to be much smaller than that
of the machine it guides, even when we use O(n^2) algorithms. We also
have m equal to n^2 in this problem, so some of our algorithms will
have to be O(n^2).
Although vertices are (x,y) points, we will generally refer to them
by number. That suggests that we will need to store them in an array.
*/
// +---------+-------------------------------------------------------
// | Headers |
// +---------+
#include
#include
#include
// +-------+---------------------------------------------------------
// | Types |
// +-------+
/**
* Points in the graph. It's a physical graph, so we give them
* x and y positions.
*/
struct Point
{
int x; // x position of the point
int y; // y position of the point
};
typedef struct Point Point;
/**
* Edges in the graph.
*/
struct Edge
{
int from;
int to;
double distance;
};
typedef struct Edge Edge;
/**
* Comparators for our sorting algorithm.
*/
typedef int (*comparator)(void *,void *);
/**
* States for visiting vertices.
*/
enum VState { UNVISITED, VISITED, PROCESSED };
typedef enum VState VState;
// +---------+-------------------------------------------------------
// | Globals |
// +---------+
int REPORT = 0;
// +---------+-------------------------------------------------------
// | Sorting |
// +---------+
/**
* It's a quick hack, so we're sorting with insertion sort.
*/
void
sort (void *values[], int n, comparator compare)
{
int i; // Counter for outer loop
int j; // Counter for inner loop
for (i = 1; i < n; i++)
{
int pos = i-1;
while ((pos >= 0) && (compare(values[i], values[pos]) < 0))
pos--;
pos++;
void *tmp = values[i];
for (j = i; j > pos; j--)
{
values[j] = values[j-1];
} // for j
values[pos] = tmp;
} // for i
} // sort
/**
* Order two nodes by their x coordinate (for "leftmost point")
*/
int
compare_by_x (void *p1, void *p2)
{
int x1 = ((Point *) p1)->x;
int x2 = ((Point *) p2)->x;
if (x1 < x2)
return -1;
else if (x1 > x2)
return 1;
else
return 0;
} // compare_by_x
/**
* Order two edges by their distance.
*/
int
compare_edges (void *e1, void *e2)
{
double d1 = ((Edge *) e1)->distance;
double d2 = ((Edge *) e2)->distance;
if (d1 < d2)
return -1;
else if (d1 > d2)
return 1;
else
return 0;
} // compare_edges
// +----------------------+------------------------------------------
// | Additional Utilities |
// +----------------------+
/**
* Square a number.
*/
double
square (double d)
{
return d*d;
} // square
/**
* Compute the distance from p1 to p2.
*/
double
distance (Point p1, Point p2)
{
return sqrt (square (p1.x - p2.x) + square (p1.y - p2.y));
} // distance
// +------------+----------------------------------------------------
// | Union Find |
// +------------+
// n.b. These implementations are based loosely on Union-Find in
// Skiena p. 200
int
find (int set_parent[], int i)
{
if (set_parent[i] == i)
{
return i;
}
else
{
return find (set_parent, set_parent[i]);
}
} // find
void
union_sets (int set_parent[], int set_size[], int s1, int s2)
{
int root1 = find (set_parent, s1);
int root2 = find (set_parent, s2);
if (root1 == root2)
return;
if (set_size[root1] > set_size[root2])
{
set_size[root1] += set_size[root2];
set_parent[root2] = root1;
}
else
{
set_size[root2] += set_size[root1];
set_parent[root1] = root2;
}
} // union_sets
// +-----------------+-----------------------------------------------
// | Core Algorithms |
// +-----------------+
/**
* Determine the total distance that the naive traversal method
* does on a set of points.
*/
double
naive (Point *points[], int n)
{
double dist = 0.0;
int p;
if (REPORT)
{
fprintf (stderr, "Starting naive algorithm ... ");
} // if (REPORT)
// Order the points by their x coordinate.
sort ((void **) points, n, compare_by_x);
Point start = { 0, 0 };
// Move the left and right arms to the leftmost point
dist = 2 * distance (start, *(points[0]));
if (REPORT)
{
fprintf (stderr, "Moving left and right arm to (%d,%d)\n",
points[0]->x, points[0]->y);
}
// The right arm starts at the leftmost point and moves to each subsequent
// point
for (p = 1; p < n; p++)
{
dist += distance (*(points[p-1]), *(points[p]));
if (REPORT)
{
fprintf (stderr, "Moving right arm to (%d,%d)\n",
points[p]->x, points[p]->y);
}
} // for
// And we're done
return dist;
} // naive
/**
* Determine the total distance that the smart traversal method
* does on a set of points.
*/
int
smart (Point *points[], int n)
{
int i, j; // Generic counter variables
// Make the MST. This code is inspired by the implementation of
// Prim's algorithm from pp. 194-195 of Skiena.
int e; // Counter variable for edges
int nedges = n-1; // Number of edges in MST
Edge edges[nedges]; // Edges in MST
Edge *edgesp[nedges]; // Pointers to edges in MST (for sorting)
double distance2[n]; // The distance to node i from the MST
VState state[n]; // The state of node i
int parent[n]; // The "parent" of node i in the MST.
int v; // The current vertex in Prim's algorithm
double dist; // Some computed distance.
// Set up edge pointers
for (i = 0; i < nedges; i++)
{
edgesp[i] = edges+i;
}
// Initialize the state of all nodes
for (i = 0; i < n; i++)
{
state[i] = UNVISITED;
} // for
// Start with node 0. (In Prim's, you can start with any node.)
v = 0;
distance2[v] = 0;
// Add the edges
for (e = 0; e < nedges; e++)
{
// Mark node v.
state[v] = PROCESSED;
// Update the minimum distance to all neighboring nodes.
for (i = 0; i < n; i++)
{
if (i != v)
{
dist = distance (*points[v], *points[i]);
if ( (state[i] == UNVISITED) ||
((state[i] == VISITED) && (dist < distance2[i])) )
{
state[i] = VISITED;
distance2[i] = dist;
parent[i] = v;
}
} // if (i != v)
} // for
// Find the unprocessed node with the smallest edge weight
v = 0;
dist = 0.0;
for (i = 1; i < n; i++)
{
if ( (state[i] == VISITED) &&
((state[v] == PROCESSED) || (dist > distance2[i])) )
{
dist = distance2[i];
v = i;
} // if
} // for
// Add it to the tree
edges[e].from = parent[v];
edges[e].to = v;
edges[e].distance = distance2[v];
} // for each edge
// Sort the edges in the MST by weight
sort ((void **) edgesp, nedges, compare_edges);
// Heuristic: Remove the top 1/4 to make clusters. (Skiena does not
// suggest a particular heuristic.) `individual` marks the start of
// the edges that we handle individually
int individual = (3 * nedges) / 4;
// Identify the clusters using union-find.
int set_parent[n];
int set_size[n];
for (i = 0; i < n; i++)
{
set_parent[i] = i;
set_size[i] = 1;
} // for
for (i = 0; i < individual; i++)
{
union_sets (set_parent, set_size, edgesp[i]->from, edgesp[i]->to);
}
// Process each smaller cluster using the naive algorithm.
// Note: We are not being careful about the order in which we process
// clusters.
dist = 0.0;
Point left = { 0, 0 }; // Position of left arm
Point right = { 0, 0 }; // Position of right arm
for (i = 0; i < n; i++)
{
// If we've identified a set
if (set_parent[i] == i)
{
dist += distance (left, *(points[i]));
left = *(points[i]);
for (j = 0; j < n; j++)
{
if ((j != i) && (find (set_parent, j)))
{
dist += distance (right, *(points[j]));
right = *(points[j]);
} // if
} // for j
} // if
} // for i
// And we're done.
return dist;
} // smart
// +-------------+---------------------------------------------------
// | I/O Helpers |
// +-------------+
/**
* Extract an integer from a string. Returns 1 upon success and 0
* upon failure.
*/
int
str2int (char *str, int *i)
{
char *end;
*i = strtol(str, &end, 10);
return (*end == '\0');
} // str2int
/**
* Print usage information.
*/
void
usage (int argc, char *argv[])
{
fprintf (stderr, "Usage: %s POINTS TRIALS\n", argv[0]);
fprintf (stderr, " where POINTS is the number of points");
fprintf (stderr, " and TRIALS is the number of repetitions");
} // usage
// +------+----------------------------------------------------------
// | Main |
// +------+
int
main (int argc, char *argv[])
{
int npoints; // The number of points we will generate
int ntrials; // The number of trials
int p; // Loop variable for points
int t; // Loop variable for trials
double naive_distance = 0;
// The total amount of distance the naive algorithm traveled
double smart_distance = 0;
// The total amount of distance the smart algorithm traveled
// TO DO: Seed the random number generator.
// Process parameter list
if (argc != 3)
{
usage (argc, argv);
return 1;
}
if (! str2int (argv[1], &npoints))
{
fprintf (stderr, "Invalid number of points: %s\n", argv[1]);
usage (argc, argv);
return 2;
}
if (! str2int (argv[2], &ntrials))
{
fprintf (stderr, "Invalid number of trials: %s\n", argv[2]);
usage (argc, argv);
return 3;
}
// Special debugging
if (ntrials < 3)
{
REPORT = 1;
}
// Do the trials
for (t = 0; t < ntrials; t++)
{
// Generate the list of points
Point points[npoints];
Point *points_naive[npoints];
Point *points_smart[npoints];
for (p = 0; p < npoints; p++)
{
points[p].x = random() % 100;
points[p].y = random() % 100;
points_naive[p] = points_smart[p] = (points + p);
}
// Run each algorithm
naive_distance += naive (points_naive, npoints);
smart_distance += smart (points_smart, npoints);
} // for each trial
// Print out the results
printf ("Average distance, naive algorithm: %lf\n", naive_distance / ntrials);
printf ("Average distance, smart algorithm: %lf\n", smart_distance / ntrials);
// And we're done
return 0;
} // main