Welcome to TSPLIB 95’s documentation!¶

TSPLIB 95¶

TSPLIB 95 is a library for working with TSPLIB 95 files.

Free software: Apache Software License 2.0
Documentation: https://tsplib95.readthedocs.io.

For now…

documentation is not complete
only 3.6 is supported (I am willing to remove f-strings if there is support; I might also spontaneously decide to do that)
there are some things missing (being able to write out a TSPLIB file chief among them)

Features¶

read and use TSPLIB95 files like a boss
easily convert problems into networkx.Graph instances
supports and implements the following EDGE_WEIGHT_TYPE s
- EXPLICIT
- EUC_2D
- EUC_3D
- MAX_2D
- MAX_3D
- MAN_2D
- MAN_3D
- CEIL_2D
- GEO
- ATT
- XRAY1
- XRAY2
supports the following EDGE_WEIGHT_FORMAT s
- FULL_MATRIX
- UPPER_ROW
- LOWER_ROW
- UPPER_DIAG_ROW
- LOWER_DIAG_ROW
- UPPER_COL
- LOWER_COL
- UPPER_DIAG_COL
- LOWER_DIAG_COL
supports SPECIAL FUNCTION edge weights too

It also has a CLI program to print a tabular summary of one or more TSPLIB95 files. No idea why anyone would want that, but there you have it.

Credits¶

See TSPLIB for original details, including file format specification, C++ code, and sample problems.

This package was created with Cookiecutter and the audreyr/cookiecutter-pypackage project template.

Installation¶

Stable release¶

To install TSPLIB 95, run this command in your terminal:

$ pip install tsplib95

This is the preferred method to install TSPLIB 95, as it will always install the most recent stable release.

If you don’t have pip installed, this Python installation guide can guide you through the process.

From sources¶

The sources for TSPLIB 95 can be downloaded from the Github repo.

You can either clone the public repository:

$ git clone git://github.com/rhgrant10/tsplib95

Or download the tarball:

$ curl  -OL https://github.com/rhgrant10/tsplib95/tarball/master

Once you have a copy of the source, you can install it with:

$ python setup.py install

Usage¶

To use TSPLIB 95 in a project:

import tsplib95

Loading problems and solutions is easy:

>>> problem = tsplib95.load_problem('path/to/ulysses16.tsp')
>>> problem
<tsplib95.models.Problem at 0x105030d30>
>>> solution = tsplib95.load_solution('path/to/ulysses16.opt.tour')
>>> solution
<tsplib95.models.Solution at 0x104314d68>

Note

tsplib95 does not ship with any problem files itself. The problems and solutions are standalone files. load_problem and load_solution take a filesystem path as an argument, not the name of a problem. Feel free to download and use any of the original TSPLIB problem files commonly used and referenced by the community, find others, or write your own. Any file that adheres to the TSPLIB95 file format standards should load without error.

Both have the base attributes, but let’s focus on a problem object first:

>>> problem.name  # not specified
>>> problem.comment
'Odyssey of Ulysses (Groetschel/Padberg)'
>>> problem.type
'TSP'
>>> problem.dimension
16

Problems can be specified in several ways according to the TSPLIB format. Here’s how this particular problem is specified:

>>> problem.display_data_type
'COORD_DISPLAY'
>>> problem.edge_data_format    # not specified
>>> problem.edge_weight_format  # not specified
>>> problem.edge_weight_type
'GEO'
>>> problem.node_coord_type     # not specified

Regardless of how the problem is specified, nodes and edges are accessible in the same way. Nodes and edges are returned as generators since there could be a significant number of them:

>>> list(problem.get_nodes())
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
>>> list(problem.get_edges())[:5]
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5)]

We can find the weight of the edge between nodes 1 and, say, 11, using wfunc:

>>> problem.wfunc
<function tsplib95.models.Problem._create_distance_function.<locals>.adapter>
>>> problem.wfunc(1, 11)
26

If the distance function for the problem is “SPECIAL” you must provide a custom distance function. The function must accept two node coordinates and return the distance between them. Let’s create one:

>>> import random
>>> import math
>>>
>>> def euclidean_2d_jitter(a, b):
...     x1, y1 = a
...     x2, y2 = b
...     dist = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
...     return dist * random.random() * 2
...

