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