cities.java

一个非常好的

/* Applet to solve the Traveling Salesman Problem
 * Copyright (C) 2002 Tobias Oetzel ([e-mail])
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published by the 
 * Free Software Foundation; either version 2 of the License, or (at your option)
 * any later version. This program is distributed in the hope that it will be 
 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. 
 * You should have received a copy of the GNU General Public License along with this program;
 * if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, 
 * Boston, MA 02111-1307, USA. 
*/



// system Routines to organize the tsp
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.lang.*;
import java.lang.Math;


class city
{
  // x,y coordinates
  protected int x;
  protected int y;
  // constructor
  public city(int myx, int myy)
  {
    if ((myx!=0) && (myy!=0)) 
    {
      x=myx;
      y=myy;
    }
  }
  
  
}

public class cities
{
  // Vector to hold city classes
	private Vector MyCities;
	// Vector to hold the Initial-StartConfiguration
	private Vector MyStartConfiguration;
	// "Main" Instance for gui propose
	private tsp    TspInstance;
	
	// constructor
	public cities(tsp MyInstance)
	{
	  TspInstance=MyInstance;
	  MyCities=new Vector();
	}
	
	public int findcity(int x,int y)
	{
	  city MyCity;
	  for(int i=0;i<MyCities.size();i++)
	  {
		MyCity=(city)MyCities.elementAt(i);
		if(x>=MyCity.x-5 && x<=MyCity.x+5 && y>=MyCity.y-5 && y<=MyCity.y+5)
	      return i;
	  }
	  return -1;
	}
	
  // add city to MyCities Vector
  public void AddCity(int x, int y)
  {
	  city MyCity;
	  MyCity=new city(x,y);
	  MyCities.addElement(MyCity);
    TspInstance.ChangeCityCount(1);
  }
  
  // remove city from MyCities Vector
  public void RemoveCity(int CityIndex)
  {
    TspInstance.MyDraw.RemoveCity(GetCityAt(CityIndex));
   	MyCities.removeElementAt(CityIndex);
    TspInstance.ChangeCityCount(-1);
  } 
  
  public int ManageCity(int x, int y)
  {
    if ((x<=TspInstance.MyDraw.DrawRight-5)  && (y<=TspInstance.MyDraw.DrawBottom-5))
  	{
  	  int CityIndex;
  	  CityIndex=findcity(x,y);
  	  if (CityIndex<0)
  	  {
  	  	AddCity(x,y);
        return 1;
  	  } 
  	  else
  	  {	
  	    RemoveCity(CityIndex);
        return 2;
  	  }  
    } 
    else 
    {
      return -1;
    }  
    	
  }  
  
  // remove all citees from MyCities Vector
  public void RemoveAllCities()
	{
		MyCities.removeAllElements();
    TspInstance.ResetCityCount();
  }		

	public int GetMyCitiesSize()
	{
		return MyCities.size();
	}	
	
  // return the city-object at position i in the MyCities vector
	public city GetCityAt(int i)
	{
    return (city)MyCities.elementAt(i);
	}	
	
	public Vector GetMyCities()
	{
	  return MyCities;
	}  
	
  // Generates i random cities und fill ups the MyCities vector
  public void GenerateRandomCities(int count)
  {
		int x,y;
		RemoveAllCities();
		for(int i=0;i<count;i++)
		{
      x=(int)(java.lang.Math.random()*(TspInstance.MyDraw.DrawRight-5));
      y=(int)(java.lang.Math.random()*(TspInstance.MyDraw.DrawBottom-5));
			if (findcity(x,y)==-1)
			{
			  AddCity(x,y);
  		} 
  		else
  		{
  		  count++;
  		}	 
		}
  }
  
  // Generates first random tour
  public void GenerateRandomStartSolution(boolean draw)
  {

    MyStartConfiguration = new Vector ();

    Vector TempCities;
    TempCities=new Vector ();
    for (int i=0;i<MyCities.size();i++)
    {
      TempCities.add(new Integer(i));
    }  

    int howmany;
    howmany = MyCities.size();
  
    // GetStartIndex
    int startindex;
    startindex=(int)(java.lang.Math.random()*howmany);
    MyStartConfiguration.addElement(new Integer(((Integer)TempCities.elementAt(startindex)).intValue()));
    TempCities.removeElementAt(startindex);
    
    // Generate Random Path
    howmany=TempCities.size();
    while (howmany>0)
    { 
      int index;
      index=(int)(java.lang.Math.random()*howmany);
      MyStartConfiguration.add(new Integer ( ((Integer)TempCities.elementAt(index)).intValue()));
      TempCities.removeElementAt(index);
      howmany=TempCities.size();
    }  
    
    if (draw)
    { 
      TspInstance.MyDraw.DrawConfiguration(MyStartConfiguration);
    }  
  }

  // Set first tour
  public void SetStartSolution(Vector v, boolean draw)
  {
    MyStartConfiguration = v;

    if (draw)
    { 
      TspInstance.MyDraw.DrawConfiguration(MyStartConfiguration);
    }  
  }
  
  private int square (int in)
  {
    return in*in;
  }
  
  public double GetDistanceCity(city ACity, city BCity)
  {
    return Math.sqrt(square(ACity.x-BCity.x)+
                     square(ACity.y-BCity.y));
  }  
  
