Greedy TSP

City.pde

class City {
  PVector pos;
  int index;
  float dist;
  boolean used=false;

  City(PVector p, int I) {
    pos=p;
    index=I;
  }

  float getDist(PVector start) {
    return dist(pos.x, pos.y, start.x, start.y);
  }

  void show() {
    strokeWeight(10);
    if (index==startPoint) {
      stroke(0, 0, 255);
    } else {
      stroke(0);
    }
    point(pos.x, pos.y);
    fill(0);
    text(index, pos.x, pos.y-10);
    //println(index, used);
  }

  boolean compare(City other) {
    return dist(pos.x, pos.y, other.pos.x, other.pos.y)<0.000001;
  }
}

TSP.pde

ArrayList<City> cities=new ArrayList<City>();
ArrayList<PVector> positions=new ArrayList<PVector>();
int startPoint=0, Vnum=(int)random(5, 10);
float totalD=0;
int state=3;
boolean calculatedR=false, calculating=false;

void setup() {
  size(800, 600);
  for (int i=0; i<200; i++) {
    float x=random(width);
    float y=random(height);
    cities.add(new City(new PVector(x, y), i));
  }
}

void draw() {
  positions.clear();
  background(255);
  int previous=startPoint;
  startPoint=getStart(cities);
  if (previous!=startPoint) {
    calculatedR=false;
    totalD=0;
  }
  for (City c : cities) {
    c.used=false;
    c.show();

    strokeWeight(1);
    stroke(120, 50);
  }
  City startCity=cities.get(startPoint);
  if (state==1) {
    positions.add(startCity.pos);
    greedySalesmanRecursive(cities, startCity);
  } else if (state==3) {
    ArrayList<City> neighbors=getNeighbors(cities, startCity);
    for (City c : neighbors) {
      text(dist(c.pos.x, c.pos.y, startCity.pos.x, startCity.pos.y), c.pos.x, c.pos.y+20);
      drawLine(c.pos, startCity.pos);
    }
  }
  totalD=getTotalDist(positions);
  text("Route length: "+totalD, 200, 50);
}

void keyPressed() {
  if (key=='1') {
    state=1;
  } else if (key=='2') {
    state=2;
  } else if (key=='3') {
    state=3;
  }
}

void mousePressed() {
  for (City c : cities) {
    if (dist(mouseX, mouseY, c.pos.x, c.pos.y)<20) {
      c.pos.x=mouseX;
      c.pos.y=mouseY;
    }
  }
}


void greedySalesmanRecursive(ArrayList<City> list, City start) {
  if (!calculatedR) {//see the distance from start to the rest of cities, go to nearest, create a new list without the used one
    float recordD=MAX_FLOAT;
    int newC=start.index;
    //println(list.get(0).pos);
    for (City c : list) {
      if (c.index!=start.index&&!c.used) {
        float d=dist(c.pos.x, c.pos.y, start.pos.x, start.pos.y);
        if (d<recordD) {
          recordD=d;
          newC=list.indexOf(c);
        }
      }
    }
    start.used=true;
    if (newC<list.size()) {

      City newStart=list.get(newC);
      positions.add(newStart.pos);
      //totalD+=start.pos.dist(newStart.pos);
      drawLine(newStart.pos, start.pos);
      ArrayList<City> newL=new ArrayList<City>();
      newL.add(newStart);
      for (int i=0; i<list.size(); i++) {
        if (!list.get(i).used&&!list.get(i).compare(newStart)) {
          newL.add(list.get(i));
        }
      } 
      if (!newL.isEmpty()) {
        greedySalesmanRecursive(newL, newStart);
      } else {
        println("done");
        calculatedR=true;
        return;
      }
    }
  }
}

void getRoutesBruteForce(ArrayList<City> list, City start) {//iterate from each point to every other, store the index routes in intlists
  if (!list.isEmpty()) {
    for (int i=0; i<list.size(); i++) {
      ArrayList neighbors=getNeighbors(list, cities.get(i)); 
      getRoutesBruteForce(neighbors, cities.get(i));
    }
  }
}

ArrayList<City> getNeighbors(ArrayList<City> list, City start) {
  ArrayList<City> newL=new ArrayList<City>();
  for (City c : list) {
    if (c.index!=start.index) {
      newL.add(c);
    }
  }
  return newL;
}



float getTotalDist(ArrayList<PVector> list) {
  float out=0;
  for (int i=0; i<list.size()-1; i++) {
    out+=list.get(i).dist(list.get(i+1));
  }

  return out;
}

int getStart(ArrayList<City> list) {
  float recordDist=MAX_FLOAT;
  int index=0;
  for (City c : list) {
    float aux=dist(c.pos.x, c.pos.y, mouseX, mouseY);
    if (aux<recordDist) {
      recordDist=aux;
      index=list.indexOf(c);
    }
  }
  return index;
}

boolean allCitiesVisited(ArrayList<City> list) {
  boolean done=true;
  for (City c : list) {
    if ( c.used) {
      done=false;
    }
  }
  //println(done);
  return done;
}


void drawLine(PVector start, PVector end) {
  pushStyle();
  strokeWeight(1);
  stroke(200, 0, 0);
  line(start.x, start.y, end.x, end.y);
  popStyle();
}