# How convert the Traveling Salesperson JS to Object-oriented Programming style Java Processing

**URL:** <https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691>\
**Category:** Coding Questions\
**Tags:** homework\
**Created:** [January 2, 2021, 2:53pm UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691 "2021-01-02T14:53:24Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![psamead](https://avatars.discourse-cdn.com/v4/letter/p/2bfe46/32.png) [@psamead](https://discourse.processing.org/u/psamead)\
**Post date:** [January 2, 2021, 2:53pm UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691/1 "2021-01-02T14:53:24Z")

</div>

> please format code with \</\> button \* [homework policy](https://discourse.processing.org/faq/#homework) \* [asking questions](https://discourse.processing.org/t/2147)

Dear friends,  
I am learning the Processing and trying to convert Daniel’s ‘Traveling Sales Person’ JavaScript to the Java Processing in the Object Oriented style using the genetic algorithm method. But it seems my code is not actually calculating. I wonder ifsomeone can help me to find out the problem and teach me how to fix it.

Here is the code:

> int totalCities = 12;  
> int popSize = 500;
> 
> Population population;
> 
> void setup()  
> {  
> size(800, 800);  
> population = new Population();  
> }
> 
> void draw()  
> {  
> background(0);
> 
> population.run();  
> population.show();  
> }
> 
> class City  
> {  
> // PVector as the location of city on the screen  
> PVector loc; // psotion  
> float r; // circles radius
> 
> City(PVector p)  
> {  
> loc = p.copy();
> 
> ```
> r = 16;
> 
> ```
> 
> }  
> }
> 
> class Order  
> {  
> IntList index;  
> int shuffleTimes = 10;
> 
> Order()  
> {
> 
> ```
> index = new IntList();
> for(int i = 0; i < totalCities; i++)
> {
> index.append(i);
> }    
> 
> ```
> 
> }
> 
> void shuffleOrder()  
> {  
> for(int i = 0; i \< shuffleTimes; i++)  
> {  
> int numA = floor(random(index.size()));  
> int numB = floor(random(index.size()));  
> swap(index, numA, numB);  
> }  
> }
> 
> void swap(IntList list, int i, int j)  
> {  
> int tempA = list.get(i);  
> int tempB = list.get(j);  
> list.set(i, tempB);  
> list.set(j, tempA);  
> }
> 
> }
> 
> class Population  
> {  
> IntList population;  
> Order seqList;  
> City cities;
> 
> float fitness;
> 
> float recordDistance = Float.POSITIVE\_INFINITY;
> 
> IntList bestEver;  
> IntList currentBest;
> 
> //PVector points;
> 
> Population()  
> {  
> fitness = new float[popSize];
> 
> ```
> cities = new City[totalCities];
> for(int i = 0; i < totalCities; i++)
> {
> PVector v = new PVector(random(width), random(height/2));
> 
> cities[i] = new City(v);
> //cities[i] = new City();
> }
> 
> population = new IntList[popSize];
> seqList = new Order();
> 
> for(int i = 0; i < popSize; i++)
> {
> seqList.shuffleOrder();
> population[i] = seqList.index.copy();    
> } 
> 
> ```
> 
> }
> 
> float calcDistance(City cities, IntList list)  
> {  
> float sum = 0;  
> for(int i = 0; i \< list.size()- 1; i++)  
> {  
> int cityAIndex = list.get(i);  
> City cityA = cities[cityAIndex];  
> int cityBIndex = list.get(i+1);  
> City cityB = cities[cityBIndex];  
> float d = dist(cityA.loc.x, cityA.loc.y, cityB.loc.x, cityB.loc.y);  
> sum += d;  
> }  
> return sum;  
> }
> 
> void calculateFitness()  
> {  
> float currentRecord = Float.POSITIVE\_INFINITY;  
> for(int i = 0; i \< population.length; i++)  
> {  
> float d = calcDistance(cities, population[i]);  
> if(d \< recordDistance)  
> {  
> recordDistance = d;  
> bestEver = population[i];  
> }  
> if(d \< currentRecord)  
> {  
> currentRecord = d;  
> currentBest = population[i];  
> }
> 
> ```
> fitness[i] = 1/(pow(d, 8)+1);
> }
> 
> ```
> 
> }
> 
> void normalizeFitness()  
> {  
> float sum = 0;  
> for(int i = 0; i \< fitness.length; i++)  
> {  
> sum += fitness[i];  
> }  
> for(int i = 0; i \< fitness.length; i++)  
> {  
> fitness[i] = fitness[i]/sum;  
> }  
> }
> 
> void nextGeneration()  
> {  
> IntList newPopulation = new IntList[popSize];  
> for(int i = 0; i \< population.length; i++)  
> {  
> IntList orderA = pickOne(population, fitness);  
> IntList orderB = pickOne(population, fitness);  
> IntList order = crossOver(orderA, orderB);  
> mutate(order, 0.01);  
> newPopulation[i] = order;
> 
> ```
> }
> 
> ```
> 
> }
> 
> IntList pickOne(IntList list, float prob)  
> {  
> int index = 0;  
> float r = random(1);
> 
> ```
> while(r > 0)
> {
> r = r - prob[index];
> index++;
> }
> index--;
> 
> return list[index].copy();
> 
> ```
> 
> }
> 
> IntList crossOver(IntList orderA, IntList orderB)  
> {  
> int start = floor(random(orderA.size()));  
> int end = floor(random(start+1, orderA.size()));  
> IntList neworder = new IntList();  
> for(int i = start; i \< end; i++)  
> {  
> neworder.append(orderA.get(i));  
> }
> 
> ```
> for(int i = 0; i < orderB.size(); i++)
> {
> int city = orderB.get(i);
> if(!neworder.hasValue(city))
> {
> neworder.append(city);
> }
> }
> return neworder;
> 
> ```
> 
> }
> 
> void mutate(IntList order, float mutationRate)  
> {  
> for(int i = 0; i \< totalCities; i++)  
> {  
> if(random(1) \< mutationRate)  
> {  
> int indexA = floor(random(order.size()));  
> int indexB = (indexA + 1) % totalCities;  
> swap(order, indexA, indexB);  
> }  
> }  
> }
> 
> void swap(IntList a, int i, int j)  
> {  
> int temp1 = a.get(i);  
> int temp2 = a.get(j);  
> a.set(i, temp2);  
> a.set(j, temp1);  
> }
> 
> void run()  
> {  
> calculateFitness();  
> normalizeFitness();  
> nextGeneration();
> 
> }
> 
> void show()  
> {  
> stroke(250, 160, 0);  
> strokeWeight(4);  
> noFill();  
> beginShape();  
> for(int i = 0; i \< bestEver.size(); i++)  
> {  
> int n = bestEver.get(i);  
> vertex(cities[n].loc.x, cities[n].loc.y);  
> ellipse(cities[n].loc.x, cities[n].loc.y, 16, 16);  
> }  
> endShape();
> 
> ```
> translate(0, height/2);
> 
> stroke(250, 0, 160);
> strokeWeight(4);
> noFill();
> beginShape();
> for(int i = 0; i < currentBest.size(); i++)
> {
> int n = currentBest.get(i);
> vertex(cities[n].loc.x, cities[n].loc.y);
> ellipse(cities[n].loc.x, cities[n].loc.y, 16, 16);
> }
> endShape();
> 
> ```
> 
> }
> 
> }

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [January 2, 2021, 7:51pm UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691/2 "2021-01-02T19:51:20Z")

</div>

What do you see now and what do you want to see instead?

---

<div class="post-metadata">

**Author:** ![psamead](https://avatars.discourse-cdn.com/v4/letter/p/2bfe46/32.png) [@psamead](https://discourse.processing.org/u/psamead)\
**Post date:** [January 3, 2021, 9:53am UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691/3 "2021-01-03T09:53:13Z")

</div>

Hi Chrisir,  
Thanks for your kindly reply. I know there are problem here in framing this question. I am quite a newbie and don’t really know the exact question is. But basically my code results in a static image.

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/8/8634f761b9009772b2e1c53283b77af61d004732.png)

The functions doesn’t seem to generate new order objects to mark the cities. In the example provided by Dantiel [**CC\_035\_4\_TSP\_GA**](https://github.com/CodingTrain/website/tree/main/CodingChallenges/CC_035.4_TSP_GA/Processing/CC_035_4_TSP_GA), the functions constantly provide orders in comparision.

what kind of mistake do I make here that the code does not work in that way?

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [January 3, 2021, 3:22pm UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691/4 "2021-01-03T15:22:37Z")

</div>

I see

Error was that this line was missing  
` population = newPopulation;`

at the end of nextGeneration()

Chrisir

```auto
//
int totalCities = 12;
int popSize = 500;

Population population;

void setup()
{
  size(800, 800);
  population = new Population();

  frameRate(1);
}

void draw()
{
  background(0);

  population.run();
  population.show();

  print(".");
}

// ==================================================================================================

class City
{
  // PVector as the location of city on the screen
  PVector loc; // position
  float r; // circles radius

  City(PVector p)
  {
    loc = p.copy();
    r = 16;
  }
}

// ==================================================================================================

class Order
{
  IntList index;
  int shuffleTimes = 10;

  Order()
  {
    index = new IntList();
    for (int i = 0; i < totalCities; i++)
    {
      index.append(i);
    }
  }

  void shuffleOrder()
  {
    for (int i = 0; i < shuffleTimes; i++)
    {
      int numA = floor(random(index.size()));
      int numB = floor(random(numA, index.size())); // Added numA here !!!
      swap(index, numA, numB);
    }
  }

  void swap(IntList list, int i, int j)
  {
    int tempA = list.get(i);
    int tempB = list.get(j);
    list.set(i, tempB);
    list.set(j, tempA);
  }
}

// ==================================================================================================

class Population
{
  IntList[] population;
  Order seqList;
  City[] cities;

  float[] fitness;

  float recordDistance = Float.POSITIVE_INFINITY;

  IntList bestEver;
  IntList currentBest;

  //PVector points;

  Population()
  {
    fitness = new float[popSize];

    cities = new City[totalCities];
    for (int i = 0; i < totalCities; i++)
    {
      PVector v = new PVector(random(width), random(height/2));

      cities[i] = new City(v);
      //cities[i] = new City();
    }

    population = new IntList[popSize];
    seqList = new Order();

    for (int i = 0; i < popSize; i++)
    {
      seqList.shuffleOrder();
      population[i] = seqList.index.copy();
    }
  }

  float calcDistance(City[] cities, IntList list)
  {
    float sum = 0;
    for (int i = 0; i < list.size()- 1; i++)
    {
      int cityAIndex = list.get(i);
      City cityA = cities[cityAIndex];

      int cityBIndex = list.get(i+1);
      City cityB = cities[cityBIndex];

      float d = dist(cityA.loc.x, cityA.loc.y, 
        cityB.loc.x, cityB.loc.y);
      sum += d;
    }
    return sum;
  }

  void calculateFitness()
  {
    float currentRecord = Float.POSITIVE_INFINITY;
    for (int i = 0; i < population.length; i++)
    {
      float d = calcDistance(cities, population[i]);
      if (d < recordDistance)
      {
        recordDistance = d;
        bestEver = population[i].copy();
      }
      if (d < currentRecord)
      {
        currentRecord = d;
        currentBest = population[i].copy();
      }

      fitness[i] = 1/(pow(d, 8)+1);
    }
  }

  void normalizeFitness()
  {
    float sum = 0;
    for (int i = 0; i < fitness.length; i++)
    {
      sum += fitness[i];
    }
    for (int i = 0; i < fitness.length; i++)
    {
      fitness[i] = fitness[i]/sum;
    }
  }

  void nextGeneration()
  {
    IntList[] newPopulation = new IntList[popSize];
    for (int i = 0; i < population.length; i++)
    {
      IntList orderA = pickOne(population, fitness);
      IntList orderB = pickOne(population, fitness);
      IntList order = crossOver(orderA, orderB);
      mutate(order, 0.01); // was 0.01
      newPopulation[i] = order;
    }
    population = newPopulation;
  }

  IntList pickOne(IntList[] list, float[] prob)
  {
    int index = 0;
    float r = random(1);

    while (r > 0)
    {
      r = r - prob[index];
      index++;
    }
    index--;
    return list[index].copy();
  }

  IntList crossOver(IntList orderA, IntList orderB)
  {
    int start = floor(random(orderA.size()));
    int end = floor(random(start+1, orderA.size()));
    IntList neworder = new IntList();
    for (int i = start; i < end; i++)
    {
      neworder.append(orderA.get(i));
    }

    for (int i = 0; i < orderB.size(); i++)
    {
      int city = orderB.get(i);
      if (!neworder.hasValue(city))
      {
        neworder.append(city);
      }
    }
    return neworder;
  }

  void mutate(IntList order, float mutationRate)
  {
    for (int i = 0; i < totalCities; i++)
    {
      if (random(1) < mutationRate)
      {
        int indexA = floor(random(order.size()));
        int indexB = (indexA + 1) % totalCities;
        //print("before: " ); 
        //println(order);
        swap(order, indexA, indexB);
        //print("after: " );
        //println(order);
        //println("");
      }
    }
  }

  void swap(IntList a, int i, int j)
  {
    int temp1 = a.get(i);
    int temp2 = a.get(j);
    a.set(i, temp2);
    a.set(j, temp1);
  }

  void run()
  {
    calculateFitness();
    normalizeFitness();
    nextGeneration();
  }

  void show()
  {
    pushMatrix(); 

    stroke(250, 160, 0);
    strokeWeight(4);
    noFill();
    beginShape();
    for (int i = 0; i < bestEver.size(); i++)
    {
      int n = bestEver.get(i);
      vertex(cities[n].loc.x, cities[n].loc.y);
      ellipse(cities[n].loc.x, cities[n].loc.y, 16, 16);
    }
    endShape();
    popMatrix();

    pushMatrix(); 
    translate(0, height/2);

    stroke(250, 0, 160);
    strokeWeight(4);
    noFill();
    beginShape();
    for (int i = 0; i < currentBest.size(); i++)
    {
      int n = currentBest.get(i);
      vertex(cities[n].loc.x, cities[n].loc.y);
      ellipse(cities[n].loc.x, cities[n].loc.y, 16, 16);
    }
    endShape();
    popMatrix();
  }
  //
}//class Population
//

```

keywords:

- object-oriented programming,
- OOP,
- Traveling Salesman Problem, Traveling Salesperson Problem (TSP),
- Travelling Salesman Problem, Travelling Salesperson Problem (TSP),
- an [NP-hard](https://en.wikipedia.org/wiki/NP-hardness) problem in [combinatorial optimization](https://en.wikipedia.org/wiki/Combinatorial_optimization), important in [theoretical computer science](https://en.wikipedia.org/wiki/Theoretical_computer_science) and [operations research](https://en.wikipedia.org/wiki/Operations_research).

---

<div class="post-metadata">

**Author:** ![psamead](https://avatars.discourse-cdn.com/v4/letter/p/2bfe46/32.png) [@psamead](https://discourse.processing.org/u/psamead)\
**Post date:** [January 3, 2021, 4:42pm UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691/5 "2021-01-03T16:42:16Z")

</div>

Thanks for your kindly reply. This is very helpful and figuring out my mistake. The keywords are extremely useful to let me understand the topics behind. May I ask you a few more questions, if you have time to answer.

> [@Chrisir](#):
>
> `int numB = floor(random(numA, index.size())); // Added numA here !!!`

Is it to avoid the same number be picked here?

> [@Chrisir](#):
>
> ```auto
> if (random(1) < mutationRate)
> {
> int indexA = floor(random(order.size()));
> int indexB = (indexA + 1) % totalCities;
> //print("before: " ); 
> //println(order);
> swap(order, indexA, indexB);
> //print("after: " );
> //println(order);
> //println("");
> }
> 
> ```

It seems there are difference generated even without ‘numA’ being added.

> [@Chrisir](#):
>
> `(indexA + 1) % totalCities;`

Is here using % to give a reverse series of number? But why + 1 ? Because the floor function is used?

Sorry for my English.  
Very appreciate your time on my work befoe. Thank you again.

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [January 3, 2021, 5:01pm UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691/6 "2021-01-03T17:01:45Z")

</div>

> [@psamead](#):
>
> Is it to avoid the same number be picked here?

This was an error by me

Please delete this numA!!!

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [January 3, 2021, 5:03pm UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691/7 "2021-01-03T17:03:42Z")

</div>

> [@psamead](#):
>
> Is here using % to give a reverse series of number?

The % remainder is generally used to avoid that the value can get higher than this

When you say ` % totalCities` the result is 0,1,2… up to totalCities-1

---

<div class="post-metadata">

**Author:** ![psamead](https://avatars.discourse-cdn.com/v4/letter/p/2bfe46/32.png) [@psamead](https://discourse.processing.org/u/psamead)\
**Post date:** [January 4, 2021, 12:00am UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691/8 "2021-01-04T00:00:25Z")

</div>

Thanks your explaination.

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [January 4, 2021, 11:44am UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691/9 "2021-01-04T11:44:35Z")

</div>

> [@psamead](#):
>
> But why + 1 ? Because the floor function is used?

That I don’t know

I am sorry

---

<div class="post-metadata">

**Author:** ![psamead](https://avatars.discourse-cdn.com/v4/letter/p/2bfe46/32.png) [@psamead](https://discourse.processing.org/u/psamead)\
**Post date:** [January 4, 2021, 11:47am UTC](https://discourse.processing.org/t/how-convert-the-traveling-salesperson-js-to-object-oriented-programming-style-java-processing/26691/10 "2021-01-04T11:47:56Z")

</div>

Thanks still 🙂