Of course, you may want to leverage the existing distance functions:

>>> from tsplib95 import distances
>>>
>>> def euclidean_jitter(a, b):
...    dist = distances.euclidean(a, b)  # works for n-dimensions
...    return dist * random.random() * 2
...

You can either provide that function at load time or you can also set it on an existing Problem instance:

>>> problem = tsplib95.load_problem('example.tsp', special=euclidean_2d_jitter)
>>> problem.special = euclidean_jitter

Note that setting the special function on a problem that has explicit edge weights has no effect.

You can get a networkx.Graph instance from the problem:

>>> G = problem.get_graph()
>>> G.nodes
NodeView((1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16))

And you can trace the tours found in a Solution:

>>> solution = tsplib95.load_solution('ulysses16.opt.tour')
>>> problem.trace_tours(solution)
[73]

Note that it returns a list of tour distances, one for each tour defined in the solution.

API Documentation¶

Model classes¶

class tsplib95.models.File(**kwargs)[source]¶

Bases: object

Base file format type.

This class isn’t meant to be used directly. It contains the common keyword values among all formats. Note that all information is optional. Missing information values are set to None. See the official TSPLIB documentation for more details.

name - NAME

comment - COMMENT

type - TYPE

dimension - DIMENSION

class tsplib95.models.Problem(special=None, **kwargs)[source]¶

Bases: tsplib95.models.File

A TSPLIB problem file.

Provides a python-friendly way to access the fields of a TSPLIB probem. The fields are mapped as follows:

name - NAME

comment - COMMENT

type - TYPE

dimension - DIMENSION

capacity - CAPACITY

edge_weight_type - EDGE_WEIGHT_TYPE

edge_weight_format - EDGE_WEIGHT_FORMAT

edge_data_format - EDGE_DATA_FORMAT

node_coord_type - NODE_COORD_TYPE

display_data_type - DISPLAY_DATA_TYPE

depots - DEPOT_SECTION

demands - DEMAND_SECTION

node_coords - NODE_COORD_SECTION

edge_weights - EDGE_WEIGHT_SECTION

display_data - DISPLAY_DATA_SECTION

edge_data - EDGE_DATA_SECTION

fixed_edges - FIXED_EDGES_SECTION

For problems that require a special distance function, you must set the special function in one of two ways:

>>> problem = Problem(special=func, ...)  # at creation time
>>> problem.special = func                # on existing problem

Special distance functions are ignored for explicit problems but are required for some.

Regardless of problem type or specification, the weight of the edge between two nodes given by index can always be found using wfunc. For example, to get the weight of the edge between nodes 13 and 6:

>>> problem.wfunc(13, 6)
87

The length of a problem is the number of nodes it contains.

get_display(i)[source]¶

Return the display data for node at index i, if available.

Parameters:	i (int) – node index
Returns:	display data for node i

get_edges()[source]¶

Return an iterator over the edges.

Returns:	edges
Return type:	iter

get_graph()[source]¶

Return the corresponding networkx.Graph instance.

If the graph is not symmetric then a DiGraph is returned. If present, the coordinates of each node are set to the coord key, and each edge has an is_fixed key that is True if the edge is in the list of fixed edges.

Returns:	graph

get_nodes()[source]¶

Return an iterator over the nodes.

Returns:	nodes
Return type:	iter

is_complete()[source]¶

Return True if the problem specifies a complete graph.

Return type:	bool

is_depictable()[source]¶

Return True if the problem is designed to be depicted.

Return type:	bool

is_explicit()[source]¶

Return True if the problem specifies explicit edge weights.

Return type:	bool

is_full_matrix()[source]¶

Return True if the problem is specified as a full matrix.

Return type:	bool

is_special()[source]¶

Return True if the problem requires a special distance function.

Return type:	bool

is_symmetric()[source]¶

Return True if the problem is not asymmetrical.

Note that even if this method returns False there is no guarantee that there are any two nodes with an asymmetrical distance between them.

Return type:	bool

is_weighted()[source]¶

Return True if the problem has weighted edges.

Return type:	bool

special¶: Special distance function

trace_tours(solution)[source]¶

Calculate the total weights of the tours in the given solution.

Parameters:	solution (`Solution`) – solution with tours to trace
Returns:	one or more tour weights
Return type:	list

