CITIES
City Distance Tools

CITIES is a MATLAB 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 MATLAB library which contains the original text of the Sparks clustering algorithm.

ASA136, a MATLAB library which implements the K-Means algorithm.

CITIES, a dataset directory which contains a number of city distance datasets.

DISTANCE_TO_POSITION, a MATLAB 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 MATLAB library which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.

TSP, a dataset directory which contains test data for the traveling salesperson problem;

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, pages 345-405, September 1991.
2. 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.
3. Marc de Berg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000.
4. Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review, Volume 41, 1999, pages 637-676.
5. Alan Gibbons,
   Algorithmic Graph Theory,
   Cambridge University Press, 1985.
6. John Hartigan, M A Wong,
   Algorithm AS 136: A K-Means Clustering Algorithm,
   Applied Statistics,
   Volume 28, Number 1, 1979, pages 100-108.
7. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, pages 325-331, 1991.
8. Hang Tong Lau,
   Algorithms on Graphs,
   Tab Books, 1989.
9. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Sung Nok Chiu,
   Spatial Tesselations: Concepts and Applications of Voronoi Diagrams,
   Second Edition,
   Wiley, 2000.
10. Joseph O'Rourke,
    Computational Geometry,
    Cambridge University Press,
    Second Edition, 1998.
11. Helmut Spaeth,
    Cluster Analysis Algorithms for Data Reduction and Classification of Objects,
    Ellis Horwood, 1980.
12. David Sparks,
    Algorithm AS 58: Euclidean Cluster Analysis,
    Applied Statistics,
    Volume 22, Number 1, 1973,
    pages 126-130.

Source Code:

• dist_table_check.m, checks a distance table.
• file_column_count.m, counts the number of columns in the first line of a file.
• file_exist.m, reports whether a file exists.
• file_row_count.m, counts the number of row records in a file.
• i4_sign.m, returns the sign of an I4.
• i4_to_a.m, returns the I-th alphabetic character;
• ll_rad_sphere_dist.m, computes the great circle distance between two points on a sphere of given radius, where the positions are given as latitude and longitude in radians.
• point_to_dist_table.m, returns a distance table given a set of point coordinates.
• r8mat_data_read.m, reads a table from an R8MAT file.
• r8mat_header_read.m, reads a table header from an R8MAT file.
• r8mat_print.m, prints an R8MAT.
• r8mat_print_some.m, prints some of an R8MAT.
• r8mat_transpose_print.m, prints the transpose of an R8MAT.
• r8mat_transpose_print_some.m, prints the transpose of some of an R8MAT.
• r8mat_write.m, writes an R8MAT file.
• r8vec_print.m, prints an R8VEC;
• s_word_count.m, counts the number of words in a string.
• timestamp.m, prints the current YMDHMS date as a timestamp.

Examples and Tests:

• cities_test.m, calls all the tests.
• cities_test01.m, tests XY_TO_DIST.
• spaeth2_09.txt, a distance table.
• cities_test_output.txt, the output file.

You can go up one level to the MATLAB source codes.