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