class tsplib95.models.Solution(**kwargs)[source]¶

Bases: tsplib95.models.File

A TSPLIB solution file containing one or more tours to a problem.

name - NAME

comment - COMMENT

type - TYPE

dimension - DIMENSION

tours - TOUR_SECTION

The length of a solution is the number of tours it contains.

Matrix weights¶

class tsplib95.matrix.FullMatrix(numbers, size, min_index=0)[source]¶

Bases: tsplib95.matrix.Matrix

A complete square matrix.

Parameters:	numbers (list) – the elements of the matrix size (int) – the width (also height) of the matrix min_index (int) – the minimum index

get_index(i, j)[source]¶

Return the linear index for the element at (i,j).

Parameters:	i (int) – row j (int) – column
Returns:	linear index for element (i,j)
Return type:	int

class tsplib95.matrix.HalfMatrix(numbers, size, min_index=0)[source]¶

Bases: tsplib95.matrix.Matrix

A triangular half-matrix.

Parameters:	numbers (list) – the elements of the matrix size (int) – the width (also height) of the matrix min_index (int) – the minimum index

has_diagonal = True¶: True if the half-matrix includes the diagonal

value_at(i, j)[source]¶

Get the element at row i and column j.

Parameters:	i (int) – row j (int) – column
Returns:	value of element at (i,j)

class tsplib95.matrix.LowerCol(numbers, size, min_index=0)[source]¶: Bases: tsplib95.matrix.UpperRow

class tsplib95.matrix.LowerDiagCol(numbers, size, min_index=0)[source]¶: Bases: tsplib95.matrix.UpperDiagRow

class tsplib95.matrix.LowerDiagRow(numbers, size, min_index=0)[source]¶

Bases: tsplib95.matrix.HalfMatrix

Lower-triangular matrix that includes the diagonal.

Parameters:	numbers (list) – the elements of the matrix size (int) – the width (also height) of the matrix min_index (int) – the minimum index

get_index(i, j)[source]¶

Return the linear index for the element at (i,j).

Parameters:	i (int) – row j (int) – column
Returns:	linear index for element (i,j)
Return type:	int

has_diagonal = True¶

class tsplib95.matrix.LowerRow(numbers, size, min_index=0)[source]¶

Bases: tsplib95.matrix.LowerDiagRow

Lower-triangular matrix that does not include the diagonal.

Parameters:	numbers (list) – the elements of the matrix size (int) – the width (also height) of the matrix min_index (int) – the minimum index

has_diagonal = False¶

class tsplib95.matrix.Matrix(numbers, size, min_index=0)[source]¶

Bases: object

A square matrix created from a list of numbers.

Elements are accessible using matrix notation. Negative indexing is not allowed.

Parameters:	numbers (list) – the elements of the matrix size (int) – the width (also height) of the matrix min_index (int) – the minimum index

get_index(i, j)[source]¶

Return the linear index for the element at (i,j).

Parameters:	i (int) – row j (int) – column
Returns:	linear index for element (i,j)
Return type:	int

is_valid_row_column(i, j)[source]¶

Return True if (i,j) is a row and column within the matrix.

Parameters:	i (int) – row j (int) – column
Returns:	whether (i,j) is within the bounds of the matrix
Return type:	bool

value_at(i, j)[source]¶

Get the element at row i and column j.

Parameters:	i (int) – row j (int) – column
Returns:	value of element at (i,j)

class tsplib95.matrix.UpperCol(numbers, size, min_index=0)[source]¶: Bases: tsplib95.matrix.LowerRow

class tsplib95.matrix.UpperDiagCol(numbers, size, min_index=0)[source]¶: Bases: tsplib95.matrix.LowerDiagRow

class tsplib95.matrix.UpperDiagRow(numbers, size, min_index=0)[source]¶

Bases: tsplib95.matrix.HalfMatrix

Upper-triangular matrix that includes the diagonal.

Parameters:	numbers (list) – the elements of the matrix size (int) – the width (also height) of the matrix min_index (int) – the minimum index

get_index(i, j)[source]¶

Return the linear index for the element at (i,j).

Parameters:	i (int) – row j (int) – column
Returns:	linear index for element (i,j)
Return type:	int

has_diagonal = True¶

class tsplib95.matrix.UpperRow(numbers, size, min_index=0)[source]¶

