CITIES
City Distance Tools
CITIES
is a FORTRAN90 library which
works with problems involving intercity distances.
Such problems include:
-
traveling salesman problems (connected path through every city);
-
K-means calculations (find M spots that minimize total of the
distance from each city to its nearest spot);
-
K-medians calculations (make M of the cities "special", to minimize
the total distance from each city to its nearest special city);
-
Weighted K-means or K-medians (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 Y-shaped 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 FORTRAN90 library which
contains the original text of the Sparks
clustering algorithm.
ASA136,
a FORTRAN90 library which
implements the K-Means algorithm.
CITIES,
a dataset directory which
contains a number of city distance datasets.
DISTANCE_TO_POSITION,
a FORTRAN90 program which
estimates the positions of cities based on a city-to-city distance table.
DISTANCE_TO_POSITION_SPHERE,
a MATLAB program which
estimates the positions of cities on a sphere (such as the earth)
based on a city-to-city distance table.
FLOYD,
a FORTRAN90 library which
implements Floyd's algorithm for finding the shortest distance between pairs of
nodes on a directed graph.
GRAPH_REPRESENTATION,
a data directory which
contains examples of ways of representing abstract
mathematical graphs
KMEANS,
a FORTRAN90 library which
treats the K-means
problem of grouping a discrete set of N points into K clusters.
LAU_NP,
a FORTRAN90 library which
includes heuristic approaches
to certain NP-complete problems, including the traveling salesman
problem, the K-center problem and the K-median problem.
POINT_MERGE,
a FORTRAN90 library which
considers N points in M dimensional space, and counts or indexes
the unique or "tolerably unique" items.
SPAETH,
a FORTRAN90 library which
can cluster data according to various principles.
SPAETH,
a dataset collection which
contains a set of test data.
SPAETH2,
a FORTRAN90 library which
can cluster data according to various principles.
SPAETH2,
a dataset collection which
contains a set of test data.
TOMS456,
a FORTRAN77 library which
solves the routing problem, connecting some nodes
in a network.
TSP,
a dataset directory which
contains test data for the traveling salesperson problem;
TSP_BRUTE,
a FORTRAN90 program which
reads a file of city-to-city distances and solves the
traveling salesperson problem, using brute force.
Reference:
-
Franz Aurenhammer,
Voronoi diagrams -
a study of a fundamental geometric data structure,
ACM Computing Surveys,
Volume 23, Number 3, pages 345-405, 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 SAND2002-0099,
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 637-676.
-
Alan Gibbons,
Algorithmic Graph Theory,
Cambridge University Press, 1985.
-
John Hartigan, M A Wong,
Algorithm AS 136: A K-Means Clustering Algorithm,
Applied Statistics,
Volume 28, Number 1, 1979, pages 100-108.
-
Barry Joe,
GEOMPACK - a software package for the generation of meshes
using geometric algorithms,
Advances in Engineering Software,
Volume 13, pages 325-331, 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 126-130.
Source Code:
Examples and Tests:
-
cities_test.f90,
a sample problem.
-
spaeth2_09_dist.txt,
a distance table.
-
usca312_main.txt,
is the main file for 312 city locations in the US and Canada.
-
usca312_dms.txt,
the latitude and longitude of each city.
-
uscap_ll.txt,
the latitude and longitude of each capital.
-
uscap_xy.txt,
the (X,Y) coordinates of each capital using a cylindrical projection.
-
wg22_dist.txt,
a distance table.
-
wg22_xy.txt,
the (X,Y) coordinates of each city.
-
cities_test.txt,
the output file.
List of Routines:
-
CH_CAP capitalizes a single character.
-
CH_EQI is a case insensitive comparison of two characters for equality.
-
CH_TO_DIGIT returns the value of a base 10 digit.
-
DEGREES_TO_RADIANS converts an angle from degrees to radians.
-
DIST_TABLE_CHECK checks a distance table.
-
DMS_PRINT prints the latitude and longitude in degrees/minutes/seconds.
-
DMS_READ reads DMS data from a file.
-
DMS_TO_DIST creates a distance table from latitudes and longitudes.
-
DMS_TO_DISTANCE_EARTH finds the distance between two points on the earth.
-
DMS_TO_RADIANS converts degrees, minutes, seconds to radians.
-
DMS_TO_XY: Latitude/Longitude in DMS to XY coordinates.
-
DMS_WRITE writes a DMS latitude, longitude file.
-
FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
-
FILE_EXIST reports whether a file exists.
-
FILE_ROW_COUNT counts the number of row records in a file.
-
GET_UNIT returns a free FORTRAN unit number.
-
I4_SIGN evaluates the sign of an I4.
-
I4_TO_A returns the I-th alphabetic character.
-
LAT_CHAR returns a character for negative or positive latitude.
-
LL_DEGREES_TO_DIST creates a distance table from latitudes and longitudes.
-
LL_DEGREES_TO_DISTANCE_EARTH: distance between two points on the earth.
-
LL_DEGREES_TO_XY: Latitude/Longitude in degrees to XY coordinates.
-
LL_RAD_DIST_SPHERE: spherical distance, latitude and longitude in radians.
-
LONG_CHAR returns a character for negative or positive longitude.
-
MAIN_READ_CODE reads the name of the code file from the main file.
-
MAIN_READ_DIST reads the name of the distance file from the main file.
-
MAIN_READ_DMS reads the name of the DMS file from the main file.
-
MAIN_READ_GEOM reads the name of the geometry from the main file.
-
MAIN_READ_NAME reads the name of the name file from the main file.
-
MAIN_READ_SIZE reads the problem size N from the main file.
-
MAIN_READ_XY reads the name of the XY file from the main file.
-
POINT_TO_DIST_TABLE creates a distance table from Cartesian coordinates.
-
R8MAT_DATA_READ reads data from an R8MAT file.
-
R8MAT_HEADER_READ reads the header from an R8MAT file.
-
R8MAT_PRINT prints an R8MAT.
-
R8MAT_PRINT_SOME prints some of an R8MAT.
-
R8MAT_TRANSPOSE_PRINT prints an R8MAT, transposed.
-
R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
-
R8MAT_WRITE writes an R8MAT file.
-
R8VEC_PRINT prints a real vector.
-
R8VEC2_DATA_READ reads data from an R8VEC2 file.
-
R8VEC2_HEADER_READ reads the header from an R8VEC2 file.
-
R8VEC2_PRINT prints an R8VEC2.
-
R8VEC2_WRITE writes an R8VEC2 file.
-
S_CAT concatenates two strings to make a third string.
-
S_EQI is a case insensitive comparison of two strings for equality.
-
S_REP_ONE replaces the first occurrence of SUB1 with SUB2.
-
S_TO_I4 reads an I4 from a string.
-
S_TO_R8 reads an R8 from a string.
-
S_TO_R8VEC reads an R8VEC from a string.
-
S_TO_W reads the next blank-delimited word from a string.
-
S_WORD_COUNT counts the number of "words" in a string.
-
TIMESTAMP prints the current YMDHMS date as a time stamp.
-
WORD_NEXT_READ "reads" words from a string, one at a time.
You can go up one level to
the FORTRAN90 source codes.
Last revised on 19 May 2016.