svn-gvsig-desktop / tags / PilotoRedes_Build_4 / extensions / extGraph_predes / src / com / iver / cit / gvsig / graph / solvers / ShortestPathSolverAStar.java @ 12191
History | View | Annotate | Download (17.8 KB)
1 |
/* gvSIG. Sistema de Informaci?n Geogr?fica de la Generalitat Valenciana
|
---|---|
2 |
*
|
3 |
* Copyright (C) 2004 IVER T.I. and Generalitat Valenciana.
|
4 |
*
|
5 |
* This program is free software; you can redistribute it and/or
|
6 |
* modify it under the terms of the GNU General Public License
|
7 |
* as published by the Free Software Foundation; either version 2
|
8 |
* of the License, or (at your option) any later version.
|
9 |
*
|
10 |
* This program is distributed in the hope that it will be useful,
|
11 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
12 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
13 |
* GNU General Public License for more details.
|
14 |
*
|
15 |
* You should have received a copy of the GNU General Public License
|
16 |
* along with this program; if not, write to the Free Software
|
17 |
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,USA.
|
18 |
*
|
19 |
* For more information, contact:
|
20 |
*
|
21 |
* Generalitat Valenciana
|
22 |
* Conselleria d'Infraestructures i Transport
|
23 |
* Av. Blasco Ib??ez, 50
|
24 |
* 46010 VALENCIA
|
25 |
* SPAIN
|
26 |
*
|
27 |
* +34 963862235
|
28 |
* gvsig@gva.es
|
29 |
* www.gvsig.gva.es
|
30 |
*
|
31 |
* or
|
32 |
*
|
33 |
* IVER T.I. S.A
|
34 |
* Salamanca 50
|
35 |
* 46005 Valencia
|
36 |
* Spain
|
37 |
*
|
38 |
* +34 963163400
|
39 |
* dac@iver.es
|
40 |
*/
|
41 |
package com.iver.cit.gvsig.graph.solvers; |
42 |
|
43 |
import java.util.ArrayList; |
44 |
import java.util.Stack; |
45 |
|
46 |
import com.iver.cit.gvsig.fmap.DriverException; |
47 |
import com.iver.cit.gvsig.fmap.core.IFeature; |
48 |
import com.iver.cit.gvsig.fmap.core.IGeometry; |
49 |
import com.iver.cit.gvsig.fmap.core.v02.FConverter; |
50 |
import com.iver.cit.gvsig.fmap.drivers.DriverIOException; |
51 |
import com.iver.cit.gvsig.fmap.layers.VectorialAdapter; |
52 |
import com.iver.cit.gvsig.graph.GraphException; |
53 |
import com.iver.cit.gvsig.graph.core.AbstractNetSolver; |
54 |
import com.iver.cit.gvsig.graph.core.GvEdge; |
55 |
import com.iver.cit.gvsig.graph.core.GvFlag; |
56 |
import com.iver.cit.gvsig.graph.core.GvNode; |
57 |
import com.iver.cit.gvsig.graph.core.GvTurn; |
58 |
import com.iver.cit.gvsig.graph.core.IGraph; |
59 |
import com.vividsolutions.jts.geom.Coordinate; |
60 |
import com.vividsolutions.jts.geom.Geometry; |
61 |
import com.vividsolutions.jts.geom.GeometryFactory; |
62 |
import com.vividsolutions.jts.geom.LineString; |
63 |
import com.vividsolutions.jts.geom.MultiLineString; |
64 |
|
65 |
/**
|
66 |
* @author fjp
|
67 |
* Este es ?til solo cuando podemos calcular la distancia estimada entre
|
68 |
* 2 nodos. (Es decir, para temas de cartograf?a). Para analizar relaciones
|
69 |
* creo que no servir?a).
|
70 |
*/
|
71 |
public class ShortestPathSolverAStar extends AbstractNetSolver { |
72 |
|
73 |
private GeometryFactory geomFactory = new GeometryFactory(); |
74 |
|
75 |
protected Route route = new Route(); |
76 |
private int fieldIndexStreetName; |
77 |
|
78 |
private class InfoShp { |
79 |
public int idArc; |
80 |
public double pct; |
81 |
public double cost; |
82 |
public double distance; |
83 |
public int direction; |
84 |
public boolean bFlip; |
85 |
|
86 |
} |
87 |
|
88 |
public void setFielStreetName(String name) { |
89 |
try {
|
90 |
int aux = net.getLayer().getRecordset().getFieldIndexByName(name);
|
91 |
if (aux == -1) |
92 |
throw new RuntimeException("Field " + name + " not found."); |
93 |
fieldIndexStreetName = aux; |
94 |
} catch (com.hardcode.gdbms.engine.data.driver.DriverException e) {
|
95 |
// TODO Auto-generated catch block
|
96 |
e.printStackTrace(); |
97 |
} catch (DriverException e) {
|
98 |
// TODO Auto-generated catch block
|
99 |
e.printStackTrace(); |
100 |
} |
101 |
|
102 |
} |
103 |
|
104 |
/**
|
105 |
* @return a list of features
|
106 |
* @throws GraphException
|
107 |
*/
|
108 |
public Route calculateRoute() throws GraphException { |
109 |
GvFlag[] flags = net.getFlags();
|
110 |
if (flags.length == 0) |
111 |
throw new RuntimeException("Please, add flags before"); |
112 |
int desde = 0; |
113 |
int hasta = 1; |
114 |
double elCoste1 = 0; |
115 |
route = new Route();
|
116 |
GvFlag fFrom = flags[0];
|
117 |
fFrom.setCost(0);
|
118 |
for (int i = 0; i < flags.length - 1; i++) { |
119 |
fFrom = flags[desde]; |
120 |
GvFlag fTo = flags[hasta]; |
121 |
|
122 |
if (fFrom != fTo) {
|
123 |
int idStart = net.creaArcosVirtuales(fFrom);
|
124 |
int idStop = net.creaArcosVirtuales(fTo);
|
125 |
|
126 |
double newCost = AStar(idStart, idStop);
|
127 |
|
128 |
elCoste1 += newCost; |
129 |
fTo.setCost(elCoste1); |
130 |
|
131 |
if (newCost != Double.MAX_VALUE) |
132 |
{ |
133 |
try {
|
134 |
populateRoute(fFrom, fTo, idStart, idStop); |
135 |
} catch (DriverException e) {
|
136 |
e.printStackTrace(); |
137 |
throw new GraphException(e); |
138 |
} |
139 |
} |
140 |
else
|
141 |
{ |
142 |
// No way
|
143 |
} |
144 |
|
145 |
net.reconstruyeTramo(fFrom.getIdArc()); |
146 |
net.reconstruyeTramo(fTo.getIdArc()); |
147 |
desde = hasta; |
148 |
} // if son puntos distintos
|
149 |
hasta++; |
150 |
} |
151 |
|
152 |
return route;
|
153 |
} |
154 |
|
155 |
private void populateRouteSimple(int idStart, int idEnd) throws DriverException { |
156 |
int idEnlace;
|
157 |
GvNode node; |
158 |
GvEdge link; |
159 |
double costeEntrada;
|
160 |
|
161 |
// Trazar el camino desde idEnd hasta idStart hacia atr?s marcando los Enlaces
|
162 |
double Coste = 0; |
163 |
double Coste2 = 0; |
164 |
IGraph graph = net.getGraph(); |
165 |
node = graph.getNodeByID(idEnd); |
166 |
int from_link = node.getFromLink();
|
167 |
VectorialAdapter va = (VectorialAdapter) net.getLayer().getSource(); |
168 |
while (node.getIdNode() != idStart)
|
169 |
{ |
170 |
if (from_link == -1) |
171 |
{ |
172 |
throw new RuntimeException("Fallo al recorrer de manera inversa la soluci?n. Encontrado arco con -1"); |
173 |
// break; // FALLO!!
|
174 |
} |
175 |
link = graph.getEdgeByID(from_link); |
176 |
IFeature feat = va.getFeature(link.getIdArc()); |
177 |
route.addRouteFeature(feat.getGeometry(), link.getIdArc(), |
178 |
link.getWeight(), link.getDistance(), feat.getAttribute(getFieldIndexStreetName()).toString()); |
179 |
|
180 |
node = graph.getNodeByID(link.getIdNodeOrig()); |
181 |
|
182 |
Coste = Coste + link.getWeight(); |
183 |
Coste2 = Coste2 + link.getDistance(); |
184 |
|
185 |
// TODO:
|
186 |
// from_link = node.get_from_link(idEnlace, &costeEntrada);
|
187 |
from_link = node.getFromLink(); |
188 |
|
189 |
} |
190 |
System.out.println("Salgo con node = " + node.getIdNode()); |
191 |
} |
192 |
|
193 |
private void populateRoute(GvFlag origin, GvFlag dest, int idStart, int idEnd) throws DriverException { |
194 |
int idEnlace;
|
195 |
GvNode node; |
196 |
GvEdge link; |
197 |
double costeEntrada;
|
198 |
|
199 |
// Trazar el camino desde idEnd hasta idStart hacia atr?s marcando los Enlaces
|
200 |
|
201 |
if (idStart == idEnd)
|
202 |
return;
|
203 |
IGraph graph = net.getGraph(); |
204 |
node = graph.getNodeByID(idEnd); |
205 |
int from_link = node.getFromLink();
|
206 |
VectorialAdapter va = (VectorialAdapter) net.getLayer().getSource(); |
207 |
try {
|
208 |
va.start(); |
209 |
/* Miramos los nodos de los tramos inicio y final, y cogemos el nodo que tenga el from_link rellenado. E IGUAL A NUMSOLUCGLOBAL!!!!
|
210 |
A partir de ah?, recorremos hacia atr?s y tenemos el cuerpo principal del shape. Luego, para
|
211 |
las puntas hay que tener en cuenta los porcentajes, viendo el trozo que est? pegando a los nodos
|
212 |
que sabemos que est?n en el path
|
213 |
*/
|
214 |
|
215 |
/* 22/9/2003 Corregimos el fallo que hab?a de escribir el shape de atr?s adelante.
|
216 |
* Guardamos lo que necesitamos en listaShapes y recorremos esa lista guardando los tramos
|
217 |
* con el sentido adecuado.
|
218 |
*/
|
219 |
|
220 |
/* 3/Febrero/2005 Limpieza de c?digo superfluo y correci?n de un fallo raro. Ahora es m?s simple y parece
|
221 |
* que no falla. A ver si dura. IDEA: quiz?s se necesite meter el porcentaje en los arcos partidos.
|
222 |
*/
|
223 |
|
224 |
// Define a template class for a vector of IDs.
|
225 |
InfoShp infoShp; |
226 |
Stack pilaShapes = new Stack(); |
227 |
// typedef stack<CInfoShp> PILAINFO;
|
228 |
// PILAINFO pilaShapes;
|
229 |
|
230 |
double costeTramoFinal=-1; |
231 |
GvNode nodeEnd = graph.getNodeByID(idEnd); |
232 |
GvEdge finalEdge = graph.getEdgeByID(nodeEnd.getFromLink()); |
233 |
costeTramoFinal = finalEdge.getWeight(); |
234 |
|
235 |
GvNode pNodo; |
236 |
GvEdge pEnlace; |
237 |
|
238 |
boolean bFlipearShape = false; |
239 |
|
240 |
double pctMax, pctMin;
|
241 |
|
242 |
|
243 |
|
244 |
//////////////////////////////////////////////////////////////////////////////////////
|
245 |
// Trozo del final
|
246 |
// El shape va de idStop1 a idStop2, y el porcentaje viene en ese sentido.
|
247 |
// Si el idEnd es idStop1, quiere decir que el tramo que falta va en ese sentido tambi?n,
|
248 |
// as? que recorremos ese shape desde idStop1 hasta que rebasemos o igualemos ese porcentaje.
|
249 |
// Si no, hemos pasado por idStop2 y la parte que hay que meter es desde el pto interior a idStop2
|
250 |
///////////////////////////////////////////////////////////////////////////////////////
|
251 |
IFeature feat = va.getFeature(finalEdge.getIdArc()); |
252 |
MultiLineString jtsGeom = (MultiLineString) feat.getGeometry().toJTSGeometry(); |
253 |
// CoordinateFilter removeDuplicates = new UniqueCoordinateArrayFilter();
|
254 |
// jtsGeom.apply(removeDuplicates);
|
255 |
// jtsGeom.geometryChanged();
|
256 |
|
257 |
|
258 |
|
259 |
// SI ESTAMOS SOBRE EL MISMO TRAMO, CASO PARTICULAR
|
260 |
// y el sentido de circulaci?n es correcto
|
261 |
if ((origin.getIdArc() == dest.getIdArc()) && (nodeEnd.getBestCost() <= costeTramoFinal))
|
262 |
{ |
263 |
if (dest.getPct() > origin.getPct())
|
264 |
{ |
265 |
pctMax = dest.getPct(); |
266 |
pctMin = origin.getPct(); |
267 |
} |
268 |
else
|
269 |
{ |
270 |
pctMax = origin.getPct(); |
271 |
pctMin = dest.getPct(); |
272 |
bFlipearShape = true;
|
273 |
} |
274 |
|
275 |
LineString line = SituaSobreTramo(jtsGeom,dest.getIdArc(), dest.getPct(),1);
|
276 |
|
277 |
pctMin = pctMin / pctMax; // Porque ha cambiado la longitud del shape
|
278 |
|
279 |
line = SituaSobreTramo(line,dest.getIdArc(), pctMin,0);
|
280 |
|
281 |
if (bFlipearShape)
|
282 |
line = line.reverse(); |
283 |
|
284 |
IGeometry geom = FConverter.jts_to_igeometry(line); |
285 |
// TODO: Calcular bien el length de este arco,
|
286 |
// basandonos en el porcentaje costeTramoFinal / costeOriginal
|
287 |
route.addRouteFeature(geom, origin.getIdArc(), |
288 |
costeTramoFinal, line.getLength(), feat.getAttribute(getFieldIndexStreetName()).toString()); |
289 |
|
290 |
|
291 |
return ; // Deber?a sacar el coste |
292 |
} |
293 |
|
294 |
|
295 |
|
296 |
// Trazar el camino desde idEnd hasta idStart hacia atr?s marcando los Enlaces
|
297 |
pNodo = graph.getNodeByID(idEnd); |
298 |
|
299 |
while ((pNodo.getIdNode() != idStart))
|
300 |
{ |
301 |
idEnlace = pNodo.getFromLink(); |
302 |
pEnlace = graph.getEdgeByID(idEnlace); |
303 |
|
304 |
pNodo = graph.getNodeByID(pEnlace.getIdNodeOrig()); |
305 |
|
306 |
infoShp = new InfoShp();
|
307 |
infoShp.distance = pEnlace.getDistance(); |
308 |
infoShp.cost = pEnlace.getWeight(); |
309 |
|
310 |
if ((pEnlace.getIdArc() == origin.getIdArc()) || (pEnlace.getIdArc() == dest.getIdArc()))
|
311 |
{ |
312 |
if (pEnlace.getIdArc() == origin.getIdArc())
|
313 |
{ |
314 |
infoShp.pct = origin.getPct(); |
315 |
infoShp.idArc = origin.getIdArc(); |
316 |
if (pEnlace.getDirec() == 0) |
317 |
{ |
318 |
infoShp.direction = 1;
|
319 |
infoShp.bFlip = true;
|
320 |
} |
321 |
else // Hemos pasado por el 2 |
322 |
{ |
323 |
infoShp.direction = 0;
|
324 |
infoShp.bFlip = false;
|
325 |
} // if else */
|
326 |
} |
327 |
else
|
328 |
{ |
329 |
infoShp.pct = dest.getPct(); |
330 |
infoShp.idArc = dest.getIdArc(); |
331 |
if (pEnlace.getDirec() == 0) |
332 |
{ |
333 |
infoShp.direction = 0;
|
334 |
infoShp.bFlip = true;
|
335 |
} |
336 |
else
|
337 |
{ |
338 |
infoShp.direction = 1;
|
339 |
infoShp.bFlip = false;
|
340 |
} // if else */
|
341 |
} |
342 |
} |
343 |
else
|
344 |
{ |
345 |
infoShp.pct = 1.0;
|
346 |
infoShp.idArc = pEnlace.getIdArc(); |
347 |
|
348 |
infoShp.direction =1;
|
349 |
if (pEnlace.getDirec() == 1) |
350 |
infoShp.bFlip = false;
|
351 |
else
|
352 |
infoShp.bFlip = true;
|
353 |
} |
354 |
|
355 |
pilaShapes.push(infoShp); |
356 |
} |
357 |
|
358 |
// Y ahora recorremos hacia atr?s el vector y escribimos los shapes.
|
359 |
// VECTORINFO::iterator theIterator;
|
360 |
int auxC = 0; |
361 |
|
362 |
while (!pilaShapes.empty())
|
363 |
{ |
364 |
infoShp = (InfoShp) pilaShapes.peek(); |
365 |
feat = va.getFeature(infoShp.idArc); |
366 |
MultiLineString line = (MultiLineString) feat.getGeometry().toJTSGeometry(); |
367 |
// line.apply(removeDuplicates);
|
368 |
// line.geometryChanged();
|
369 |
|
370 |
LineString aux = null;
|
371 |
if (infoShp.pct < 1.0) |
372 |
aux = SituaSobreTramo(line,infoShp.idArc, infoShp.pct, infoShp.direction); |
373 |
|
374 |
IGeometry geom = null;
|
375 |
if (aux == null) |
376 |
{ |
377 |
if (infoShp.bFlip)
|
378 |
line = line.reverse(); |
379 |
geom = FConverter.jts_to_igeometry(line); |
380 |
} |
381 |
else
|
382 |
{ |
383 |
if (infoShp.bFlip)
|
384 |
aux = aux.reverse(); |
385 |
geom = FConverter.jts_to_igeometry(aux); |
386 |
} |
387 |
|
388 |
|
389 |
route.addRouteFeature(geom, infoShp.idArc, |
390 |
infoShp.cost, infoShp.distance, feat.getAttribute(getFieldIndexStreetName()).toString()); |
391 |
|
392 |
|
393 |
pilaShapes.pop(); |
394 |
auxC++; |
395 |
|
396 |
} |
397 |
va.stop(); |
398 |
} catch (DriverIOException e) {
|
399 |
// TODO Auto-generated catch block
|
400 |
e.printStackTrace(); |
401 |
} |
402 |
|
403 |
return;
|
404 |
|
405 |
|
406 |
} |
407 |
|
408 |
LineString SituaSobreTramo(Geometry geom, int idArc, double pct, int parte) |
409 |
// Si parte vale cero, los v?lidos son los primeros. Si no, los segundos.
|
410 |
{ |
411 |
int j, numVertices;
|
412 |
double longAcum, longReal, longBuscada, distSobre, miniPorcentaje;
|
413 |
double nuevaX, nuevaY; // Por cuestiones de claridad al programar |
414 |
double dist=0; |
415 |
|
416 |
longAcum = 0;
|
417 |
longReal = geom.getLength(); |
418 |
longBuscada = longReal * pct; |
419 |
Coordinate[] coords = geom.getCoordinates();
|
420 |
Coordinate c1 = null, c2 = null; |
421 |
ArrayList savedCoords = new ArrayList(); |
422 |
|
423 |
if (parte > 0) // Hemos entrado por el 1 hacia el 2 (al 2 no llegamos) |
424 |
{ |
425 |
for( j = 0; j < coords.length-1; j++ ) |
426 |
{ |
427 |
c1 = coords[j]; |
428 |
c2 = coords[j+1];
|
429 |
dist = c1.distance(c2); |
430 |
longAcum += dist; |
431 |
savedCoords.add(c1); |
432 |
if (longAcum >= longBuscada)
|
433 |
{ |
434 |
// Hasta aqu?. Ahora ahi que poner el punto sobre el tramo
|
435 |
distSobre = dist - (longAcum - longBuscada); |
436 |
miniPorcentaje = distSobre/dist; |
437 |
|
438 |
nuevaX = c1.x + (c2.x-c1.x) * miniPorcentaje; |
439 |
nuevaY = c1.y + (c2.y-c1.y) * miniPorcentaje; |
440 |
|
441 |
savedCoords.add(new Coordinate(nuevaX, nuevaY));
|
442 |
break;
|
443 |
} // if longAcum >= longBuscada
|
444 |
} // for j
|
445 |
|
446 |
} |
447 |
else // Hemos entrado por el 2 hacia el 1 |
448 |
{ |
449 |
numVertices = 0;
|
450 |
for( j = 0; j < coords.length; j++ ) |
451 |
{ |
452 |
////////////////////////////////////////////////////////////////
|
453 |
// 13_ene_2005: Si el ?ltimo punto es el ?ltimo punto no
|
454 |
// podemos acceder al elemento j+1 porque nos salimos del shape
|
455 |
/////////////////////////////////////////////////////////////////
|
456 |
c1 = coords[j]; |
457 |
if (j < coords.length -1) |
458 |
{ |
459 |
c2 = coords[j+1];
|
460 |
|
461 |
dist = c1.distance(c2); |
462 |
longAcum += dist; |
463 |
} |
464 |
|
465 |
if (longAcum >= longBuscada)
|
466 |
{ |
467 |
// Hasta aqu?. Empezamos a meter puntos
|
468 |
|
469 |
if (numVertices == 0) |
470 |
{ |
471 |
distSobre = dist - (longAcum - longBuscada); |
472 |
miniPorcentaje = distSobre/dist; |
473 |
nuevaX = c1.x + (c2.x-c1.x) * miniPorcentaje; |
474 |
nuevaY = c1.y + (c2.y-c1.y) * miniPorcentaje; |
475 |
|
476 |
savedCoords.add(new Coordinate(nuevaX, nuevaY));
|
477 |
} |
478 |
else
|
479 |
{ |
480 |
savedCoords.add(c2); |
481 |
} |
482 |
numVertices ++; |
483 |
// break;
|
484 |
} // if longAcum >= longBuscada
|
485 |
} // for j
|
486 |
|
487 |
// savedCoords.add(c2);
|
488 |
|
489 |
} // if else
|
490 |
|
491 |
|
492 |
return geomFactory.createLineString((Coordinate[] )savedCoords.toArray(new Coordinate[0])); |
493 |
} |
494 |
|
495 |
private int getFieldIndexStreetName() { |
496 |
return fieldIndexStreetName;
|
497 |
} |
498 |
|
499 |
private double AStar(int idStart, int idStop) { |
500 |
int nodeNum;
|
501 |
int linkNum;
|
502 |
double newCost;
|
503 |
int idSiguienteNodo;
|
504 |
GvNode node, toNode, finalNode, bestNode; // , *pNodoProv;
|
505 |
GvEdge link; |
506 |
boolean bExit = false; |
507 |
|
508 |
boolean bGiroProhibido;
|
509 |
ArrayList candidatos = new ArrayList(); |
510 |
|
511 |
// char Mensaje[200];
|
512 |
|
513 |
IGraph graph = net.getGraph(); |
514 |
|
515 |
// NUEVO: 27-6-2003
|
516 |
// Cada nodo y cada arco llevan un nuemero de soluci?n. Se supone
|
517 |
// que si lo del nodo y el arco no coincide con
|
518 |
// este numero, todav?a no ha sido inicializado y hay que hacerlo.
|
519 |
// Para evitar coincidencias cuando de la vuelta el contador, cada
|
520 |
// 65000 peticiones (por ejemplo), repasamos toda
|
521 |
// la red y ponemos numSolucGlobal a -1
|
522 |
if (numSolucGlobal > 65000) { |
523 |
numSolucGlobal = -1;
|
524 |
|
525 |
for (nodeNum = 0; nodeNum < graph.numVertices(); nodeNum++) { |
526 |
node = graph.getNodeByID(nodeNum); |
527 |
node.initialize(); |
528 |
} // for nodeNum */
|
529 |
|
530 |
} |
531 |
numSolucGlobal++; |
532 |
|
533 |
candidatos.clear(); |
534 |
// A?adimos el Start Node a la lista de candidatosSTL
|
535 |
// Nodo final
|
536 |
finalNode = graph.getNodeByID(idStop); |
537 |
finalNode.initialize(); |
538 |
|
539 |
node = graph.getNodeByID(idStart); |
540 |
node.initialize(); |
541 |
bestNode = node; |
542 |
|
543 |
candidatos.add(node); |
544 |
node.setBestCost(0);
|
545 |
node.setStatus(GvNode.statNowInList); |
546 |
node.calculateStimation(finalNode, 0);
|
547 |
|
548 |
// Mientras que la lista de candidatosSTL no est? vac?a, procesamos
|
549 |
// Nodos
|
550 |
double bestStimation;
|
551 |
|
552 |
while ((!bExit) && (candidatos.size() > 0)) { |
553 |
// Buscamos el nodo con m?nimo coste
|
554 |
node = (GvNode) candidatos.get(0);
|
555 |
bestNode = node; |
556 |
bestStimation = node.getStimation(); |
557 |
for (nodeNum = 1; nodeNum < candidatos.size(); nodeNum++) { |
558 |
node = (GvNode) candidatos.get(nodeNum); |
559 |
if (node.getStimation() < bestStimation) {
|
560 |
bestStimation = node.getStimation(); |
561 |
bestNode = node; |
562 |
} |
563 |
} // for nodeNum candidatosSTL
|
564 |
|
565 |
node = bestNode; |
566 |
// Borramos el mejor nodo de la lista de candidatosSTL
|
567 |
node.setStatus(GvNode.statWasInList); |
568 |
// TODO: BORRAR POR INDEX, NO AS?. ES M?S LENTO QUE SI BORRAMOS EL i-?simo.
|
569 |
candidatos.remove(node); |
570 |
// System.out.println("LINK " + link.getIdArc() + " from ");
|
571 |
// System.out.println("from " + idStart + " to " + finalNode.getIdNode() + ". node=" + node.getIdNode());
|
572 |
// Miramos si hemos llegado donde quer?amos
|
573 |
if (bestNode.getIdNode() == idStop) {
|
574 |
bExit = true;
|
575 |
break;
|
576 |
} |
577 |
|
578 |
// sprintf(Mensaje,"Enlaces en el nodo %ld:
|
579 |
// %ld.",pNodo->idNodo,pNodo->Enlaces.GetSize());
|
580 |
// AfxMessageBox(Mensaje);
|
581 |
|
582 |
// A?adimos a la lista de candidatosSTL los vecinos del nodo que
|
583 |
// acabamos de borrar
|
584 |
// HAY Arcos QUE SALEN Y Arcos QUE LLEGAN. SOLO MIRAMOS LOS QUE
|
585 |
// SALEN.
|
586 |
for (linkNum = 0; linkNum < node.getEnlaces().size(); linkNum++) { |
587 |
// Pillamos el nodo vecino
|
588 |
link = (GvEdge) node.getEnlaces().get(linkNum); |
589 |
idSiguienteNodo = link.getIdNodeEnd(); |
590 |
|
591 |
toNode = graph.getNodeByID(idSiguienteNodo); |
592 |
|
593 |
// 27_5_2004
|
594 |
// Si un arco tiene coste negativo, lo ignoramos
|
595 |
if (link.getWeight() < 0) |
596 |
continue;
|
597 |
|
598 |
// Fin arco con coste negativo
|
599 |
|
600 |
// NUEVO: 26-7-2003: Comprobamos si est? inicializado
|
601 |
if (toNode.getNumSoluc() != numSolucGlobal) {
|
602 |
toNode.initialize(); |
603 |
} |
604 |
else
|
605 |
{ |
606 |
// System.out.println("Nodo ya inicializado");
|
607 |
} |
608 |
|
609 |
// Miramos a ver si podemos mejorar su best_cost
|
610 |
newCost = node.getBestCost() + link.getWeight(); |
611 |
|
612 |
if (newCost < toNode.getBestCost()) {
|
613 |
// Es una mejora, as? que actualizamos el vecino y
|
614 |
// lo a?adimos a los candidatosSTL
|
615 |
toNode.setBestCost(newCost); |
616 |
toNode.setFromLink(link.getIdEdge()); |
617 |
|
618 |
toNode.calculateStimation(finalNode, newCost); |
619 |
|
620 |
if (toNode.getStatus() != GvNode.statNowInList) {
|
621 |
toNode.setStatus(GvNode.statNowInList); |
622 |
candidatos.add(toNode); |
623 |
} |
624 |
} // Si hay mejora
|
625 |
|
626 |
} // for linkNum
|
627 |
} // while candidatosSTL
|
628 |
|
629 |
newCost = finalNode.getBestCost(); |
630 |
|
631 |
return newCost;
|
632 |
} |
633 |
|
634 |
} |