Source: problems/EuclideanTSP.js

import { Permutation } from "./configurationTypes/Permutation";
import { Problem, ProblemTypeEnum } from './Problem'

/**
 * Class representing Euclidean TSP.
 */
export class EuclideanTSP extends Problem {
    /**
     * Constructor, construct the class from the data file selected.
     * @param {string} data instance of a problem coded as string
     */
    constructor(data) {
        super();
        var dataSet = data.split('\n');
        this._noCities = + dataSet[0].split(/\s+/)[0];
        this._cities = new Array(this._noCities);

        for (var i = 0; i < this._noCities; i++) {
            var coords = dataSet[1+i].split(/\s+/);
            this._cities[i] = {x: +coords[0], y: +coords[1]};
        }
        //create cache
        this._distanceCache = new Array(this._noCities);
        for (var i = 0; i < this._noCities; i++) {
            this._distanceCache[i] = new Array(this._noCities);
            for (var j = 0; j < this._noCities; j++) {
                this._distanceCache[i][j] = null;
            }
        }
    }

    /**
     * Returns fitness of selected configuration (Permutation)
     * @param  {class} permutationConfig Permutation of which fitness we want
     * @return {int}  calculated fitness of the configuration
     */
    evaluateMaximizationCost(permutationConfig) {
        var price = 0;

        var permutation = permutationConfig.getArray();

        for(var i = 0; i < permutation.length - 1; i++)
        {
            if (this._distanceCache[permutation[i]][permutation[i+1]] === null) {
                // count to cache
                this._distanceCache[permutation[i]][permutation[i+1]] = this.countEuclideanDistance(this._cities[permutation[i]], this._cities[permutation[i+1]]);
                this._distanceCache[permutation[i+1]][permutation[i]] = this._distanceCache[permutation[i]][permutation[i+1]];
            }
            price -= this._distanceCache[permutation[i]][permutation[i+1]];
        }
        if (this._distanceCache[permutation[permutation.length - 1]][permutation[0]] == null) {
            // count to cache
            this._distanceCache[permutation[permutation.length - 1]][permutation[0]] = this.countEuclideanDistance(this._cities[permutation[permutation.length - 1]], this._cities[permutation[0]]);
            this._distanceCache[permutation[0]][permutation[permutation.length - 1]] = this._distanceCache[permutation[permutation.length - 1]][permutation[0]]
        }
        price -= this._distanceCache[permutation[permutation.length - 1]][permutation[0]];
        return price;
    }

    /**
     * Counts Euclidean distance between 2 points
     * @param coord1 coordinates of first point with x and y field
     * @param coord2 coordinates of second point with x and y field
     * @returns {number} Euclidean distance between given points
     */
    countEuclideanDistance(coord1, coord2){
        return Math.sqrt(Math.pow((coord1.x - coord2.x), 2) + Math.pow((coord1.y - coord2.y), 2));
    }

    /**
     * Transforms maximization cost to real cost of problem.
     * @param {number} maxCost maximization cost to transform.
     * @returns {number} Negative value of maxCost.
     */
    transformMaximizationToRealCost(maxCost) {
        return -maxCost;
    }

    /**
     * Returns random, or sorted starting from 0, configuration of traveling salesman problem(Permutation configuration)
     * @param  {bool} random random or sorted staring with 0
     * @return {Permutation}  new Permutation class
     */
    getConfiguration(random) {
        return new Permutation({
            size: this._noCities,
            random: random
        });
    }

    /**
     * Gets permutation array from configuration.
     * @param  {class} permutationConfig permutation of which path we want to get
     * @return {String} path
     */
    getResult(permutationConfig) {
        return permutationConfig.getArray();
    }

    /**
     * Returns problem type.
     * @returns {string} permutation
     */
    getType() {
        return ProblemTypeEnum.PERMUTATION;
    }

    /**
     * Resolves number od cities range of x and y coordinates.
     * @param {string} instanceContent content of file with instance
     * @returns {{noCities: number, x: number, y: number}} object with instance params
     */
    static resolveInstanceParams(instanceContent) {
        var dataSet = instanceContent.split('\n');
        var noCities = + dataSet[0].split(/\s+/)[0];
        var xMin = null;
        var xMax = null;
        var yMin = null;
        var yMax = null;

        for (var i = 0; i < noCities; i++) {
            var coords = dataSet[1+i].split(/\s+/);
            if (xMin === null || xMin > +coords[0]) {
                xMin = +coords[0];
            }
            if (xMax === null || xMax < +coords[0]) {
                xMax = +coords[0];
            }
            if (yMin === null || yMin > +coords[1]) {
                yMin = +coords[1];
            }
            if (yMax === null || yMax < +coords[1]) {
                yMax = +coords[1];
            }
        }
        return {
            noCities: noCities,
            x: xMax-xMin,
            y: yMax-yMin
        }
    }

    /**
     * Returns instance invalidity
     * @param  {string} instanceContent content of file with instance
     * @return {boolean} is instance invalid
     */
    static isInvalidInstance(instanceContent) {
        var dataSet = instanceContent.split('\n');
        if(isNaN(dataSet[0].split(/\s+/)[0])) return { text: "First parameter must be a number."};
        var noCities = + dataSet[0].split(/\s+/)[0];

        if((instanceContent.length - 1) < noCities) return { text: "Invalid number of lines."};

        for (var i = 0; i < noCities; i++) {
            var coords = dataSet[1+i].split(/\s+/);
            if((coords.length) < 2) return { text: "Invalid number of coordinates on line."};
            if(isNaN(coords[0]) || isNaN(coords[1])) return { text: "Coordinate must be a number."};
        }
        return false; // valid instance
    }
}