  // return the Distance of a tour
  public double GetConfigurationDistance(Vector Config)
  {
    double result=0.0;
    int howmany;
    howmany=Config.size();
    
    for (int i=0;i<howmany-1;i++)
    {
      int a=((Integer)Config.elementAt(i)).intValue();
      int b=((Integer)Config.elementAt(i+1)).intValue();
      
      result+=GetDistanceCity(TspInstance.MyCities.GetCityAt(a),TspInstance.MyCities.GetCityAt(b));
    }
    
    int a=((Integer)Config.elementAt(howmany-1)).intValue();
    int b=((Integer)Config.elementAt(0)).intValue();
    result+=GetDistanceCity(TspInstance.MyCities.GetCityAt(a),TspInstance.MyCities.GetCityAt(b));
   
    return result;
  }  
  
  public Vector GetStartConfiguration()
  {
    return MyStartConfiguration;
  }  
  
  public void GenerateTucSymbol()
  {

    int x=25,
	y=85,
	dx=30,
	dy=30;
    
    // T
    AddCity( 0*dx+x,(int)(-0.1*dy+y));
    AddCity( 1*dx+x,(int)(-0.1*dy+y));
    AddCity( (int)(1.95*dx+x),(int)(-0.1*dy+y));
    AddCity( (int)(3.05*dx+x),(int)(-0.1*dy+y));
    AddCity( 4*dx+x,(int)(-0.1*dy+y));
    AddCity( 5*dx+x,(int)(-0.1*dy+y));

    AddCity( 0*dx+x,1*dy+y);
    AddCity( 1*dx+x,1*dy+y);
    AddCity( 4*dx+x,1*dy+y);
    AddCity( 5*dx+x,1*dy+y);

    AddCity( (int)(1.95*dx+x),1*dy+y);
    AddCity( (int)(1.95*dx+x),2*dy+y);
    AddCity( (int)(1.95*dx+x),3*dy+y);
    AddCity( (int)(1.95*dx+x),4*dy+y);
    AddCity( (int)(1.95*dx+x),5*dy+y);
    AddCity( (int)(1.95*dx+x),(int)(6.1*dy+y));

    AddCity( (int)(3.05*dx+x),1*dy+y);
    AddCity( (int)(3.05*dx+x),2*dy+y);
    AddCity( (int)(3.05*dx+x),3*dy+y);
    AddCity( (int)(3.05*dx+x),4*dy+y);
    AddCity( (int)(3.05*dx+x),5*dy+y);
    AddCity( (int)(3.05*dx+x),(int)(6.1*dy+y));


    // U
    AddCity( 5*dx+x,2*dy+y);
    AddCity( 5*dx+x,3*dy+y);
    AddCity( 5*dx+x,4*dy+y);
    AddCity( 5*dx+x,5*dy+y);

    AddCity( (int)(6.1*dx+x),(int)(-0.1*dy+y));
    AddCity( (int)(6.1*dx+x),1*dy+y);
    AddCity( (int)(6.1*dx+x),2*dy+y);
    AddCity( (int)(6.1*dx+x),3*dy+y);
    AddCity( (int)(6.1*dx+x),(int)(4.2*dy+y));
    AddCity( (int)(6.1*dx+x),(int)(5.8*dy+y));

    AddCity((int)(8.95*dx+x),1*dy+y);
    AddCity((int)(8.95*dx+x),2*dy+y);
    AddCity((int)(8.95*dx+x),3*dy+y);
    AddCity((int)(8.95*dx+x),(int)(4.2*dy+y));
    AddCity((int)(8.95*dx+x),(int)(5.8*dy+y));

    AddCity((int)(10.05*dx+x),(int)(-0.1*dy+y));
    AddCity((int)(10.05*dx+x),(int)(1.8*dy+y));
    AddCity((int)(10.05*dx+x),3*dy+y);
    AddCity((int)(10.05*dx+x),(int)(4.2*dy+y));
    AddCity((int)(10.05*dx+x),(int)(5.8*dy+y));

    AddCity((int)( 6.8*dx+x),5*dy+y);
    AddCity((int)( 8.2*dx+x),5*dy+y);

    AddCity( 7*dx+x,(int)(6.1*dy+y));
    AddCity( 8*dx+x,(int)(6.1*dy+y));

    // C
    AddCity(11*dx+x,(int)(-0.1*dy+y));
    AddCity(12*dx+x,(int)(-0.1*dy+y));
    AddCity(13*dx+x,(int)(-0.1*dy+y));
    AddCity(14*dx+x,(int)(0.2*dy+y));

    AddCity((int)(10.8*dx+x),1*dy+y);
    AddCity(12*dx+x,1*dy+y);
    AddCity(13*dx+x,1*dy+y);
    AddCity(14*dx+x,(int)(1.2*dy+y));
    
    AddCity((int)(10.8*dx+x),5*dy+y);
    AddCity(12*dx+x,5*dy+y);
    AddCity(13*dx+x,5*dy+y);
    AddCity(14*dx+x,(int)(4.8*dy+y));

    AddCity(11*dx+x,(int)(6.1*dy+y));
    AddCity(12*dx+x,(int)(6.1*dy+y));
    AddCity(13*dx+x,(int)(6.1*dy+y));
    AddCity(14*dx+x,(int)(5.8*dy+y));


  }  

}