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.
Features¶
- read and write TSPLIB95 file format like a boss
- easily convert problems into
networkx.Graph
instances - supports all fields in the original standard
- allows completely custom field and problem declarations
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 nonetheless.
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
Note
tsplib95 does not officially ship with any problem files itself. The problems and solutions are standalone files. 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.
Loading problems¶
Problems can be loaded from files, read from file pointers, or parsed from strings.
tsplib95.load()
: loads from a filepathtsplib95.parse()
: parses directly from a stringtsplib95.read()
: reads from a file-like object
From a filepath¶
For the simple case of a file on disk, pass the filepath to
tsplib95.load()
:
>>> import tsplib95
>>> problem = tsplib95.load('archives/problems/tsp/bay29.tsp')
From a string¶
For cases where the problem isn’t stored as a file on disk, just pass the text
directly to tsplib95.parse()
:
>>> import tsplib95
>>> with open('archives/problems/tsp/gr17.tsp') as f:
... text = f.read()
...
>>> problem = tsplib95.parse(text)
From a file-like object¶
If you already have an open file-like object, just pass it to tsplib95.read()
:
>>> import tsplib95
>>> with open('archives/problems/tsp/gr17.tsp') as f:
... problem = tsplib95.read(f)
...
SPECIAL functions¶
What’s a SPECIAL function?¶
Some problems involve using a custom function for calcating edge weights. Such custom weight functions are called “special” functions because their details are not defined by TSPLIB95 standard.
Problems that use a special function have the following characteristics:
- EDGE_WEIGHT_FORMAT is “FUNCTION”
- EDGE_WEIGHT_TYPE is “SPECIAL”
In tsplib95, a special function must accept two node coordinates and return the weight, distance, or cost of the edge between them:
from typing import Union, Sequence
def special(start: Sequence, end: Sequence) -> Union[float,int]:
pass
How to use¶
All loaders (load()
, read()
, and
parse()
) accept a custom weight function via the keyword
parameter special.
>>> import tsplib95
>>> from myapp import get_distance
>>> problem = tsplib95.load('assets/tsp/routes-150.tsp',
... special=get_distance)
Special functions can also be set on an existing problem instance:
>>> import tsplib95
>>> from myapp import get_distance
>>> problem = tsplib95.load('assets/tsp/routes-150.tsp')
>>> problem.special = get_distance
Note that setting the special function on a problem that has explicit edge weights has no effect.
An example¶
Let’s assume our app has a helper function capable of using the Google Maps API to fetch the driving distance between two geocoordinates. We can use that to create a special function and use it as the distance function in a TSPLIB95 problem.
Let’s also assume our hypothetical helper function accepts a list of waypoints as dictionaries with “lat” and “lng” keys, but our problem specifies geocoordinates as a simple tuple of latitude and longitude values.
Our special function will need to convert the tuples into the expected dictionaries and use the helper to calculate the driving distance.
>>> from myapp import helpers
>>> def waypoint(coordinates):
... return {'lat': coordinates[0], 'lng': coordinates[1]}
>>> def driving_distance(start, end):
... """Special distance function for driving distance."""
... waypoints = [waypoint(start), waypoint(end)]
... kilometers = helpers.total_distance(waypoints, method='driving')
... return kilometers
...
Now we can simply supply the
tsplib95.load
method with our special
function:
>>> import tsplib95
>>> problem = tsplib95.load('my-hometown.tsp', special=driving_distance)
As with any problem, we can find the weight of any edge using the
get_weight()
method. See the
Distances section for more details.
Note
The example above demonstrates the flexibility of the special function, but depending on the specific implementation details of the helper function, it could be too fragile.
There is no exception handling around the use of the special function so it is advisable to handle any exceptions. Depending on the use case, it may also be wise to limit calls to it by wrapping it in a debounce function or backing it with a cache.
Saving problems¶
The Problem
class also two convenience methods for output to files:
Problem.save
: saves to a filepathProblem.write
: writes to a file-like object
>>> problem.save('path/to/file.name')
>>> with open('path/to/other.name', 'w') as f:
... problem.write(f)
...
Rendering problems¶
Problems can be rendered back into text using the
Problem.render
method:
>>> print(problem.render())
NAME: gr17
COMMENT: 17-city problem (Groetschel)
TYPE: TSP
DIMENSION: 17
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW
EDGE_WEIGHT_SECTION:
0 633 0 257 390 0 91 661 228 0 412 227
169 383 0 150 488 112 120 267 0 80 572 196
77 351 63 0 134 530 154 105 309 34 29 0
259 555 372 175 338 264 232 249 0 505 289 262
476 196 360 444 402 495 0 353 282 110 324 61
208 292 250 352 154 0 324 638 437 240 421 329
297 314 95 578 435 0 70 567 191 27 346 83
47 68 189 439 287 254 0 211 466 74 182 243
105 150 108 326 336 184 391 145 0 268 420 53
239 199 123 207 165 383 240 140 448 202 57 0
246 745 472 237 528 364 332 349 202 685 542 157
289 426 483 0 121 518 142 84 297 35 29 36
236 390 238 301 55 96 153 336 0
EOF
Note this is equivalent to casting the problem to a string:
>>> assert str(problem) == problem.render()
Working with problems¶
Note
In general, familiarity with the original file format standard will translate well. Please refer to it for an better understanding of the underlying TSPLIB95 file format.
Accessing Values¶
In general, the name of a field is its keyword converted to lowercase. For example,
“NAME” is name
and “EDGE_WEIGHT_FORMAT” is edge_weight_format
, etc.:
>>> problem.name # NAME
'gr17'
>>> problem.edge_weight_format # EDGE_WEIGHT_FORMAT
'LOWER_DIAG_ROW'
However, field names do not have the “_SECTION” suffix of some keywords:
>>> problem.edge_weights # not EDGE_WEIGHT_SECTION
[[0, 633, 0, 257, 390, 0, 91, 661, 228, 0, 412, 227],
[169, 383, 0, 150, 488, 112, 120, 267, 0, 80, 572, 196],
[77, 351, 63, 0, 134, 530, 154, 105, 309, 34, 29, 0],
[259, 555, 372, 175, 338, 264, 232, 249, 0, 505, 289, 262],
[476, 196, 360, 444, 402, 495, 0, 353, 282, 110, 324, 61],
[208, 292, 250, 352, 154, 0, 324, 638, 437, 240, 421, 329],
[297, 314, 95, 578, 435, 0, 70, 567, 191, 27, 346, 83],
[47, 68, 189, 439, 287, 254, 0, 211, 466, 74, 182, 243],
[105, 150, 108, 326, 336, 184, 391, 145, 0, 268, 420, 53],
[239, 199, 123, 207, 165, 383, 240, 140, 448, 202, 57, 0],
[246, 745, 472, 237, 528, 364, 332, 349, 202, 685, 542, 157],
[289, 426, 483, 0, 121, 518, 142, 84, 297, 35, 29, 36],
[236, 390, 238, 301, 55, 96, 153, 336, 0]]
All values are available mapped either by keyword or name:
>>> problem.as_name_dict()
{'name': 'gr17',
'comment': '17-city problem (Groetschel)',
'type': 'TSP',
'dimension': 17,
'capacity': 0,
'node_coord_type': None,
'edge_weight_type': 'EXPLICIT',
'display_data_type': None,
'edge_weight_format': 'LOWER_DIAG_ROW',
'edge_data_format': None,
'node_coords': {},
'edge_data': {},
'edge_weights': [[0, 633, 0, 257, 390, 0, 91, 661, 228, 0, 412, 227],
[169, 383, 0, 150, 488, 112, 120, 267, 0, 80, 572, 196],
[77, 351, 63, 0, 134, 530, 154, 105, 309, 34, 29, 0],
[259, 555, 372, 175, 338, 264, 232, 249, 0, 505, 289, 262],
[476, 196, 360, 444, 402, 495, 0, 353, 282, 110, 324, 61],
[208, 292, 250, 352, 154, 0, 324, 638, 437, 240, 421, 329],
[297, 314, 95, 578, 435, 0, 70, 567, 191, 27, 346, 83],
[47, 68, 189, 439, 287, 254, 0, 211, 466, 74, 182, 243],
[105, 150, 108, 326, 336, 184, 391, 145, 0, 268, 420, 53],
[239, 199, 123, 207, 165, 383, 240, 140, 448, 202, 57, 0],
[246, 745, 472, 237, 528, 364, 332, 349, 202, 685, 542, 157],
[289, 426, 483, 0, 121, 518, 142, 84, 297, 35, 29, 36],
[236, 390, 238, 301, 55, 96, 153, 336, 0]],
'display_data': {},
'fixed_edges': [],
'depots': [],
'demands': {},
'tours': []}
>>> problem.as_keyword_dict()
{'NAME': 'gr17',
'COMMENT': '17-city problem (Groetschel)',
'TYPE': 'TSP',
'DIMENSION': 17,
'CAPACITY': 0,
'NODE_COORD_TYPE': None,
'EDGE_WEIGHT_TYPE': 'EXPLICIT',
'DISPLAY_DATA_TYPE': None,
'EDGE_WEIGHT_FORMAT': 'LOWER_DIAG_ROW',
'EDGE_DATA_FORMAT': None,
'NODE_COORD_SECTION': {},
'EDGE_DATA_SECTION': {},
'EDGE_WEIGHT_SECTION': [[0, 633, 0, 257, 390, 0, 91, 661, 228, 0, 412, 227],
[169, 383, 0, 150, 488, 112, 120, 267, 0, 80, 572, 196],
[77, 351, 63, 0, 134, 530, 154, 105, 309, 34, 29, 0],
[259, 555, 372, 175, 338, 264, 232, 249, 0, 505, 289, 262],
[476, 196, 360, 444, 402, 495, 0, 353, 282, 110, 324, 61],
[208, 292, 250, 352, 154, 0, 324, 638, 437, 240, 421, 329],
[297, 314, 95, 578, 435, 0, 70, 567, 191, 27, 346, 83],
[47, 68, 189, 439, 287, 254, 0, 211, 466, 74, 182, 243],
[105, 150, 108, 326, 336, 184, 391, 145, 0, 268, 420, 53],
[239, 199, 123, 207, 165, 383, 240, 140, 448, 202, 57, 0],
[246, 745, 472, 237, 528, 364, 332, 349, 202, 685, 542, 157],
[289, 426, 483, 0, 121, 518, 142, 84, 297, 35, 29, 36],
[236, 390, 238, 301, 55, 96, 153, 336, 0]],
'DISPLAY_DATA_SECTION': {},
'FIXED_EDGES_SECTION': [],
'DEPOT_SECTION': [],
'DEMAND_SECTION': {},
'TOUR_SECTION': []}
Nodes and edges¶
To help users avoid the complexity in listing the nodes and edges reliably in all
cases, there exists the get_nodes()
and
get_edges()
methods.
>>> list(problem.get_nodes())
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
>>> len(list(problem.get_edges())) # I'll spare you the full listing :P
289
>>> list(problem.get_edges())[0]
(0, 0)
Distances¶
Regardless of whether the problem is explicit or function, the distance between
two nodes can always be found by passing their indicies to
get_weight()
.
>>> problem = tsplib95.load('archives/problems/vrp/eil22.vrp')
>>> list(problem.get_nodes())
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
>>> problem.node_coords[3]
[159, 261]
>>> problem.node_coords[8]
[161, 242]
>>> problem.edge_weight_type
'EUC_2D'
>>> edge = 3, 8
>>> weight = problem.get_weight(*edge)
>>> print(f'The driving distance from node {edge[0]} to node {edge[1]} is {weight}.')
The distance between node 3 and node 8 is 19.
tsplib95
has built-in support for all function types, including special functions.
See SPECIAL functions for more information.
Boolean methods¶
Problems contain a set of functions that report “emergent” boolean information about the problem given its data.
Extra attributes¶
There can be no extra or unknown keywords in a problem. Typically, this results in a failure to parse the field preceding it, but not necessarily (for example, if the presence of the keyword in the value of the preceding field is valid then there will be no error).
However, not all fields defined on a Problem
must be present in a problem.
In such a case, requesting the value on the problem instance returns the default
value for the field. Fields are not rendered or written to file unless their value
has been set.
Tracing tours¶
Some TSPLIB95 files have a TOURS field that lists one or more tours. Often, the
tour(s) are in a separate .opt.tour
file.
StandardProblem
has a TOURS field, which means it can
parse these .opt.tour
files as well:
>>> opt = tsplib95.load('archives/solutions/tour/gr666.opt.tour')
>>> opt.type
'TOUR'
>>> len(opt.tours)
1
>>> len(opt.tours[0])
666
We have 1 tour to trace. We can simply pass the list of tours to
trace_tours()
:
>>> problem = tsplib95.load('archives/problems/tsp/gr666.tsp')
>>> >>> problem.trace_tours(opt.tours)
[294358]
Note
Note that it returned a list of tour weights, one for each tour given.
For testing purposes, there is also
trace_canonical_tour()
, which uses the
nodes in definition order as a tour and returns the total weight:
>>> weight = problem.trace_canonical_tour()
Converting problems¶
get_graph()
creates a networkx.Graph
instance from the problem data:
>>> G = problem.get_graph()
>>> G.nodes
NodeView((1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16))
The graph, nodes, and edges of the object contain as much accessory information as is present in the problem instance:
>>> G.graph
{'name': 'gr17',
'comment': '17-city problem (Groetschel)',
'type': 'TSP',
'dimension': 17,
'capacity': 0}
>>> G.nodes[0]
{'coord': None, 'display': None, 'demand': None, 'is_depot': False}
>>> G.edges[0, 1]
{'weight': 633, 'is_fixed': False}
API Documentation¶
Loaders¶
The loaders are responsible for loading from a filepath, reading a file-like object, or parsing a string.
-
tsplib95.loaders.
load
(filepath, problem_class=None, special=None)[source]¶ Load a problem at the given filepath.
Parameters: - filepath (str) – path to a TSPLIB problem file
- problem_class (type) – special/custom problem class
- special (callable) – special/custom distance function
Returns: problem instance
Return type: Problem
-
tsplib95.loaders.
load_problem
(filepath, special=None)[source]¶ Load a problem at the given filepath.
param str filepath: path to a TSPLIB problem file param callable special: special/custom distance function return: problem instance rtype: Problem
Deprecated since version 7.0.0: Will be removed in newer versions. Use tsplib95.load instead.
-
tsplib95.loaders.
load_problem_fromstring
(text, special=None)[source]¶ Load a problem from raw text.
param str text: text of a TSPLIB problem param callable special: special/custom distance function return: problem instance rtype: Problem
Deprecated since version 7.0.0: Will be removed in newer versions. Use tsplib95.parse instead.
-
tsplib95.loaders.
load_solution
(filepath)[source]¶ Load a solution at the given filepath.
param str filepath: path to a TSPLIB solution file return: solution instance rtype: Solution
Deprecated since version 7.0.0: Will be removed in newer versions. Use tsplib95.load instead.
-
tsplib95.loaders.
load_solution_fromstring
(text)[source]¶ Load a solution from raw text.
param str text: text of a TSPLIB solution return: solution instance rtype: Solution
Deprecated since version 7.0.0: Will be removed in newer versions. Use tsplib95.parse instead.
-
tsplib95.loaders.
load_unknown
(filepath)[source]¶ Load any TSPLIB file.
This is particularly useful when you do not know in advance whether the file contains a problem or a solution.
param str filepath: path to a TSPLIB problem file return: either a problem or solution instance Deprecated since version 7.0.0: Will be removed in newer versions. Use tsplib95.load instead.
-
tsplib95.loaders.
load_unknown_fromstring
(text)[source]¶ Load any problem/solution from raw text.
This is particularly useful when you do not know in advance whether the file contains a problem or a solution.
param str text: text of a TSPLIB problem/solution return: either a problem or solution instance Deprecated since version 7.0.0: Will be removed in newer versions. Use tsplib95.parse instead.
-
tsplib95.loaders.
parse
(text, problem_class=None, special=None)[source]¶ Load a problem from raw text.
Parameters: - text (str) – text of a TSPLIB problem
- problem_class (type) – special/custom problem class
- special (callable) – special/custom distance function
Returns: problem instance
Return type: Problem
Problems¶
Problem classes define what fields can be present and how they are converted to and from text.
-
class
tsplib95.models.
Problem
(**data)[source]¶ Bases:
object
Base class for all problems.
Parameters: data – name-value data -
as_dict
(by_keyword=False)[source]¶ Return the problem data as a dictionary.
Parameters: by_keyword (bool) – use keywords (True) or names (False) or keys Returns: problem data Return type: dict
-
as_keyword_dict
()[source]¶ Return the problem data as a dictionary by field keyword.
Returns: problem data Return type: dict
-
as_name_dict
()[source]¶ Return the problem data as a dictionary by field name.
Returns: problem data Return type: dict
-
classmethod
load
(filepath, **options)[source]¶ Load a problem instance from a text file.
Any keyword options are passed to the class constructor. If a keyword argument has the same name as a field then they will collide and cause an error.
Parameters: - filepath (str) – path to a problem file
- options – any keyword arguments to pass to the constructor
Returns: problem instance
Return type:
-
classmethod
parse
(text, **options)[source]¶ Parse text into a problem instance.
Any keyword options are passed to the class constructor. If a keyword argument has the same name as a field then they will collide and cause an error.
Parameters: - text (str) – problem text
- options – any keyword arguments to pass to the constructor
Returns: problem instance
Return type:
-
classmethod
read
(fp, **options)[source]¶ Read a problem instance from a file-like object.
Any keyword options are passed to the class constructor. If a keyword argument has the same name as a field then they will collide and cause an error.
Parameters: - fp (str) – a file-like object
- options – any keyword arguments to pass to the constructor
Returns: problem instance
Return type:
-
-
class
tsplib95.models.
StandardProblem
(special=None, **data)[source]¶ Bases:
tsplib95.models.Problem
Standard problem as outlined in the original TSLIB95 documentation.
The available fields and their keywords are:
name
- NAMEcomment
- COMMENTtype
- TYPEdimension
- DIMENSIONcapacity
- CAPACITYedge_weight_type
- EDGE_WEIGHT_TYPEedge_weight_format
- EDGE_WEIGHT_FORMATedge_data_format
- EDGE_DATA_FORMATnode_coord_type
- NODE_COORD_TYPEdisplay_data_type
- DISPLAY_DATA_TYPEdepots
- DEPOT_SECTIONdemands
- DEMAND_SECTIONnode_coords
- NODE_COORD_SECTIONedge_weights
- EDGE_WEIGHT_SECTIONdisplay_data
- DISPLAY_DATA_SECTIONedge_data
- EDGE_DATA_SECTIONfixed_edges
- FIXED_EDGES_SECTIONtours
- TOUR_SECTION
For SPECIAL FUNCTION problems, the special function must accept a start and an end node and return the weight, distance, or cost of the edge that joins them. It can be provided at construction time or simply set on an existing object using the
special
attribute.Parameters: - special (callable) – special function for distance
- data – name-value data
-
get_display
(i)[source]¶ Return the display data for node at index i.
If the problem is not depictable, None is returned instead.
Parameters: i (int) – node index Returns: display data for node i
-
get_edges
()[source]¶ Return an iterator over the edges.
This method provides a single way to obtain the edges of a problem regardless of how it is specified. If the EDGE_DATA_FORMAT is not set and the nodes are undefined, then the edges are also undefined.
Returns: edges Return type: iter Raises: ValueError – if the nodes and therefore the edges are undefined
-
get_graph
(normalize=False)[source]¶ Return a networkx graph instance representing the problem.
The metadata of the problem is associated with the graph itself. Additional problem information is associated with the nodes and edges. For example:
>>> G = problem.get_graph() >>> G.graph {'name': None, 'comment': '14-Staedte in Burma (Zaw Win)', 'type': 'TSP', 'dimension': 14, 'capacity': None} >>> G.nodes[1] {'coord': (16.47, 96.1), 'display': None, 'demand': None, 'is_depot': False} >>> G.edges[1, 2] {'weight': 2, 'is_fixed': False}
If the graph is asymmetric then a
networkx.DiGraph
is returned. Optionally, the nodes can be renamed to be sequential and zero-indexed.Parameters: normalize (bool) – rename nodes to be zero-indexed Returns: graph Return type: networkx.Graph
-
get_nodes
()[source]¶ Return an iterator over the nodes.
This method provides a single way to obtain the nodes of a problem regardless of how it is specified. However, if the nodes are not specified, the EDGE_DATA_FORMAT is not set, and DIMENSION has no value, then nodes are undefined.
Returns: nodes Return type: iter Raises: ValueError – if the nodes are undefined
-
get_weight
(start, end)[source]¶ Return the weight of the edge between start and end.
This method provides a single way to obtain edge weights regardless of whether the problem uses an explicit matrix or a distance function.
Parameters: - start (int) – starting node index
- end (int) – ending node index
Returns: weight of the edge between start and end
Return type: float
-
is_complete
()[source]¶ Check whether the problem specifies a complete graph.
Returns: True if the problem specifies a complete graph Return type: bool
-
is_depictable
()[source]¶ Check whether the problem can be depicted.
A problem is depictable if it has display data or has node coordinates and does not specify NO_DISPLAY.
Returns: True if the problem can be depicted Return type: bool
-
is_explicit
()[source]¶ Check whether the problem specifies edge weights explicitly.
Returns: True if the problem specifies edge weights explicitly Return type: bool
-
is_full_matrix
()[source]¶ Check whether the problem is specified as a full matrix.
Returns: True if the problem is specified as a full matrix Return type: bool
-
is_special
()[source]¶ Check whether the problem is special.
SPECIAL problems require a special distance function.
Returns: True if the problem requires a special distance function Return type: bool
-
is_symmetric
()[source]¶ Check whether the problem is symmetrical.
Warning
Although a result of
True
guarantees symmetry, a value ofFalse
merely indicates the possibliity for asymmetry. Avoid usingnot problem.is_symmetric()
when possible.Returns: True if the problem is symmetrical Return type: bool
-
is_weighted
()[source]¶ Check whether the problem has weighted edges.
A problem is considered unweighted if neither the EDGE_WEIGHT_FORMAT nor the EDGE_WEIGHT_TYPE are defined.
Returns: True if the problem is weighted Return type: bool
-
special
¶ Special distance function.
Special/custom distance functions must accept two coordinates of appropriate dimension and return the distance between them.
-
trace_canonical_tour
()[source]¶ Return the weight of the canonical tour.
The “canonical tour” uses the nodes in order. This method is present primarily for testing and purposes.
Returns: weight of the canonical tour Return type: float
-
trace_tours
(tours)[source]¶ Return the weights of the given tours.
Each tour is a list of node indices. The weights returned are the sum of the individual weights of the edges in each tour including the final edge back to the starting node.
The list of weights returned parallels the list of tours given so that
weights[i]
corresponds totours[i]
:weights = p.trace_tours(tours)
Parameters: tours (list) – one or more lists of node indices Returns: one weight for each given tour Return type: list
Fields¶
-
class
tsplib95.fields.
Field
(keyword, *, default=None)[source]¶ Bases:
object
Contains base functionality for all fields.
The default value can be a callable, in which case it is invoked for each call to
get_default_value()
. The default can be set on an instance or as a class attribute, but the class attribute is only checked when the field is initially created.Parameters: - keyword (str) – keyword (typically all caps)
- default – a default value or callable that will return a default
-
get_default_value
()[source]¶ Return the default value.
Callables are called for a default value to return each time.
Returns: the default value Return type: Any
-
parse
(text)[source]¶ Convert text into a value.
This must be implemented in a subclass.
Parameters: text (str) – Returns: a value
-
class
tsplib95.fields.
TransformerField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.Field
Field that delegates to a
Transformer
.Parameters: - keyword (str) – keyword
- transformer (callable) – transformer to use
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
parse
(text)[source]¶ Parse the text into a value using the transformer.
Parameters: text (str) – text to parse Returns: value
-
class
tsplib95.fields.
StringField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Simple string field.
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
classmethod
-
class
tsplib95.fields.
IntegerField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Simple integer field.
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
classmethod
-
class
tsplib95.fields.
FloatField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Simple float field.
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
classmethod
-
class
tsplib95.fields.
NumberField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Number field, supporting ints and floats.
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
classmethod
-
class
tsplib95.fields.
IndexedCoordinatesField
(*args, dimensions=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Field for coordinates by index.
When given,
dimensions
stipulates the possible valid dimensionalities for the coordinates. For exapmle,dimensions=(2, 3)
indicates the coordinates are either all 2d or all 3d, whereasdimensions=2
indicates all coordinates must be 2d. The check is only enforced during validation.Parameters: dimensions – one or more valid dimensionalities -
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
default
¶ alias of
builtins.dict
-
classmethod
-
class
tsplib95.fields.
AdjacencyListField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Field for an adjancency list.
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
default
¶ alias of
builtins.dict
-
classmethod
-
class
tsplib95.fields.
EdgeListField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Field for a list of edges.
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
default
¶ alias of
builtins.list
-
classmethod
-
class
tsplib95.fields.
MatrixField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Field for a matrix of numbers.
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
default
¶ alias of
builtins.list
-
classmethod
-
class
tsplib95.fields.
EdgeDataField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Field for edge data.
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
default
¶ alias of
builtins.dict
-
classmethod
-
class
tsplib95.fields.
DepotsField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Field for depots.
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
default
¶ alias of
builtins.list
-
classmethod
-
class
tsplib95.fields.
DemandsField
(keyword, *, transformer=None, **kwargs)[source]¶ Bases:
tsplib95.fields.TransformerField
Field for demands.
-
classmethod
build_transformer
()[source]¶ Construct an appropriate transformer for the field.
Returns: transformer Return type: Transformer
-
default
¶ alias of
builtins.dict
-
classmethod
Transformers¶
-
class
tsplib95.transformers.
Transformer
[source]¶ Bases:
object
Reusable transformer between text and data.
-
parse
(text)[source]¶ Return the value of the text.
Parameters: text (str) – the text Returns: the value Raises: ParsingError – if the text cannot be parsed into a value
-
-
class
tsplib95.transformers.
FuncT
(*, func)[source]¶ Bases:
tsplib95.transformers.Transformer
Transformer that simply wraps a parsing function.
The parsing function must accept a single positional argument for the text to parse. It must parse and return the value.
Values are rendered back into values using the builtin
str()
, so it’s generally best to use this for primitives.Parameters: func (callable) – parsing function -
parse
(text)[source]¶ Return the value of the text.
Parameters: text (str) – the text Returns: the value Raises: ParsingError – if the text cannot be parsed into a value
-
-
class
tsplib95.transformers.
NumberT
[source]¶ Bases:
tsplib95.transformers.Transformer
Transformer for any number, int or float.
-
parse
(text)[source]¶ Return the value of the text.
Parameters: text (str) – the text Returns: the value Raises: ParsingError – if the text cannot be parsed into a value
-
-
class
tsplib95.transformers.
ContainerT
(*, value=None, sep=None, terminal=None, terminal_required=True, size=None, filter_empty=True)[source]¶ Bases:
tsplib95.transformers.Transformer
Transformer that acts as a generic container.
Parameters: - value (
Transformer
) – transformer for each item - sep (str) – separator between items
- terminal (str) – text that marks the end
- terminal_required (bool) – whether the terminal is required
- size (int) – required number of items
- filter_empty (bool) – filter out empty items (zero-length/blank)
-
join_items
(items)[source]¶ Join zero or more items into a single text.
Parameters: items (list) – items to join Returns: joined text Return type: str
-
pack
(items)[source]¶ Pack the given items into a container.
Parameters: items (list) – items to pack Returns: container with items in it
-
parse
(text)[source]¶ Parse the text into a container of items.
Parameters: text (str) – the text to parse Returns: container
-
parse_item
(text)[source]¶ Parse the text into a single item.
Parameters: text (str) – the text to parse Returns: container
-
render
(container)[source]¶ Render the container into text.
Parameters: container – container to render Returns: text
- value (
-
class
tsplib95.transformers.
ListT
(*, value=None, sep=None, terminal=None, terminal_required=True, size=None, filter_empty=True)[source]¶ Bases:
tsplib95.transformers.ContainerT
Transformer for a list of items.
-
class
tsplib95.transformers.
MapT
(*, kv_sep=None, key=None, **kwargs)[source]¶ Bases:
tsplib95.transformers.ContainerT
Transformer for a key-value mapping of items.
Parameters: - kv_sep (str) – separator between keys and values
- key (
Transformer
) – transformer for the keys
-
pack
(items)[source]¶ Pack the given items into a container.
Parameters: items (list) – items to pack Returns: container with items in it
-
parse_item
(text)[source]¶ Parse the text into a single item.
Parameters: text (str) – the text to parse Returns: container
-
parse_key
(text)[source]¶ Parse the text into a key.
Parameters: text (str) – the text to parse Returns: key
-
parse_value
(text)[source]¶ Parse the text into a value.
Parameters: text (str) – the text to parse Returns: value
-
render_key
(key)[source]¶ Render the key into text.
Parameters: key – the key to render Returns: text Return type: str
-
class
tsplib95.transformers.
UnionT
(*tfs, **kwargs)[source]¶ Bases:
tsplib95.transformers.Transformer
-
parse
(text)[source]¶ Return the value of the text.
Parameters: text (str) – the text Returns: the value Raises: ParsingError – if the text cannot be parsed into a value
-
Matrices¶
-
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
-
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
-
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
-
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
-
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
-
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
-
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
Distances¶
-
tsplib95.distances.
TYPES
= {'ATT': <function pseudo_euclidean>, 'CEIL_2D': functools.partial(<function euclidean>, round=<built-in function ceil>), 'EUC_2D': <function euclidean>, 'EUC_3D': <function euclidean>, 'GEO': <function geographical>, 'MAN_2D': <function manhattan>, 'MAN_3D': <function manhattan>, 'MAX_2D': <function maximum>, 'MAX_3D': <function maximum>, 'XRAY1': <function xray>, 'XRAY2': functools.partial(<function xray>, sx=1.25, sy=1.5, sz=1.15)}¶ Map of distance function types to distance functions
-
tsplib95.distances.
euclidean
(start, end, round=<function nint>)[source]¶ Return the Euclidean distance between start and end.
This is capable of performing distance calculations for EUC_2D and EUC_3D problems. If
round=math.ceil
is passed, this is suitable for CEIL_2D problems as well.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.
manhattan
(start, end, round=<function nint>)[source]¶ Return the Manhattan distance between start and end.
This is capable of performing distance calculations for MAN_2D and MAN_3D problems.
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.
This is capable of performing distance calculations for MAX_2D and MAX_3D problems.
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.
This is capable of performing distance calculations for GEO problems.
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.
pseudo_euclidean
(start, end, round=<function nint>)[source]¶ Return the pseudo-Euclidean distance between start and end.
This is capable of performing distance calculations for ATT problems.
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.0, sy=1.0, sz=1.0, round=<function nint>)[source]¶ Return x-ray crystallography distance.
This is capable of performing distance calculations for xray crystallography problems. As is, it is suitable for XRAY1 problems. However, using
sx=1.25
,sy=1.5
, andsz=1.15
makes it suitable for XRAY2 problems.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
Biseps¶
Utilities¶
Exceptions¶
-
exception
tsplib95.exceptions.
TsplibError
[source]¶ Bases:
Exception
Base exception for all tsplib95 errors.
-
exception
tsplib95.exceptions.
ParsingError
[source]¶ Bases:
tsplib95.exceptions.TsplibError
,ValueError
Exception raised when a value cannot be parsed from the text.
-
exception
tsplib95.exceptions.
RenderingError
[source]¶ Bases:
tsplib95.exceptions.TsplibError
,ValueError
Exception raised when a value cannot be rendered into text.
-
exception
tsplib95.exceptions.
ValidationError
[source]¶ Bases:
tsplib95.exceptions.TsplibError
Exception raised when a problem fails validation.
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.
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.7.1 (2020-05-08)¶
- Bugfix for
StandardProblem.get_nodes
ignoring node indices specified in demands
0.7.0 (2020-04-18)¶
- Refactored the models to unify the
Problem
andSolution
classes into the newStandardProblem
class. - 93% test coverage, including distance functions, parsing functions, and rendering functions.
- You can finally write problems in TSPLIB95 format! Render to text, write to file, or save to filepath.
- Parsing text, reading files, and loading filepaths are all now supported.
- Deprecated the old loading utils.
- Custom problems now supported by allowing you to define your own fields.
- Library exceptions for parsing and rendering.
- Numerous bugfixes for the distance functions (ATT, XRAY*, GEO).
- Improved the CLI to use a pager and proper column tabulation.
- Made some progress modernizing the FORTRAN code for xray problems.
- Added codecoverage metrics and badge.
0.6.1 (2020-01-04)¶
- Fix bug that caused the parser to ignore the first line of a file
0.6.0 (2019-10-19)¶
Changes to the conversion into a
networkx.Graph
:- Depot, demand, and fixed edge data have been removed from graph metadata. Depot and demand data is now associated with individual nodes like fixed edge data was (and still is).
- Add a
normalized
parameter to allow nodes to be renamed as zero-index integers when obtaining anetworkx.Graph
.
Depots, demands, node coordinates, and display data fields now default to empty containers rather than
None
.Fixed twine/PyPI warning about long description mime type
0.5.0 (2019-10-02)¶
- New loaders that take just the text - no file necessary!
- Invalid keywords now result in a
ParsingError
- Update the CLI to catch and gracefully handle
ParsingError
- Fixed a bug when trying to amend an exception with line information
0.4.0 (2019-09-21)¶
- All expected parsing errors are now raised as
ParsingError
rather than the baseException
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 aTypeError
when run - Fix bug in
Problem.is_depictable
that produced aTypeError
when run - Fix bug in
Problem.get_display
that produced anAttributeError
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.