svn-gvsig-desktop / tags / v1_1_2_Build_1044 / prototypes / VectorialAvanzado / extensions / extGraph / src / com / iver / cit / gvsig / graph / solvers / OneToManySolver.java @ 20099
History | View | Annotate | Download (11.2 KB)
1 | 11631 | fjp | /* 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 | |||
45 | import com.iver.cit.gvsig.graph.core.AbstractNetSolver; |
||
46 | 20099 | fpenarrubia | import com.iver.cit.gvsig.graph.core.GraphException; |
47 | 11631 | fjp | import com.iver.cit.gvsig.graph.core.GvEdge; |
48 | import com.iver.cit.gvsig.graph.core.GvFlag; |
||
49 | import com.iver.cit.gvsig.graph.core.GvNode; |
||
50 | import com.iver.cit.gvsig.graph.core.IGraph; |
||
51 | |||
52 | public class OneToManySolver extends AbstractNetSolver { |
||
53 | 12157 | fjp | |
54 | private int idStart = -1; |
||
55 | private ArrayList idStops = null; |
||
56 | 11631 | fjp | |
57 | private class StopAux { |
||
58 | public StopAux(Integer idStop2) { |
||
59 | idStop = idStop2; |
||
60 | bFound = false;
|
||
61 | } |
||
62 | private Integer idStop; |
||
63 | private boolean bFound; |
||
64 | public boolean isFound() { |
||
65 | return bFound;
|
||
66 | } |
||
67 | public void setFound(boolean found) { |
||
68 | bFound = found; |
||
69 | } |
||
70 | public Integer getIdStop() { |
||
71 | return idStop;
|
||
72 | } |
||
73 | } |
||
74 | |||
75 | private GvFlag sourceFlag;
|
||
76 | 12926 | fjp | private boolean bExploreAll = false; // by default |
77 | 11631 | fjp | |
78 | |||
79 | 12157 | fjp | |
80 | 11631 | fjp | /**
|
81 | 12157 | fjp | * We have this method separated from calculate to speed up odmatrix calculations.
|
82 | * The developer can position flags once, and call calculate only changing source
|
||
83 | * (idStart). This way, destination flags are positionned only once.
|
||
84 | * @throws GraphException
|
||
85 | 11631 | fjp | */
|
86 | 12157 | fjp | public void putDestinationsOnNetwork() throws GraphException |
87 | { |
||
88 | 11631 | fjp | GvFlag[] flags = net.getFlags(); // Destinations |
89 | |||
90 | if (flags.length == 0) |
||
91 | throw new RuntimeException("Please, add flags before"); |
||
92 | 12157 | fjp | |
93 | idStops = new ArrayList(); |
||
94 | 11631 | fjp | for (int i = 0; i < flags.length; i++) { |
95 | GvFlag fTo = flags[i]; |
||
96 | |||
97 | int idStop = net.creaArcosVirtuales(fTo);
|
||
98 | idStops.add(new Integer(idStop)); |
||
99 | } |
||
100 | 12157 | fjp | |
101 | } |
||
102 | public void removeDestinationsFromNetwork() |
||
103 | { |
||
104 | GvFlag[] flags = net.getFlags(); // Destinations |
||
105 | for (int i = 0; i < flags.length; i++) |
||
106 | { |
||
107 | GvFlag fTo = flags[i]; |
||
108 | net.reconstruyeTramo(fTo.getIdArc()); |
||
109 | } |
||
110 | |||
111 | } |
||
112 | /**
|
||
113 | * @throws GraphException
|
||
114 | */
|
||
115 | public void calculate() throws GraphException { |
||
116 | if (idStops == null) |
||
117 | { |
||
118 | throw new RuntimeException("Please, call putDestinationsOnNetwork before calculate()"); |
||
119 | } |
||
120 | GvFlag[] flags = net.getFlags(); // Destinations |
||
121 | idStart = net.creaArcosVirtuales(sourceFlag); |
||
122 | 11631 | fjp | dijkstra(idStart, idStops); |
123 | 12157 | fjp | |
124 | IGraph graph = net.getGraph(); |
||
125 | 11631 | fjp | for (int i = 0; i < flags.length; i++) |
126 | { |
||
127 | GvFlag fTo = flags[i]; |
||
128 | Integer auxId = (Integer) idStops.get(i); |
||
129 | GvNode auxNode = graph.getNodeByID(auxId.intValue()); |
||
130 | // System.out.println("Asigno bestCost = " + auxNode.getBestCost());
|
||
131 | 12157 | fjp | if (auxNode.getBestCost() == Double.MAX_VALUE) |
132 | { |
||
133 | fTo.setCost(-1);
|
||
134 | fTo.setAccumulatedLength(-1);
|
||
135 | } |
||
136 | else
|
||
137 | { |
||
138 | fTo.setCost(auxNode.getBestCost()); |
||
139 | fTo.setAccumulatedLength(auxNode.getAccumulatedLength()); |
||
140 | } |
||
141 | 11631 | fjp | } |
142 | |||
143 | 12157 | fjp | // TODO: No podemos reconstruir el tramo porque perdemos la conectividad
|
144 | // con el resto de destinos.
|
||
145 | // net.reconstruyeTramo(sourceFlag.getIdArc());
|
||
146 | 11631 | fjp | } |
147 | |||
148 | |||
149 | private void dijkstra(int idStart, ArrayList stops) { |
||
150 | int nodeNum;
|
||
151 | int linkNum;
|
||
152 | double newCost;
|
||
153 | int idSiguienteNodo;
|
||
154 | GvNode node, toNode, bestNode; // , *pNodoProv;
|
||
155 | GvEdge link; |
||
156 | boolean bExit = false; |
||
157 | double bestCost;
|
||
158 | |||
159 | boolean bGiroProhibido;
|
||
160 | // List clonedStops = Collections.synchronizedList(stops);
|
||
161 | ArrayList clonedStops = new ArrayList(); |
||
162 | for (int i=0; i < stops.size(); i++) |
||
163 | { |
||
164 | Integer idStop = (Integer) stops.get(i); |
||
165 | clonedStops.add(new StopAux(idStop));
|
||
166 | } |
||
167 | ArrayList candidatos = new ArrayList(); |
||
168 | |||
169 | // GvTurn elGiro;
|
||
170 | // char Mensaje[200];
|
||
171 | |||
172 | IGraph graph = net.getGraph(); |
||
173 | |||
174 | // NUEVO: 27-6-2003
|
||
175 | // Cada nodo y cada arco llevan un nuemero de soluci?n. Se supone
|
||
176 | // que si lo del nodo y el arco no coincide con
|
||
177 | // este numero, todav?a no ha sido inicializado y hay que hacerlo.
|
||
178 | // Para evitar coincidencias cuando de la vuelta el contador, cada
|
||
179 | // 65000 peticiones (por ejemplo), repasamos toda
|
||
180 | // la red y ponemos numSolucGlobal a -1
|
||
181 | if (numSolucGlobal > 65000) { |
||
182 | numSolucGlobal = -1;
|
||
183 | |||
184 | for (nodeNum = 0; nodeNum < graph.numVertices(); nodeNum++) { |
||
185 | node = graph.getNodeByID(nodeNum); |
||
186 | node.initialize(); |
||
187 | } // for nodeNum */
|
||
188 | |||
189 | } |
||
190 | numSolucGlobal++; |
||
191 | |||
192 | candidatos.clear(); |
||
193 | // A?adimos el Start Node a la lista de candidatosSTL
|
||
194 | // Nodos finales
|
||
195 | for (int h=0; h < clonedStops.size(); h++) |
||
196 | { |
||
197 | StopAux auxStop = (StopAux) clonedStops.get(h); |
||
198 | int idStop = auxStop.getIdStop().intValue();
|
||
199 | |||
200 | GvNode auxNode = graph.getNodeByID(idStop); |
||
201 | auxNode.initialize(); |
||
202 | } |
||
203 | node = graph.getNodeByID(idStart); |
||
204 | node.initialize(); |
||
205 | bestNode = node; |
||
206 | |||
207 | candidatos.add(node); |
||
208 | node.setBestCost(0);
|
||
209 | node.setStatus(GvNode.statNowInList); |
||
210 | bestCost = Double.MAX_VALUE;
|
||
211 | |||
212 | // Mientras que la lista de candidatosSTL no est? vac?a, procesamos
|
||
213 | // Nodos
|
||
214 | int stopActual = 0; |
||
215 | |||
216 | while ((!bExit) && (candidatos.size() > 0)) { |
||
217 | // Buscamos el nodo con m?nimo coste
|
||
218 | node = (GvNode) candidatos.get(0);
|
||
219 | bestNode = node; |
||
220 | bestCost = node.getBestCost(); |
||
221 | for (nodeNum = 1; nodeNum < candidatos.size(); nodeNum++) { |
||
222 | node = (GvNode) candidatos.get(nodeNum); |
||
223 | if (node.getBestCost() < bestCost) {
|
||
224 | bestCost = node.getBestCost(); |
||
225 | bestNode = node; |
||
226 | } |
||
227 | } // for nodeNum candidatosSTL
|
||
228 | |||
229 | node = bestNode; |
||
230 | // Borramos el mejor nodo de la lista de candidatosSTL
|
||
231 | node.setStatus(GvNode.statWasInList); |
||
232 | // TODO: BORRAR POR INDEX, NO AS?. ES M?S LENTO QUE SI BORRAMOS EL i-?simo.
|
||
233 | candidatos.remove(node); |
||
234 | // System.out.println("LINK " + link.getIdArc() + " from ");
|
||
235 | // System.out.println("from " + idStart + " to " + finalNode.getIdNode() + ". node=" + node.getIdNode());
|
||
236 | 12926 | fjp | if (!bExploreAll)
|
237 | { |
||
238 | // Miramos si hemos llegado donde quer?amos
|
||
239 | StopAux auxStop = (StopAux) clonedStops.get(stopActual); |
||
240 | int idStop = auxStop.getIdStop().intValue();
|
||
241 | |||
242 | if (bestNode.getIdNode() == idStop) {
|
||
243 | // Hemos llegado a ese punto. Miramos el resto de puntos destino
|
||
244 | // a ver si ya hemos pasado por alguno de ellos.
|
||
245 | // Si con algun punto no pasamos por aqu?, no habremos llegado a ese punto.
|
||
246 | // No importa, puede que al resto s?, y esos nodos a los que s? hemos llegado
|
||
247 | // tendr?n bien rellenado el coste.
|
||
248 | auxStop.setFound(true);
|
||
249 | for (int i=stopActual; i < clonedStops.size(); i++) |
||
250 | 11631 | fjp | { |
251 | 12926 | fjp | auxStop = (StopAux) clonedStops.get(i); |
252 | if (!auxStop.isFound())
|
||
253 | 11631 | fjp | { |
254 | 12926 | fjp | Integer id = auxStop.getIdStop();
|
255 | |||
256 | GvNode auxNode = graph.getNodeByID(id.intValue()); |
||
257 | if (auxNode.getStatus() == GvNode.statWasInList)
|
||
258 | { |
||
259 | auxStop.setFound(true);
|
||
260 | } |
||
261 | else
|
||
262 | { |
||
263 | stopActual = i; |
||
264 | break;
|
||
265 | } |
||
266 | 11631 | fjp | } |
267 | 12926 | fjp | } |
268 | if (clonedStops.size() == 0) |
||
269 | { |
||
270 | bExit = true;
|
||
271 | break; // Ya hemos llegado a todos los nodos |
||
272 | } |
||
273 | } |
||
274 | } // if bExploreAll
|
||
275 | |||
276 | 11631 | fjp | // sprintf(Mensaje,"Enlaces en el nodo %ld:
|
277 | // %ld.",pNodo->idNodo,pNodo->Enlaces.GetSize());
|
||
278 | // AfxMessageBox(Mensaje);
|
||
279 | |||
280 | // A?adimos a la lista de candidatosSTL los vecinos del nodo que
|
||
281 | // acabamos de borrar
|
||
282 | // HAY Arcos QUE SALEN Y Arcos QUE LLEGAN. SOLO MIRAMOS LOS QUE
|
||
283 | // SALEN.
|
||
284 | for (linkNum = 0; linkNum < node.getEnlaces().size(); linkNum++) { |
||
285 | // Pillamos el nodo vecino
|
||
286 | link = (GvEdge) node.getEnlaces().get(linkNum); |
||
287 | idSiguienteNodo = link.getIdNodeEnd(); |
||
288 | |||
289 | toNode = graph.getNodeByID(idSiguienteNodo); |
||
290 | |||
291 | // 27_5_2004
|
||
292 | // Si un arco tiene coste negativo, lo ignoramos
|
||
293 | if (link.getWeight() < 0) |
||
294 | continue;
|
||
295 | |||
296 | // Fin arco con coste negativo
|
||
297 | |||
298 | // NUEVO: 26-7-2003: Comprobamos si est? inicializado
|
||
299 | if (toNode.getNumSoluc() != numSolucGlobal) {
|
||
300 | toNode.initialize(); |
||
301 | } |
||
302 | else
|
||
303 | { |
||
304 | // System.out.println("Nodo ya inicializado");
|
||
305 | } |
||
306 | |||
307 | // Miramos si ese nodo ya ha estado antes en la lista de
|
||
308 | // candidatos
|
||
309 | if (toNode.getStatus() != GvNode.statWasInList) {
|
||
310 | // Miramos a ver si podemos mejorar su best_cost
|
||
311 | newCost = node.getBestCost() + link.getWeight(); |
||
312 | |||
313 | |||
314 | // Miramos la lista de Giros de ese nodo
|
||
315 | bGiroProhibido = false;
|
||
316 | for (int idGiro = 0; idGiro < node.getTurns().size(); idGiro++) { |
||
317 | // Si est? prohibido, a por otro
|
||
318 | // elGiro = (GvTurn) node.getTurns().get(idGiro);
|
||
319 | // TODO: HABILITAR ESTO
|
||
320 | // if ((elGiro.idTramoOrigen ==
|
||
321 | // Arcos[pNodo->from_link].idTramo) &&
|
||
322 | // (elGiro.idTramoDestino == pEnlace->idTramo))
|
||
323 | // {
|
||
324 | // if (elGiro.cost < 0)
|
||
325 | // {
|
||
326 | // bGiroProhibido = true;
|
||
327 | // // No podemos inicializar por completo el nodo porque
|
||
328 | // entonces
|
||
329 | // // perdemos el fromLink (el arco desde donde hemos
|
||
330 | // llegado hasta
|
||
331 | // // este nodo, que es necesario para calcular los
|
||
332 | // costes y generar
|
||
333 | // // el shape recorriendo hacia atr?s el camino
|
||
334 | // realizado.
|
||
335 | // // Si hab?a m?s de un nodo con costes prohibidos,
|
||
336 | // cab?a la posibilidad
|
||
337 | // // de que perdieramos este enlace.
|
||
338 | //
|
||
339 | // // Para que pueda volver a entrar en c?lculos
|
||
340 | // pNodo->status = statNotInList;
|
||
341 | // pNodo->best_cost = INFINITO;
|
||
342 | //
|
||
343 | // }
|
||
344 | // else
|
||
345 | // newCost += elGiro.cost;
|
||
346 | // break; // Salimos del for porque ya hemos encontrado
|
||
347 | // el giro
|
||
348 | // }
|
||
349 | } |
||
350 | // Si est? prohibido, vamos a por otro enlace, PERO
|
||
351 | // MARCAMOS EL NODO
|
||
352 | // COMO NO VISITADO PARA QUE PUEDA VOLVER A ENTRAR EN LA
|
||
353 | // LISTA DE CANDIDATOS
|
||
354 | // SI VENIMOS POR OTRO LADO.
|
||
355 | if (bGiroProhibido) {
|
||
356 | continue;
|
||
357 | } |
||
358 | |||
359 | if (newCost < toNode.getBestCost()) {
|
||
360 | // Es una mejora, as? que actualizamos el vecino y
|
||
361 | // lo a?adimos a los candidatosSTL
|
||
362 | toNode.setBestCost(newCost); |
||
363 | double newLength = node.getAccumulatedLength() + link.getDistance();
|
||
364 | toNode.setAccumulatedLength(newLength); |
||
365 | toNode.setFromLink(link.getIdEdge()); |
||
366 | |||
367 | if (toNode.getStatus() != GvNode.statNowInList) {
|
||
368 | toNode.setStatus(GvNode.statNowInList); |
||
369 | candidatos.add(toNode); |
||
370 | } |
||
371 | } // Si hay mejora
|
||
372 | } // if ese nodo no ha estado en la lista de candidatosSTL
|
||
373 | |||
374 | } // for linkNum
|
||
375 | } // while candidatosSTL
|
||
376 | |||
377 | } |
||
378 | |||
379 | |||
380 | public GvFlag getSourceFlag() {
|
||
381 | return sourceFlag;
|
||
382 | } |
||
383 | |||
384 | |||
385 | public void setSourceFlag(GvFlag sourceFlag) { |
||
386 | this.sourceFlag = sourceFlag;
|
||
387 | 12157 | fjp | |
388 | 11631 | fjp | } |
389 | 12926 | fjp | public void setExploreAllNetwork(boolean b) { |
390 | bExploreAll = b; |
||
391 | } |
||
392 | 11631 | fjp | |
393 | } |