Source: problems/TravellingSalesman.js

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

export class TravellingSalesman extends Problem {
    /**
     * Constructor, construct the class from the data file selected.
     * Calculates n:n distance between nodes using Floyd-Warshall algorithm
     * @param {string} data instance of a problem coded as string
     */
    constructor(data) {
        super();
        data = data.split(/\s+/);

        this._type = data[0];
        this._noNodes = +data[1];
        this._noEdges = +data[2];
        this._noNodesToVisit = +data[3];
        this._maxPrice = +data[4];
        this._nodesToVisit = [];

        data.splice(0, 5);

        if(this._type === "Shortest") {
          for(var i = 0; i < this._noNodesToVisit; i++)
          {
              this._nodesToVisit.push(+data[i]);
          }

          data.splice(0, this._noNodesToVisit);
        }

        this._distanceArray = new Array(this._noNodes);
        this._pathArray = new Array(this._noNodes);

        for(var i = 0; i < this._noNodes; i++)
        {
            this._distanceArray[i] = new Array(this._noNodes);
            this._pathArray[i] = new Array(this._noNodes);
        }

        // initializing arrays, distance array to inf if no edge, and path array to null if no edge
        for(var i = 0; i < this._noNodes; i++)
        {
            for(var j = 0; j < this._noNodes; j++)
            {
                if(+data[i * this._noNodes + j] !== 0 || i === j) {
                    this._distanceArray[i][j] = +data[i * this._noNodes + j];
                    this._pathArray[i][j] = j;
                }
                else {
                    this._distanceArray[i][j] = Number.MAX_SAFE_INTEGER;
                    this._pathArray[i][j] = null;
                }
            }
        }
        var start, end;
        // if shortest calculate shortest path using floyd warshall
        if(this._type === "Shortest") {
          if(this._noNodes !== this._noNodesToVisit) this._dijkstra();
          else this._floydWarshall();
        }
    }

    /**
     * Floyd warshall algorithm to calculate n:n distances between nodes(vertexes), saves it to _distanceArray, _pathArray for path reconstruction
     * @return {null}
     */
    _floydWarshall() {
        for(var i = 0; i < this._noNodes; i ++)
        {
            for(var j = 0; j < this._noNodes; j ++)
            {
                for(var k = 0; k < this._noNodes; k ++)
                {
                    if(this._distanceArray[j][k] > this._distanceArray[j][i] + this._distanceArray[i][k]) {
                        this._distanceArray[j][k] = this._distanceArray[j][i] + this._distanceArray[i][k];
                        this._pathArray[j][k] = this._pathArray[j][i];
                    }
                }
            }
        }
    }

    /**
     * Dijkstra algorithm to caculate path from nodes to visit to all other nodes
     * @return {null} doesnt return anything
     */
    _dijkstra() {
      var distanceArray = [];
      var pathArray = [];
      var nodes = [];
      var shortest;
      var chosenNode;

      const distances = this._distanceArray;
      // for all nodes
      for(var i = 0; i < this._noNodesToVisit; i++)
      {
        //initialization
        for(var j = 0; j < this._noNodes; j++)
        {
          distanceArray[j] = Number.MAX_SAFE_INTEGER;
          pathArray[j] = null;
          nodes.push(j);
        }

        distanceArray[this._nodesToVisit[i]] = 0;
        //while there are unvisited nodes
        while(nodes.length > 0)
        {
          shortest = Number.MAX_SAFE_INTEGER;
          for(var j = 0; j < nodes.length; j++)
          {
            if(distanceArray[nodes[j]] < shortest) {
              shortest = distanceArray[nodes[j]];
              chosenNode = nodes[j];
            }
          }
          //remove node with shortest path
          nodes.splice(nodes.indexOf(chosenNode), 1);
          // update shortest path and array for path rebuilding
          for(var j = 0; j < this._noNodes; j++)
          {
            if(shortest + distances[chosenNode][j] < distanceArray[j]) {
              distanceArray[j] = shortest + distances[chosenNode][j];
              pathArray[j] = chosenNode;
            }
          }
        }
        pathArray[this._nodesToVisit[i]] = this._nodesToVisit[i];

        // rebuild all paths and update _pathArray and _distanceArray arrays
        var currentNode;
        for(var k = 0; k < pathArray.length; k++)
        {
          currentNode = k;
          while(pathArray[currentNode] !== this._nodesToVisit[i])
          {
            this._pathArray[pathArray[currentNode]][k] = currentNode;
            currentNode = pathArray[currentNode];
          }
          this._pathArray[this._nodesToVisit[i]][k] = currentNode;
          this._distanceArray[this._nodesToVisit[i]][k] = distanceArray[k];
        }

      }

    }

