Module org.jgrapht.io
Package org.jgrapht.nio.tsplib

Class TSPLIBImporter<V,E>

java.lang.Object
org.jgrapht.nio.tsplib.TSPLIBImporter<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
GraphImporter<V,E>
public class TSPLIBImporter<V,E> extends Object implements GraphImporter<V,E>
Importer for files in the TSPLIB95 format.

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

  • EDGE_WEIGHT_TYPE
    • values are supported for a NODE_DATA_SECTION:
    • 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.

    • Field Details

    • Constructor Details

      • TSPLIBImporter

        public TSPLIBImporter()
        Constructs a new importer.

    • Method Details

      • getMetadata

        public TSPLIBImporter.Metadata<V,E> getMetadata()
        Returns the TSPLIBImporter.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

        public void importGraph(Graph<V,E> graph, Reader in)
        Import a graph using the given Reader.

        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 with getMetadata() after this method returns. If the readers source contains a TOUR_SECTION the imported tour can be obtained from TSPLIBImporter.Metadata.getTour().

        This implementation is not thread-safe and must be synchronized externally if called by concurrent threads.

        Specified by:
        importGraph in interface GraphImporter<V,E>
        Parameters:
        graph - the graph into which this importer writes, must weighted.
        in - the input reader
        Throws:
        IllegalArgumentException - if the specified graph is not weighted

      • readContentForGraph

        private TSPLIBImporter.Metadata<V,E> readContentForGraph(Iterator<String> lines, Graph<V,E> graph)

      • 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 imported TSPLIBImporter.Node

      • getEdgeWeightFunction

        private ToIntBiFunction<TSPLIBImporter.Node,TSPLIBImporter.Node> getEdgeWeightFunction(String edgeWeightType)

      • readNodes

        private List<TSPLIBImporter.Node> readNodes(Iterator<String> lines, int dimension)

      • parseNode

        private TSPLIBImporter.Node parseNode(String line)

      • importTour

        public List<V> importTour(TSPLIBImporter.Metadata<V,E> referenceMetadata, Reader in)
        Imports a tour described by a List of vertices 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 with getMetadata() after this method returns. The Metadata#getVertexToNodeMapping() vertexToNodeMapping in the metadata of this import is the same as in the given metadata.

        This implementation is not thread-safe and must be synchronized externally if called by concurrent threads.

        Parameters:
        referenceMetadata - the Metadata defining the available vertices and their Nodes.
        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

        private List<Integer> readTourSection(Iterator<String> lines, Integer dimension)
        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

        private List<V> getVertexTour(List<Integer> tour, Map<V,TSPLIBImporter.Node> vertex2node)

      • getOrderedVertices

        private List<V> getOrderedVertices(Map<V,TSPLIBImporter.Node> vertex2node)

      • readSpecificationSection

        private boolean readSpecificationSection(String key, TSPLIBImporter.Specification spec, String[] lineElements)

      • requireValidValue

        private String requireValidValue(String value, List<String> validValues, String valueType)

      • parseInteger

        private Integer parseInteger(String valueStr, String valueType)

      • extractValueBeforeWhitespace

        public String extractValueBeforeWhitespace(String value)

      • getLineIterator

        private static Iterator<String> getLineIterator(Reader in)

      • readLine

        private static String readLine(BufferedReader reader)

      • getKey

        private static String getKey(String[] keyValue)

      • getValue

        private String getValue(String[] keyValue)

      • requireNotSet

        private void requireNotSet(Object target, String keyName)

      • requireSet

        private void requireSet(Object requirement, String target)

      • getImportException

        private static ImportException getImportException(Exception e, String target)

      • computeEuclideanDistance

        int computeEuclideanDistance(TSPLIBImporter.Node n1, TSPLIBImporter.Node n2)
        Computes the distance of the two nodes n1 and n2 according to the EUC_2D or EUC_3D metric depending on their dimension. The used metric is also known as L2-norm.
        Parameters:
        n1 - a Node with two or three dimensional coordinates
        n2 - a Node with two or three dimensional coordinates
        Returns:
        the EUC_2D or EUC_3D edge weight for nodes n1 and n2

      • computeMaximumDistance

        int computeMaximumDistance(TSPLIBImporter.Node n1, TSPLIBImporter.Node n2)
        Computes the distance of the two nodes n1 and n2 according to the MAX_2D or MAX_3D metric depending on their dimension. The used metric is also known as L∞-norm.
        Parameters:
        n1 - a Node with two or three dimensional coordinates
        n2 - a Node with two or three dimensional coordinates
        Returns:
        the MAX_2D or MAX_3D edge weight for nodes n1 and n2

      • computeManhattanDistance

        int computeManhattanDistance(TSPLIBImporter.Node n1, TSPLIBImporter.Node n2)
        Computes the distance of the two nodes n1 and n2 according to the MAN_2D or MAN_3D metric depending on their dimension. The used metric is also known as L1-norm.
        Parameters:
        n1 - a Node with two or three dimensional coordinates
        n2 - a Node with two or three dimensional coordinates
        Returns:
        the MAN_2D or MAN_3D edge weight for nodes n1 and n2

      • compute2DCeilingEuclideanDistance

        int compute2DCeilingEuclideanDistance(TSPLIBImporter.Node n1, TSPLIBImporter.Node n2)
        Computes the distance of the two nodes n1 and n2 according to the CEIL_2D metric, the round up version of EUC_2D. The points must have dimension two.
        Parameters:
        n1 - a Node with two or three dimensional coordinates
        n2 - a Node with two or three dimensional coordinates
        Returns:
        the CEIL_2D edge weight for nodes n1 and n2
        See Also:

      • compute2DGeographicalDistance

        int compute2DGeographicalDistance(TSPLIBImporter.Node n1, TSPLIBImporter.Node n2)
        Computes the distance of the two nodes n1 and n2 according to the GEO 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 - a Node with two or three dimensional coordinates
        n2 - a Node with two or three dimensional coordinates
        Returns:
        the GEO edge weight for nodes n1 and n2

      • computeRadiansAngle

        private static double computeRadiansAngle(double x)

      • compute2DPseudoEuclideanDistance

        int compute2DPseudoEuclideanDistance(TSPLIBImporter.Node n1, TSPLIBImporter.Node n2)
        Computes the distance of two the two nodes n1 and n2 according to the ATT metric. The nodes must have two dimensional coordinates.
        Parameters:
        n1 - a Node with two dimensional coordinates
        n2 - a Node with two dimensional coordinates
        Returns:
        the ATT edge weight for nodes n1 and n2

      • getL1Distance

        private double getL1Distance(TSPLIBImporter.Node n1, TSPLIBImporter.Node n2)

      • getL2Distance

        private double getL2Distance(TSPLIBImporter.Node n1, TSPLIBImporter.Node n2)

      • getLInfDistance

        private double getLInfDistance(TSPLIBImporter.Node n1, TSPLIBImporter.Node n2)