Bases: tsplib95.matrix.UpperDiagRow

Upper-triangular matrix that does not include the diagonal.

Parameters:	numbers (list) – the elements of the matrix size (int) – the width (also height) of the matrix min_index (int) – the minimum index

has_diagonal = False¶

Distance functions¶

tsplib95.distances.euclidean(start, end, round=<function nint>)[source]¶

Return the Euclidean distance between start and end.

Parameters:	start (tuple) – n-dimensional coordinate end (tuple) – n-dimensional coordinate round (callable) – function to use to round the result
Returns:	rounded distance

tsplib95.distances.geographical(start, end, round=<function nint>, radius=6378.388)[source]¶

Return the geographical distance between start and end.

Parameters:	start (tuple) – n-dimensional coordinate end (tuple) – n-dimensional coordinate round (callable) – function to use to round the result radius (float) – the radius of the Earth
Returns:	rounded distance

tsplib95.distances.manhattan(start, end, round=<function nint>)[source]¶

Return the Manhattan distance between start and end.

Parameters:	start (tuple) – n-dimensional coordinate end (tuple) – n-dimensional coordinate round (callable) – function to use to round the result
Returns:	rounded distance

tsplib95.distances.maximum(start, end, round=<function nint>)[source]¶

Return the Maximum distance between start and end.

Parameters:	start (tuple) – n-dimensional coordinate end (tuple) – n-dimensional coordinate round (callable) – function to use to round the result
Returns:	rounded distance

tsplib95.distances.pseudo_euclidean(start, end, round=<function nint>)[source]¶

Return the pseudo-Euclidean distance between start and end.

Parameters:	start (tuple) – n-dimensional coordinate end (tuple) – n-dimensional coordinate round (callable) – function to use to round the result
Returns:	rounded distance

tsplib95.distances.xray(start, end, sx=1, sy=1, sz=1, round=<function icost>)[source]¶

Return x-ray crystallography distance.

Parameters:	start (tuple) – 3-dimensional coordinate end (tuple) – 3-dimensional coordinate sx (float) – x motor speed sy (float) – y motor speed sz (float) – z motor speed
Returns:	distance

Utilities¶

tsplib95.utils.load_problem(filepath, special=None)[source]¶

Load a problem at the given filepath.

Parameters:	filepath (str) – path to a TSPLIB problem file special (callable) – special/custom distance function
Returns:	problem instance
Return type:	`Problem`

tsplib95.utils.load_solution(filepath)[source]¶

Load a solution at the given filepath.

Parameters:	filepath (str) – path to a TSPLIB solution file
Returns:	solution instance
Return type:	`Solution`

tsplib95.utils.load_unknown(filepath)[source]¶

Load a TSPLIB file.

Parameters:	filepath (str) – path to a TSPLIB problem file
Returns:	either a problem or solution instance

Exceptions¶

class tsplib95.parser.ParsingError[source]¶

Error raised when a given file cannot be parsed.

This indicates the file does not conform to the standard TSPLIB95 file format.

Contributing¶

Contributions are welcome, and they are greatly appreciated! Every little bit helps, and credit will always be given.

You can contribute in many ways:

Types of Contributions¶

Report Bugs¶

Report bugs at https://github.com/rhgrant10/tsplib95/issues.

If you are reporting a bug, please include:

Your operating system name and version.
Any details about your local setup that might be helpful in troubleshooting.
Detailed steps to reproduce the bug.

Fix Bugs¶

Look through the GitHub issues for bugs. Anything tagged with “bug” and “help wanted” is open to whoever wants to implement it.

Implement Features¶

Look through the GitHub issues for features. Anything tagged with “enhancement” and “help wanted” is open to whoever wants to implement it.

Write Documentation¶

TSPLIB 95 could always use more documentation, whether as part of the official TSPLIB 95 docs, in docstrings, or even on the web in blog posts, articles, and such.

Submit Feedback¶

The best way to send feedback is to file an issue at https://github.com/rhgrant10/tsplib95/issues.

If you are proposing a feature:

Explain in detail how it would work.
Keep the scope as narrow as possible, to make it easier to implement.
Remember that this is a volunteer-driven project, and that contributions are welcome :)

Get Started!¶

Ready to contribute? Here’s how to set up tsplib95 for local development.

