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

Class 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 java.lang.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