cities
cities,
a MATLAB code 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 MIT license
Languages:
cities is available in
a C++ version and
a FORTRAN90 version and
a MATLAB version.
Related Data and Programs:
asa058,
a MATLAB code which
contains the original text of the Sparks clustering algorithm.
asa136,
a MATLAB code which
implements the K-Means algorithm.
cities,
a dataset directory which
contains a number of city distance datasets.
cities_test
distance_to_position,
a MATLAB code which
estimates the positions of cities based on a city-to-city distance table.
distance_to_position_sphere,
a MATLAB code which
estimates the positions of cities on a sphere (such as the earth)
based on a city-to-city distance table.
floyd,
a MATLAB code 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;
Source Code:
-
ch_cap.m
returns the capitalized version of a character;
-
degrees_to_radians.m,
converts degrees to radians.
-
dist_table_check.m,
checks a distance table.
-
dist_table_check_test.m
-
dms_print.m,
prints the latitude and longitude in degrees/minutes/seconds.
-
dms_to_distance_earth.m,
finds the distance between two points on the earth.
-
dms_to_radians.m,
converts degrees, minutes, seconds to radians.
-
dms_to_xy.m,
converts Latitude/Longitude in DMS to XY coordinates.
-
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;
-
lat_char.m,
returns a character for negative or positive latitude.
-
ll_degrees_to_distance.m,
creates a distance table from latitudes and longitudes.
-
ll_degrees_to_distance_earth.m,
distance between two points on the earth.
-
ll_degrees_to_xy.m,
convert Latitude/Longitude in degrees to XY coordinates on an unrolled cylinder.
-
ll_degrees_to_xyz.m,
convert Latitude/Longitude in degrees to XYZ coordinates on a sphere.
-
ll_rad_dist_sphere.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.
-
lon_char.m,
returns a character for negative or positive longitude.
-
main_read_size.m,
reads the problem size N from the main file.
-
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_eqi.m,
is TRUE if two strings are equal, ignoring case and trailing blanks;
-
s_len_trim.m
returns the length of a string to the last nonblank;
-
s_word_count.m,
counts the number of words in a string.
Last revised on 14 December 2018.