    /**
     * Binds the permutaion from Permutation configuration, to the actual nodes to visit
     * @param  {class} permutationConfig permutaion configuration
     * @return {array} array with permutation binded to actual nodes
     */
    _bindToNodes(permutationConfig) {
        var myPermutation = permutationConfig.map(x=>x);

        for(var i = 0; i < this._noNodesToVisit; i++)
        {
            myPermutation[i] = this._nodesToVisit[myPermutation[i]];
        }

        return myPermutation;
    }
    /**
     * Rebuild the current path using _pathArray
     * @param  {class} permutationConfig Permutation of which path we are building
     * @return {String} return the rebuilded path
     */
    rebuildPath(permutationConfig) {
        var permutation = this._bindToNodes(permutationConfig);

        var path = [permutation[0]];

        for(var i = 1; i < permutation.length; i++)
        {
            while(permutation[i-1] != permutation[i])
            {
                permutation[i-1] = this._pathArray[permutation[i-1]][permutation[i]];
                path.push(permutation[i-1]);
            }
        }
        path.push(path[0]);

        return path;
    }

    /**
     * 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();

        if(this._type === "Shortest") permutation = this._bindToNodes(permutation);

        for(var i = 0; i < permutation.length - 1; i++)
        {
            price -= this._distanceArray[permutation[i]][permutation[i+1]];
        }

        price -= this._distanceArray[permutation[permutation.length - 1]][permutation[0]];

        return price;
    }

    transformMaximizationToRealCost(maxCost) {
        return -maxCost;
    }

    // /**
    //  * Return price function value that will be displayed in graph
    //  * @param  {class} bitArrayConfig config for which we want the value for the graph
    //  * @return {int}  the returned value
    //  */
    // getProblemCost(bitArrayConfig){
    //   return -this.getFitness(bitArrayConfig);
    // }

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

    /**
     * Returns the actual path of the configuration, the real config is only the permutation of nodes that has to be visited, not the path
     * @param  {class} permutationConfig permutation of which path we want to build
     * @return {String} the actual path as string
     */
    getResult(permutationConfig) {
        if(this._type === "Hamiltonian") return permutationConfig.getArray();

        return this.rebuildPath(permutationConfig.getArray());
    }

    /**
     * Returns what type of configuration is this problem using
     * @return {enum} type of the problem(configuration type)
     */
    getType() {
        return ProblemTypeEnum.PERMUTATION;
    }

