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