/ - Diff - | gvSIG desktop 1 - gvSIG

Revision 23229

     import java.util.Random;
     import org.gvsig.graph.core.GvFlag;
     import com.sun.org.apache.xpath.internal.operations.Mod;
     public class TspSolverAnnealing {
     	static int T_INIT = 100;
     	static double FINAL_T = 0.1;
     	static double COOLING = 0.9; /* to lower down T (< 1) */
     	int n;
     	int[] iorder;
     	int[] jorder;
     	float[] b = new float[4];
     	double[][] odMatrix;
     	boolean g_bVolverOrigen;
     	boolean bReturnToOrigin;
     	int origenTSP, destinoTSP;
     	int[] vTSP;
     	static int T_INIT = 100;
     	static double FINAL_T = 0.1;
     	static double COOLING = 0.9; /* to lower down T (< 1) */
     	int TRIES_PER_T = 500*n; // TODO: PONER ESTO BIEN.
     	int IMPROVED_PATH_PER_T = 60*n;  // TODO: PONER ESTO BIEN.
     //	static long A[56]= {-1};
     //	long *rand_fptr = A;
     //	#define mod_diff(x,y)   (((x)-(y))&0x7fffffff)
     //	private long flipCycle()
     //	{
     //		long *ii,*jj;
     //		for (ii = &A[1], jj = &A[32]; jj <= &A[55]; ii++, jj++)
     //		*ii= mod_diff (*ii, *jj);
     //
     //		for (jj = &A[1]; ii <= &A[55]; ii++, jj++)
     //		*ii= mod_diff (*ii, *jj);
     //		rand_fptr = &A[54];
     //		return A[55];
     //	}
     //	typedef int Path[3];      /* specify how to change path */
     	/*
     	 * State vars
     	 */
     	int     verbose = 0;
     //	 Point   *cities;
     //	 int     *dist;
     	private GvFlag[] flags  = null;
     	private boolean bVolverOrigen = false;
     	private double distTotMin = Double.MAX_VALUE;
     //	#define D(x,y) odMatrix[x][y]    //dist[(x)*n+y]
     	/* float calcula_dist_ordenacion(int v[], int bVolverOrigen)
+    	{
     		float dist, distTot;
-...
     	        distTot = odMatrix[origenTSP][v[0]]; // Origen al primer punto
     	        for (i = 0; i< numElemTSP-1;i++)
+    			{
     	            //frmDocMap.Distancia v(i), v(i + 1), dist, tiempo
     				dist = odMatrix[v[i]][v[i+1]];
     	            distTot = distTot + dist;
+    			}
     	        //  desde y hasta el almacen (distancia al primero y al ?ltimo
     	        // frmDocMap.Distancia idNodoOrigen, v(0), dist, tiempo
     	        if (bVolverOrigen)
+    			{
     				dist = odMatrix[v[numElemTSP-1]][origenTSP];
-...
     		int i;
     		double len = 0;
     		len = odMatrix[origenTSP][iorder[0]];
     		len = D(origenTSP, iorder[0]);
     		for (i = 0; i < n-1; i++)
+    		{
     			len += odMatrix[iorder[i]][iorder[i+1]];
     			len += D(iorder[i], iorder[i+1]);
+    		}
     		if (g_bVolverOrigen)
     			len += odMatrix[iorder[n-1]][origenTSP]; /* close path */
     		if (bReturnToOrigin)
     			len += D(iorder[n-1], origenTSP); /* close path */
     		else
     			len += odMatrix[iorder[n-1]][destinoTSP]; /* close path */
     			len += D(iorder[n-1], destinoTSP); /* close path */
     		return (len);
+    	}
     	/*
     	 * Prim's approximated TSP tour
     	 * See also [Cristophides'92]
     	 */
     	// TODO: NO LO USO => Borrar esta funci?n.
     	void findEulerianPath()
