CITIES
City Distance Tools
CITIES,
a C++ library which
works with problems involving intercity distances.
Such problems include:

traveling salesman problems (connected path through every city);

Kmeans calculations (find M spots that minimize total of the
distance from each city to its nearest spot);

Kmedians calculations (make M of the cities "special", to minimize
the total distance from each city to its nearest special city);

Weighted Kmeans or Kmedians (let the population of each city
be used as a weight, which makes some cities more important);

Minimal spanning trees (construct the shortest highway
system that connects all the cities, using only straight paths
from one city to another (ignore the possibility that two roads
could cross, or that a Yshaped connector between three cities
might be cheaper);

Voronoi diagrams (assign each spot of land to the nearest city,
making "provinces");
Licensing:
The computer code and data files described and made available on this web page
are distributed under
the GNU LGPL license.
Languages:
CITIES is available in
a C++ version and
a FORTRAN90 version and
a MATLAB version.
Related Data and Programs:
ASA058,
a C++ library which
contains the original text of the Sparks clustering algorithm.
ASA136,
a C++ library which
implements the KMeans algorithm.
CITIES,
a dataset directory which
contains a number of city distance datasets.
cities_test
FLOYD,
a C++ library which
implements Floyd's algorithm for finding the shortest distance between
pairs of nodes on a directed graph.
KMEANS,
a C++ library which
treats the Kmeans
problem of grouping a discrete set of N points into K clusters.
POINT_MERGE,
a C++ library which
considers N points in M dimensional space, and counts or indexes
the unique or "tolerably unique" items.
SPAETH,
a dataset collection which
contains a set of test data.
SPAETH2,
a dataset collection which
contains a set of test data.
TSP,
a dataset directory which
contains test data for the traveling salesperson problem;
Reference:

Franz Aurenhammer,
Voronoi diagrams 
a study of a fundamental geometric data structure,
ACM Computing Surveys,
Volume 23, Number 3, pages 345405, September 1991.

John Burkardt, Max Gunzburger, Janet Peterson, Rebecca Brannon,
User Manual and Supporting Information for Library of Codes
for Centroidal Voronoi Placement and Associated Zeroth,
First, and Second Moment Determination,
Sandia National Laboratories Technical Report SAND20020099,
February 2002.

Marc de Berg, Marc Krevald, Mark Overmars,
Otfried Schwarzkopf,
Computational Geometry,
Springer, 2000.

Qiang Du, Vance Faber, Max Gunzburger,
Centroidal Voronoi Tessellations: Applications and Algorithms,
SIAM Review, Volume 41, 1999, pages 637676.

Alan Gibbons,
Algorithmic Graph Theory,
Cambridge University Press, 1985.

John Hartigan, M A Wong,
Algorithm AS 136: A KMeans Clustering Algorithm,
Applied Statistics,
Volume 28, Number 1, 1979, pages 100108.

Barry Joe,
GEOMPACK  a software package for the generation of meshes
using geometric algorithms,
Advances in Engineering Software,
Volume 13, pages 325331, 1991.

Hang Tong Lau,
Algorithms on Graphs,
Tab Books, 1989.

Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Sung Nok Chiu,
Spatial Tesselations:
Concepts and Applications of Voronoi Diagrams,
Second Edition,
Wiley, 2000.

Joseph O'Rourke,
Computational Geometry,
Cambridge University Press,
Second Edition, 1998.

Helmut Spaeth,
Cluster Analysis Algorithms
for Data Reduction and Classification of Objects,
Ellis Horwood, 1980.

David Sparks,
Algorithm AS 58: Euclidean Cluster Analysis,
Applied Statistics,
Volume 22, Number 1, 1973,
pages 126130.
Source Code:
Last revised on 19 February 2020.