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.