+    	{
     		int[] mst = new int[n];
     		int[] arc = new int[n];
     		int i, j = 0, k = 0, l, a;
     		double d, maxd;
     		double[] dis = new double[n];
     		maxd = Math.sqrt(b[1]-b[0])+ Math.sqrt(b[3]-b[2]);
     		d    = maxd;
     		dis[0] = -1;
     		for (i = 1; i < n; i++)
+    		{
     			dis[i] = odMatrix[i][0]; arc[i] = 0;
     		        if (d > dis[i])
+    			{
     				d = dis[i];
     				j = i;
+    			}
+    		}
     		/*
     		 * O(n^2) Minimum Spanning Trees by Prim and Jarnick
     		 * for graphs with adjacency matrix.
     		 */
     		for (a = 0; a < n - 1; a++)
+    		{
     			mst[a] = j * n + arc[j]; /* join fragment j with MST */
     			dis[j] = -1;
     			d = maxd;
     			for (i = 0; i < n; i++)
+    			{
     				if (dis[i] >= 0) /* not connected yet */
+    				{
     					if (dis[i] > odMatrix[i][j])
+    					{
     						dis[i] = odMatrix[i][j];
     						arc[i] = j;
+    					}
     					if (d > dis[i])
+    					{
     						d = dis[i];
     						k = i;
+    					}
+    				}
+    			}
     			j = k;
+    		}
     		/*
     		 * Preorder Tour of MST
     		 */
     //	#define VISITED(x) jorder[x]
     //	#define NQ(x) arc[l++] = x
     //	#define DQ()  arc[--l]
     //	#define EMPTY (l==0)
     		for (i = 0; i < n; i++) jorder[i] = 0;
     		k = 0; l = 0; d = 0;
     		arc[l++] = 0;
     		while (l != 0)
+    		{
     			i = arc[--l];
     			if (!(jorder[i] == 0))
+    			{
     				iorder[k++] = i;
     				jorder[i]  = 1;
     				for (j = 0; j < n - 1; j++) /* push all kids of i */
+    				{
     					if (i == mst[j]%n)
     						arc[l++] = mst[j]/n;
+    				}
+    			}
+    		}
+    	}
     	int mod(int a, int b) {
     		return (a % b);
     		int aux = (a % b);
     		if (aux < 0)
     			aux = aux + b;
     		return aux;
+    	}
     	double D(int f, int t) {
-...
     		// b va a ser el nuevo origen => sumamos su distancia a nuestro origen fijo
     		double Dant, Dnuevo, Ddiff = 0;
     		Dant = odMatrix[origenTSP][iorder[0]];
     		Dnuevo = odMatrix[origenTSP][b];
     		Dant = D(origenTSP, iorder[0]);
     		Dnuevo = D(origenTSP, b);
     		Ddiff = Dnuevo - Dant;
     		// tambi?n hay que mirar la distancia al destino desde el ?ltimo punto
     		int fin=n-1;
     		if (g_bVolverOrigen)
     		if (bReturnToOrigin)
+    		{
     			// p[2] va a ser el pr?ximo ?ltimo punto
     			Dant = D(iorder[fin], origenTSP);
-...
     			Ddiff = Dnuevo-Dant;
+    		}
     		int fin = n-1;
     		if (g_bVolverOrigen) // Miramos la distancia al cero
     		if (bReturnToOrigin) // Miramos la distancia al cero
+    		{
     			// iorder[p[1]] o iorder[p[0]] va a acabar en la ?ltima posici?n
     			if (p[0]==fin || p[1] == fin) // tambi?n hay que mirar la distancia al destino desde el ?ltimo punto
-...
     	double annealing()
+    	{
     		int[] p;
     		int[] p = new int[3];
     		int    i=1, j, pathchg;
     		int    numOnPath, numNotOnPath;
     		double    pathlen, bestlen;
     		double energyChange, T;
     		/*
     		 * Set up first eulerian path iorder to be improved by
     		 * simulated annealing.
-...
     		pathlen = pathLength(); // (iorder);
     		bestlen = pathlen;
     		Random rnd = new Random();
     		int TRIES_PER_T = 500*n;
     		int IMPROVED_PATH_PER_T = 60*n;
     		for (T = T_INIT; T > FINAL_T; T *= COOLING)  /* annealing schedule */
+    	        {
-...
     				do {
     					p[0] = rnd.nextInt(n);
     					p[1] = rnd.nextInt(n);
     					if (p[0] == p[1]) p[1] = mod(p[0]+1,n); /* non-empty path */
     					if (p[0] == p[1])
     						p[1] = mod(p[0]+1,n); /* non-empty path */
     					numOnPath = mod(p[1]-p[0],n) + 1;
     					numNotOnPath = n - numOnPath;
     				} while (numOnPath < 2 || numNotOnPath < 2) ; /* non-empty path */
     				double rreal = rnd.nextDouble();
     				if ((rnd.nextInt() % 2) == 0) /*  threeWay */
+    				{
     					do {
     						p[2] = mod(rnd.nextInt(numNotOnPath)+p[1]+1,n);
     					} while (p[0] == mod(p[2]+1,n)); /* avoids a non-change */
     					energyChange = getThreeWayCost (p);
     					if ((energyChange < 0) || (RREAL < Math.exp(-energyChange/T)))
     					if ((energyChange < 0) || (rreal < Math.exp(-energyChange/T)))
+    					{
     						pathchg++;
     						pathlen += energyChange;
-...
     				else            /* path Reverse */
+    				{
     					energyChange = getReverseCost (p);
     					if ((energyChange < 0) || (RREAL < Math.exp(-energyChange/T)))
     					if ((energyChange < 0) || (rreal < Math.exp(-energyChange/T)))
+    					{
     						pathchg++;
     						pathlen += energyChange;
-...
     		return bestlen;
+    	}
     	public void setStops(GvFlag[] flags) {
     		this.flags = flags;
+    	}
     	/**
     	 * This function will use annealing only if numStops >= 6. If numStops < 6, it will
     	 * use direct calculation, ensuring the optimum result.
     	 * @return
     	 */
     	public GvFlag[] calculate() {
     		GvFlag[] orderedStops = new GvFlag[flags.length];
     		int numStops = flags.length;
     		int numElemTSP;
     		origenTSP = 0;
     		destinoTSP = numStops-1;
     		if (bVolverOrigen )
     			numElemTSP = numStops-1;
     		else
     			numElemTSP = numStops-2;
     		n = numElemTSP;
     		bReturnToOrigin = bVolverOrigen;
     		iorder = new int[n];
     		jorder = new int[n];
     		vTSP = new int[numStops];
     		vTSP[0] = origenTSP;
     		vTSP[numStops-1] = destinoTSP;
     		if (numElemTSP > 0)
+    		{
     			// v = new int[numElemTSP];
     			for (int i=0; i< numElemTSP; i++)
+    			{
     				iorder[i] = i + 1;
     				vTSP[i+1] = i + 1; // v[i];
+    			}
+    		}
     		/* identity permutation */
     		// for (i = 0; i < n; i++) iorder[i] = i+1;
     		double distTotal=0.0;
     		if (numElemTSP < 7)
+    		{
     			distTotMin = calculate_distance(iorder,bVolverOrigen);
     			permut(iorder, numElemTSP, bVolverOrigen);
     			distTotal = distTotMin ;
+    		}
     		else
+    		{
     			distTotal = annealing();
+    		}
     		System.out.println("DistTotal = " + distTotal);
     		System.out.print("new order = [");
     		for (int i=0; i < vTSP.length; i++) {
     			orderedStops[i] = flags[vTSP[i]];
     			System.out.print(vTSP[i] + " ");
+    		}
     		System.out.println("]");
     		return orderedStops;
+    	}
     	double calculate_distance(int v[], boolean bVolverOrigen)
+    	{
     		double dist, distTot;
     		int i;
     	        distTot = D(origenTSP, v[0]); // Origen al primer punto
     	        for (i = 0; i< n-1;i++)
+    			{
     	            //frmDocMap.Distancia v(i), v(i + 1), dist, tiempo
     				dist = D(v[i], v[i+1]);
     	            distTot = distTot + dist;
+    			}
     	        //  desde y hasta el almacen (distancia al primero y al ?ltimo
     	        if (bVolverOrigen)
+    			{
     				dist = D(v[n-1], origenTSP);
     	            distTot = distTot + dist;
+    	        }
     			else
+    			{
     				dist = D(v[n-1], destinoTSP);
     				distTot = distTot + dist;
+    			}
     			return distTot;
+    	}
     	void exchange(int v[], int p1, int p2)
+    	{
     	  int aux;
     	  aux = v[p1];
     	  v[p1] = v[p2];
     	  v[p2] = aux;
+    	}
     	 void permut (int v[], int m, boolean bVolverOrigen)
+    	{
     	  int i, j;
     	  double distTot;
     	  if (m > 0)
     	    for (i = 0; i < m; i++)
+    	      {
     	    	exchange(v, i, m-1);
     	        permut (v, m-1, bVolverOrigen);
     	        exchange(v, i, m-1);
+    	      }
     	  else
+    	  {
     	     // escribir_vector (v);
     	     // Aqu? tenemos el vector que buscamos
     	     // Calculamos su distancia y si es menor que la que tenemos guardada, guardamos el nuevo vector.
     		  distTot = calculate_distance(v, bVolverOrigen);
     	        if (distTot < distTotMin)
+    			{
     	            distTotMin = distTot;
     	            for (j = 0; j< n; j++)
     	                vTSP[j+1] = v[j];
+    	        }
     	        // 'MuestraVector v
+    	  }
+    	}
     	public void setODMatrix(double[][] odMatrix) {
     		this.odMatrix = odMatrix;
+    	}
     	/**
     	 * @return true if the path is closed => will return to origin.
     	 * @see setReturnToOrigin
     	 */
     	public boolean isClosed() {
     		return bReturnToOrigin;
+    	}
     	public void setReturnToOrigin(boolean returnToOrigin) {
     		bReturnToOrigin = returnToOrigin;
+    	}
+    }

     		View v = (View) PluginServices.getMDIManager().getActiveWindow();
     		MapContext map = v.getMapControl().getMapContext();
     		SingleLayerIterator it = new SingleLayerIterator(map.getLayers());
     		// TODO: DISTINGUIR ENTRE OR?GENES Y DESTINOS. AHORA MISMO LOS DOS COINCIDEN.
     		// El usuario tiene que poder escoger un tema de or?genes y otro de destinos.
     		if (actionCommand.equals("ODMATRIX")) {
     			while (it.hasNext())
-...
     						return;
+    					}
     //					PluginServices.getMDIManager().addWindow(new RouteControlPanel(net));
     					JFileChooser dlg = new JFileChooser();
     					if (dlg.showSaveDialog((Component) PluginServices.getMainFrame()) == JFileChooser.APPROVE_OPTION)
+    					{
     //						RandomAccessFile file = null;
     //						try {
     //							file = new RandomAccessFile(dlg.getSelectedFile(), "rw");
     //						} catch (FileNotFoundException e1) {
     //							// TODO Auto-generated catch block
     //							e1.printStackTrace();
     //						}
     						BufferedWriter output;
     						try {
     							output = new BufferedWriter(new FileWriter(dlg.getSelectedFile()));

Also available in: Unified diff