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