- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
GraphImporter<V,
E>
This importer reads the nodes of a Symmetric travelling salesman problem instance from a
file and creates a complete graph
and provides further data
from the file and about the imported graph.
This implementation does not cover the full TSPLIB95 standard and only implements the subset of
capabilities required at the time of creation. All keywords of The specification part in
chapter 1.1 of the TSPLIB95 standard are considered. Their values can be obtained from
the corresponding getters of the TSPLIBImporter.Specification
. But only the following
- EUC_2D
- EUC_3D
- MAX_2D
- MAX_3D
- MAN_2D
- MAN_3D
- CEIL2D
- GEO
- ATT
The following data sections of The data part in chapter 1.2 of the TSPLIB95 standard are supported:
- NODE_COORD_SECTION
- TOUR_SECTION
It was attempted to make the structure of this implementation generic so further keywords from the specification part or other data sections can be considered if required by broaden this class. Currently this implementation only reads Symmetric travelling salesman problems with a NODE_COORD_SECTION and on of the supported EDGE_WEIGHT_TYPE.
The website of the TSPLIB standard already contains a large library of different TSP instances provided as files in TSPLIB format. The TSPLIB library of the University of Waterlo provides more problem instances, among others a World TSP and instances based on cities of different countries.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
Container for the meta data of an imported TSPLIB95 file.static class
A node imported from the NODE_COORD_SECTION of a TSPLIB95-file.static class
Container for the entry values read from the specification part of a file in TSPLIB95 format. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final String
private static final String
private static final String
private static final String
private static final String
private static final String
private static final String
private TSPLIBImporter.Metadata
<V, E> private static final String
private static final String
private static final String
(package private) static final double
(package private) static final double
private static final String
private static final String
private int
private static final Pattern
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) int
Computes the distance of the two nodes n1 and n2 according to theCEIL_2D
metric, the round up version ofEUC_2D
.(package private) int
Computes the distance of the two nodes n1 and n2 according to theGEO
metric.(package private) int
Computes the distance of two the two nodes n1 and n2 according to theATT
metric.(package private) int
Computes the distance of the two nodes n1 and n2 according to theEUC_2D
orEUC_3D
metric depending on their dimension.(package private) int
Computes the distance of the two nodes n1 and n2 according to theMAN_2D
orMAN_3D
metric depending on their dimension.(package private) int
Computes the distance of the two nodes n1 and n2 according to theMAX_2D
orMAX_3D
metric depending on their dimension.private static double
computeRadiansAngle
(double x) getEdgeWeightFunction
(String edgeWeightType) private static ImportException
getImportException
(Exception e, String target) private static String
private double
private double
private double
Returns theTSPLIBImporter.Metadata
of the latest imported file or null, if no import completed yet or the latest import failed.getOrderedVertices
(Map<V, TSPLIBImporter.Node> vertex2node) private String
getVertexTour
(List<Integer> tour, Map<V, TSPLIBImporter.Node> vertex2node) void
importGraph
(Graph<V, E> graph, Reader in) Import a graph using the givenReader
.importTour
(TSPLIBImporter.Metadata<V, E> referenceMetadata, Reader in) private Integer
parseInteger
(String valueStr, String valueType) private TSPLIBImporter.Node
private TSPLIBImporter.Metadata
<V, E> private TSPLIBImporter.Metadata
<V, E> readContentForTour
(Iterator<String> lines, Map<V, TSPLIBImporter.Node> vertex2node) private static String
readLine
(BufferedReader reader) private Map
<V, TSPLIBImporter.Node> readNodeCoordinateSection
(Iterator<String> lines, TSPLIBImporter.Metadata<V, E> data) Reads all nodes of the NODE_COORD_SECTION and fills the graph of the data accordingly.private List
<TSPLIBImporter.Node> private boolean
readSpecificationSection
(String key, TSPLIBImporter.Specification spec, String[] lineElements) readTourSection
(Iterator<String> lines, Integer dimension) Reads a tour of the TOUR_SECTION and returns the List of ordered vertex numbers describing the tour.private void
requireNotSet
(Object target, String keyName) private void
requireSet
(Object requirement, String target) private String
requireValidValue
(String value, List<String> validValues, String valueType) Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.jgrapht.nio.GraphImporter
importGraph, importGraph
-
Field Details
-
NAME
- See Also:
-
TYPE
- See Also:
-
COMMENT
- See Also:
-
DIMENSION
- See Also:
-
CAPACITY
- See Also:
-
EDGE_WEIGHT_TYPE
- See Also:
-
EDGE_WEIGHT_FORMAT
- See Also:
-
EDGE_DATA_FORMAT
- See Also:
-
NODE_COORD_TYPE
- See Also:
-
DISPLAY_DATA_TYPE
- See Also:
-
NODE_COORD_SECTION
- See Also:
-
TOUR_SECTION
- See Also:
-
VALID_TYPES
-
VALID_EDGE_WEIGHT_TYPES
-
VALID_EDGE_WEIGHT_FORMATS
-
VALID_EDGE_DATA_FORMATS
-
VALID_NODE_COORD_TYPES
-
VALID_DISPLAY_DATA_TYPE
-
vectorLength
private int vectorLength -
metadata
-
WHITE_SPACE
-
PI
static final double PI- See Also:
-
RRR
static final double RRR- See Also:
-
-
Constructor Details
-
TSPLIBImporter
public TSPLIBImporter()Constructs a new importer.
-
-
Method Details
-
getMetadata
Returns theTSPLIBImporter.Metadata
of the latest imported file or null, if no import completed yet or the latest import failed.- Returns:
TSPLIBFileData
of the latest import
-
importGraph
Import a graph using the givenReader
.It is the callers responsibility to ensure the
Reader
is closed after this method returned.The given
Graph
must be weighted. Also the graph should be empty, otherwise the behavior is unspecified which could lead to exceptions.The source of the given Reader should contain a NODE_COORD_SECTION (if not the graph is not changed) and can contain a TOUR_SECTION. If a TOUR_SECTION is present a corresponding NODE_COORD_SECTION is mandatory and the read vertex numbers are referred to the NODE_COORD_SECTION in the same source.
TSPLIBImporter.Metadata
of the import can be obtained withgetMetadata()
after this method returns. If the readers source contains a TOUR_SECTION the imported tour can be obtained fromTSPLIBImporter.Metadata.getTour()
.This implementation is not thread-safe and must be synchronized externally if called by concurrent threads.
- Specified by:
importGraph
in interfaceGraphImporter<V,
E> - Parameters:
graph
- the graph into which this importer writes, must weighted.in
- the input reader- Throws:
IllegalArgumentException
- if the specifiedgraph
is not weighted
-
readContentForGraph
-
readNodeCoordinateSection
private Map<V,TSPLIBImporter.Node> readNodeCoordinateSection(Iterator<String> lines, TSPLIBImporter.Metadata<V, E> data) Reads all nodes of the NODE_COORD_SECTION and fills the graph of the data accordingly.- Returns:
- a mapping from created graph
vertex
to corresponding importedTSPLIBImporter.Node
-
getEdgeWeightFunction
private ToIntBiFunction<TSPLIBImporter.Node,TSPLIBImporter.Node> getEdgeWeightFunction(String edgeWeightType) -
readNodes
-
parseNode
-
importTour
Imports a tour described by aList
ofvertices
using the given Reader.It is the callers responsibility to ensure the
Reader
is closed after this method returned.The source of the given Reader should contain a TOUR_SECTION (if not null is returned). The vertices specified by their number in the TOUR_SECTION are referred to the nodes respectively vertices in the given
metadata
.The
TSPLIBImporter.Metadata
of the import can be obtained withgetMetadata()
after this method returns. TheMetadata#getVertexToNodeMapping() vertexToNodeMapping
in the metadata of this import is the same as in the givenmetadata
.This implementation is not thread-safe and must be synchronized externally if called by concurrent threads.
- Parameters:
referenceMetadata
- theMetadata
defining the available vertices and theirNodes
.in
- the input reader- Returns:
- the imported tour or null, if no tour was imported
-
readContentForTour
private TSPLIBImporter.Metadata<V,E> readContentForTour(Iterator<String> lines, Map<V, TSPLIBImporter.Node> vertex2node) -
readTourSection
Reads a tour of the TOUR_SECTION and returns the List of ordered vertex numbers describing the tour.- Returns:
- the list of vertex number describing the tour
-
getVertexTour
-
getOrderedVertices
-
readSpecificationSection
private boolean readSpecificationSection(String key, TSPLIBImporter.Specification spec, String[] lineElements) -
requireValidValue
-
parseInteger
-
extractValueBeforeWhitespace
-
getLineIterator
-
readLine
-
getKey
-
getValue
-
requireNotSet
-
requireSet
-
getImportException
-
computeEuclideanDistance
Computes the distance of the two nodes n1 and n2 according to theEUC_2D
orEUC_3D
metric depending on their dimension. The used metric is also known as L2-norm.- Parameters:
n1
- aNode
with two or three dimensional coordinatesn2
- aNode
with two or three dimensional coordinates- Returns:
- the
EUC_2D
orEUC_3D
edge weight for nodes n1 and n2
-
computeMaximumDistance
Computes the distance of the two nodes n1 and n2 according to theMAX_2D
orMAX_3D
metric depending on their dimension. The used metric is also known as L∞-norm.- Parameters:
n1
- aNode
with two or three dimensional coordinatesn2
- aNode
with two or three dimensional coordinates- Returns:
- the
MAX_2D
orMAX_3D
edge weight for nodes n1 and n2
-
computeManhattanDistance
Computes the distance of the two nodes n1 and n2 according to theMAN_2D
orMAN_3D
metric depending on their dimension. The used metric is also known as L1-norm.- Parameters:
n1
- aNode
with two or three dimensional coordinatesn2
- aNode
with two or three dimensional coordinates- Returns:
- the
MAN_2D
orMAN_3D
edge weight for nodes n1 and n2
-
compute2DCeilingEuclideanDistance
Computes the distance of the two nodes n1 and n2 according to theCEIL_2D
metric, the round up version ofEUC_2D
. The points must have dimension two.- Parameters:
n1
- aNode
with two or three dimensional coordinatesn2
- aNode
with two or three dimensional coordinates- Returns:
- the
CEIL_2D
edge weight for nodes n1 and n2 - See Also:
-
compute2DGeographicalDistance
Computes the distance of the two nodes n1 and n2 according to theGEO
metric. The used metric computes the distance between two points on a earth-like sphere, while the point coordinates describe their geographical latitude and longitude. The points must have dimension two.- Parameters:
n1
- aNode
with two or three dimensional coordinatesn2
- aNode
with two or three dimensional coordinates- Returns:
- the
GEO
edge weight for nodes n1 and n2
-
computeRadiansAngle
private static double computeRadiansAngle(double x) -
compute2DPseudoEuclideanDistance
Computes the distance of two the two nodes n1 and n2 according to theATT
metric. The nodes must have two dimensional coordinates.- Parameters:
n1
- aNode
with two dimensional coordinatesn2
- aNode
with two dimensional coordinates- Returns:
- the
ATT
edge weight for nodes n1 and n2
-
getL1Distance
-
getL2Distance
-
getLInfDistance
-