Fork the tsplib95 repo on GitHub.

Clone your fork locally:

$ git clone git@github.com:your_name_here/tsplib95.git

Install your local copy into a virtualenv. Assuming you have virtualenvwrapper installed, this is how you set up your fork for local development:
```
$ mkvirtualenv tsplib95
$ cd tsplib95/
$ python setup.py develop
```
Create a branch for local development:
```
$ git checkout -b name-of-your-bugfix-or-feature
```
Now you can make your changes locally.
When you’re done making changes, check that your changes pass flake8 and the tests, including testing other Python versions with tox:
```
$ flake8 tsplib95 tests
$ python setup.py test or py.test
$ tox
```
To get flake8 and tox, just pip install them into your virtualenv.

Commit your changes and push your branch to GitHub:

$ git add .
$ git commit -m "Your detailed description of your changes."
$ git push origin name-of-your-bugfix-or-feature

Submit a pull request through the GitHub website.

Pull Request Guidelines¶

Before you submit a pull request, check that it meets these guidelines:

The pull request should include tests.
If the pull request adds functionality, the docs should be updated. Put your new functionality into a function with a docstring, and add the feature to the list in README.rst.
The pull request should work for Python 2.7, 3.4, 3.5 and 3.6, and for PyPy. Check https://travis-ci.org/rhgrant10/tsplib95/pull_requests and make sure that the tests pass for all supported Python versions.

Tips¶

To run a subset of tests:

$ py.test tests.test_tsplib95

Deploying¶

A reminder for the maintainers on how to deploy. Make sure all your changes are committed (including an entry in HISTORY.rst). Then run:

$ bumpversion patch # possible: major / minor / patch
$ git push
$ git push --tags

Travis will then deploy to PyPI if tests pass.

Credits¶

Development Lead¶

Robert Grant <rhgrant10@gmail.com>

Contributors¶

Michael Ritter <michael.ritter^P@tum.de>

History¶

0.4.0 (2019-09-21)¶

All expected parsing errors are now raised as ParsingError rather than the base Exception type.
Fix name of distance paramter to distances.geographical. Previously it was “diameter” but was used as a radius. It is now “radius”.
Relax restriction on networkx version (now ~=2.1)
Add documentation for each problem field
Other minor documentation changes
Add offical 3.7 support
Add missing history entry for v0.3.3
Remove some dead code

0.3.3 (2019-03-24)¶

Fix parsing bug for key-value lines whose value itself contains colons

0.3.2 (2018-10-07)¶

Fix bug in Problem.is_complete that produced a TypeError when run
Fix bug in Problem.is_depictable that produced a TypeError when run
Fix bug in Problem.get_display that produced an AttributeError when run
Added some unit tests for the Problem class
Added some unit tests for the parser module

0.3.1 (2018-10-03)¶

Fix bug in Problem.is_weighted that caused problems with defined nodes coords to use the unit distance function

0.3.0 (2018-08-12)¶

Added XRAY1 and XRAY2 implementations
Simplified some of the matrix code

0.2.0 (2018-08-12)¶

Implement column-wise matrices
Add a utiltiy for loading an unknown file
Fix bug in the ATT distance function
Update the CLI to use the models
Document a bunch-o-stuff
Switch to RTD sphinx theme
Move most utilties into utils

0.1.0 (2018-08-12)¶

First release on PyPI.

Welcome to TSPLIB 95’s documentation!¶

TSPLIB 95¶

Features¶

Credits¶

Installation¶

Stable release¶

From sources¶

Usage¶

API Documentation¶

Model classes¶

Matrix weights¶

Distance functions¶

Utilities¶

Exceptions¶

Contributing¶

Types of Contributions¶

Report Bugs¶

Fix Bugs¶

Implement Features¶

Write Documentation¶

Submit Feedback¶

Get Started!¶

Pull Request Guidelines¶

Tips¶

Deploying¶

Credits¶

Development Lead¶

Contributors¶

History¶

0.4.0 (2019-09-21)¶

0.3.3 (2019-03-24)¶

0.3.2 (2018-10-07)¶

0.3.1 (2018-10-03)¶

0.3.0 (2018-08-12)¶

0.2.0 (2018-08-12)¶

0.1.0 (2018-08-12)¶

Indices and tables¶