cities

cities, a Python 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 information on this web page is distributed under the MIT license.

Languages:

cities is available in a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

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

floyd, a Python 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:

• cities.py, the source code.
• cities.sh, calls all the tests.
• cities.txt, the output file.

• 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.