    /**
     * Returns instance invalidity
     * @param  {string} instanceContent content of the instance
     * @return {boolean} is instance invalid
     */
    static isInvalidInstance(instanceContent) {
        instanceContent = instanceContent.split(/\s+/);

        var type = instanceContent[0];

        if(type !== "Hamiltonian" && type !== "Shortest")
        return { text: "TSP type not specified"};

        var noNodes = +instanceContent[1];
        var noEdges = +instanceContent[2];
        var noNodesToVisit = +instanceContent[3];
        var maxValue = +instanceContent[4];

        instanceContent.splice(0, 1);

        for(var i = 0; i < instanceContent.length; i++){
          if(isNaN(instanceContent[i])) return { text: "Most contain only numbers"};
          if(+instanceContent[i] < 0) return { text: "Can not contain negative numbers"};
        }

        if(noNodesToVisit > noNodes) return { text: "Number of nodes to visit cant be higher than number of nodes"};
        if(noEdges > (noNodes * (noNodes - 1)) / 2) return { text: "Number of edges cant be higher than (number of nodes * (number of nodes - 1)) / 2 becasue graph is not oriented."}
        instanceContent.splice(0, 4);

        if(type === "Hamiltonian") {
          if((instanceContent.length - 1) !== noNodes * noNodes) return { text: "Invalid array"};
          if(noNodes !== noNodesToVisit) return { text: "Number of nodes must be equal to number of nodes to visit for Hamiltonian type"};
          if(noEdges !== (noNodes * (noNodes - 1)) / 2) return { text: "Number of edges must be equal to (number of nodes * (number of nodes - 1)) / 2"};

          for(var i = 0; i < noNodes * noNodes; i++)
          {
              if(i % (noNodes + 1) !== 0 && +instanceContent[i] === 0) return { text: "Graph must be complete"};
          }
        }
        else {
          var array = new Array(noNodes);
          var numberOfEdges = 0;

          if(noEdges < noNodes - 1) return { text: "Number of edges must be atleast number of nodes - 1"};

          for(var i = 0; i < noNodesToVisit; i++)
          {
            if(+instanceContent[i] > (noNodes - 1)) return { text: "Node you want to visit doesnt exist: \"" +instanceContent[i] + "\". Must be lower than number of nodes - 1"};
          }

          for(var i = 1; i < noNodesToVisit; i++)
          {
            if(+instanceContent[i-1] > +instanceContent[i]) return { text: "Nodes to visit must be sorted in ascending order"};
            if(+instanceContent[i-1] === +instanceContent[i]) return { text: "Nodes to visit cant contaion duplicates"};
          }

          if((instanceContent.length - 1) !== (noNodes * noNodes) + noNodesToVisit) return { text: "Invalid array size, or nodes to visit size"};

          instanceContent.splice(0, noNodesToVisit);

          for(var i = 0; i < noNodes; i++)
          {
              array[i] = new Array(noNodes);
          }

          for(var i = 0; i < noNodes; i++)
          {
            for(var j = 0; j < noNodes; j++)
            {
              array[i][j] = +instanceContent[i * noNodes + j];
              if(array[i][j]) numberOfEdges++;
            }
          }
          if(numberOfEdges / 2 !== noEdges) return { text: "Number of edges is not correct"};
          if(!TravellingSalesman._isGraphStronglyConnected(array)) return { text: "Graph must be strongly connected"};
        }

        for(var i = 0; i < noNodes * noNodes; i++)
        {
            if(+instanceContent[i] > maxValue) return { text: "Edge weight cant exceed maximum edge weight"};
            if(i % (noNodes + 1) === 0 && +instanceContent[i] !== 0) return { text: "Diagonal must contain only 0"};
        }

        return false; // valid instance
    }

    /**
     * Check if graph is connected
     * @param  {Array}  array graph as an 2D array
     * @return {Boolean}  true if connected, false if not
     */
    static _isGraphStronglyConnected(array){
      var connected = [];
      var opened = [];

      connected.push(0);
      opened.push(0);
      //while there are open vertices to check
      while(opened.length > 0)
      {
          for(var k = 0; k < array.length; k++){
            //if theres an edge, and the vertice wasnt visited yet
            if(array[opened[0]][k] && !connected.includes(k)) {
              connected.push(k);
              opened.push(k);
              if(array[opened[0]][k] !== array[k][opened[0]]) return false;
            }
          }
          // if all vertices are visited the graph is connected
          if(connected.length === array.length) return true;
          //remove last visited vertice
          opened.shift();
        }
          return false;
      }

    /**
     * Returns parameters of the instance
     * @param  {string} instanceContent content of the instance
     * @return {object} instance parameters
     */
    static resolveInstanceParams(instanceContent) {
        instanceContent = instanceContent.split(/\s+/);

        return {
            type: instanceContent[0],
            noNodes: +instanceContent[1],
            noEdges: +instanceContent[2],
            noNodesToVisit: +instanceContent[3],
            maxPrice: +instanceContent[4]
        }
    }
}