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.

    Author:
    Hannes Wellmann

    • 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

      • 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

      • extractValueBeforeWhitespace

        public String extractValueBeforeWhitespace(String value)