Application: gvSIG desktop

/* gvSIG. Sistema de Informaci?n Geogr?fica de la Generalitat Valenciana

 *

 * Copyright (C) 2004 IVER T.I. and Generalitat Valenciana.

 *

 * This program is free software; you can redistribute it and/or

 * modify it under the terms of the GNU General Public License

 * as published by the Free Software Foundation; either version 2

 * of the License, or (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307,USA.

 *

 * For more information, contact:

 *

 *  Generalitat Valenciana

 *   Conselleria d'Infraestructures i Transport

 *   Av. Blasco Ib??ez, 50

 *   46010 VALENCIA

 *   SPAIN

 *

 *      +34 963862235

 *   gvsig@gva.es

 *      www.gvsig.gva.es

 *

 *    or

 *

 *   IVER T.I. S.A

 *   Salamanca 50

 *   46005 Valencia

 *   Spain

 *

 *   +34 963163400

 *   dac@iver.es

 */

package com.iver.cit.gvsig.graph.solvers;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Iterator;

import java.util.List;

import com.iver.cit.gvsig.graph.GraphException;

import com.iver.cit.gvsig.graph.core.AbstractNetSolver;

import com.iver.cit.gvsig.graph.core.GvEdge;

import com.iver.cit.gvsig.graph.core.GvFlag;

import com.iver.cit.gvsig.graph.core.GvNode;

import com.iver.cit.gvsig.graph.core.IGraph;

public class OneToManySolver extends AbstractNetSolver {

        private class StopAux {

                public StopAux(Integer idStop2) {

                        idStop = idStop2;

                        bFound = false;

                }

                private Integer idStop;

                private boolean bFound;

                public boolean isFound() {

                        return bFound;

                }

                public void setFound(boolean found) {

                        bFound = found;

                }

                public Integer getIdStop() {

                        return idStop;

                }

        }

        private GvFlag sourceFlag;

        /**

         * @throws GraphException 

         */

        public void calculate() throws GraphException {

                IGraph graph = net.getGraph();

                GvFlag[] flags = net.getFlags(); // Destinations

                if (flags.length == 0)

                        throw new RuntimeException("Please, add flags before");

                int idStart = net.creaArcosVirtuales(sourceFlag);

                ArrayList idStops = new ArrayList();

                for (int i = 0; i < flags.length; i++) {

                        GvFlag fTo = flags[i];

                        int idStop = net.creaArcosVirtuales(fTo);

                        idStops.add(new Integer(idStop));

                }

                dijkstra(idStart, idStops);

                for (int i = 0; i < flags.length; i++)

                {

                        GvFlag fTo = flags[i];

                        Integer auxId = (Integer) idStops.get(i);

                        GvNode auxNode = graph.getNodeByID(auxId.intValue());

//                        System.out.println("Asigno bestCost = " + auxNode.getBestCost());

                        fTo.setCost(auxNode.getBestCost());

                        fTo.setAccumulatedLength(auxNode.getAccumulatedLength());

                }

                for (int i = 0; i < flags.length; i++)

                {

                        GvFlag fTo = flags[i];

                        net.reconstruyeTramo(fTo.getIdArc());                        

                }

                net.reconstruyeTramo(sourceFlag.getIdArc());

        }

        private void dijkstra(int idStart, ArrayList stops) {

                int nodeNum;

                int linkNum;

                double newCost;

                int idSiguienteNodo;

                GvNode node, toNode, bestNode; // , *pNodoProv;

                GvEdge link;

                boolean bExit = false;

                double bestCost;

                boolean bGiroProhibido;

                // List clonedStops = Collections.synchronizedList(stops);

                ArrayList clonedStops = new ArrayList();

                for (int i=0; i < stops.size(); i++)

                {

                        Integer idStop = (Integer) stops.get(i);

                        clonedStops.add(new StopAux(idStop));

                }

                ArrayList candidatos = new ArrayList();

//                GvTurn elGiro;

                // char Mensaje[200];

                IGraph graph = net.getGraph();

                // NUEVO: 27-6-2003

                // Cada nodo y cada arco llevan un nuemero de soluci?n. Se supone

                // que si lo del nodo y el arco no coincide con

                // este numero, todav?a no ha sido inicializado y hay que hacerlo.

                // Para evitar coincidencias cuando de la vuelta el contador, cada

                // 65000 peticiones (por ejemplo), repasamos toda

                // la red y ponemos numSolucGlobal a -1

                if (numSolucGlobal > 65000) {

                        numSolucGlobal = -1;

                        for (nodeNum = 0; nodeNum < graph.numVertices(); nodeNum++) {

                                node = graph.getNodeByID(nodeNum);

                                node.initialize();

                        } // for nodeNum */

                }

                numSolucGlobal++;

                candidatos.clear();

                // A?adimos el Start Node a la lista de candidatosSTL

                // Nodos finales

                for (int h=0; h < clonedStops.size(); h++)

                {

                        StopAux auxStop = (StopAux) clonedStops.get(h);

                        int idStop = auxStop.getIdStop().intValue();

                        GvNode auxNode = graph.getNodeByID(idStop);

                        auxNode.initialize();

                }

                node = graph.getNodeByID(idStart);

                node.initialize();

                bestNode = node;

                candidatos.add(node);

                node.setBestCost(0);

                node.setStatus(GvNode.statNowInList);

                bestCost = Double.MAX_VALUE;

                // Mientras que la lista de candidatosSTL no est? vac?a, procesamos

                // Nodos

                int stopActual = 0;

                while ((!bExit) && (candidatos.size() > 0)) {

                        // Buscamos el nodo con m?nimo coste

                        node = (GvNode) candidatos.get(0);

                        bestNode = node;

                        bestCost = node.getBestCost();

                        for (nodeNum = 1; nodeNum < candidatos.size(); nodeNum++) {

                                node = (GvNode) candidatos.get(nodeNum);

                                if (node.getBestCost() < bestCost) {

                                        bestCost = node.getBestCost();

                                        bestNode = node;

                                }

                        } // for nodeNum candidatosSTL

                        node = bestNode;

                        // Borramos el mejor nodo de la lista de candidatosSTL

                        node.setStatus(GvNode.statWasInList);

                        // TODO: BORRAR POR INDEX, NO AS?. ES M?S LENTO QUE SI BORRAMOS EL i-?simo.

                        candidatos.remove(node);

                        // System.out.println("LINK " + link.getIdArc() + " from ");

                        // System.out.println("from " + idStart + " to " + finalNode.getIdNode() + ". node=" + node.getIdNode());

                        // Miramos si hemos llegado donde quer?amos

                        StopAux auxStop = (StopAux) clonedStops.get(stopActual);

                        int idStop = auxStop.getIdStop().intValue();

                        if (bestNode.getIdNode() == idStop) {

                                // Hemos llegado a ese punto. Miramos el resto de puntos destino

                                // a ver si ya hemos pasado por alguno de ellos.

                                // Si con algun punto no pasamos por aqu?, no habremos llegado a ese punto.

                                // No importa, puede que al resto s?, y esos nodos a los que s? hemos llegado

                                // tendr?n bien rellenado el coste.

                                auxStop.setFound(true);

                                for (int i=stopActual; i < clonedStops.size(); i++)

                                {

                                        auxStop = (StopAux) clonedStops.get(i);

                                        if (!auxStop.isFound())

                                        {

                                                Integer id = auxStop.getIdStop();

                                                GvNode auxNode = graph.getNodeByID(id.intValue());

                                                if (auxNode.getStatus() == GvNode.statWasInList)

                                                {

                                                        auxStop.setFound(true);

                                                }

                                                else

                                                {

                                                        stopActual = i;

                                                        break;

                                                }

                                        }

                                }                                                

                                if (clonedStops.size() == 0)

                                {

                                        bExit = true;

                                        break; // Ya hemos llegado a todos los nodos

                                }                                

                        }

                        // sprintf(Mensaje,"Enlaces en el nodo %ld:

                        // %ld.",pNodo->idNodo,pNodo->Enlaces.GetSize());

                        // AfxMessageBox(Mensaje);

                        // A?adimos a la lista de candidatosSTL los vecinos del nodo que

                        // acabamos de borrar

                        // HAY Arcos QUE SALEN Y Arcos QUE LLEGAN. SOLO MIRAMOS LOS QUE

                        // SALEN.

                        for (linkNum = 0; linkNum < node.getEnlaces().size(); linkNum++) {

                                // Pillamos el nodo vecino

                                link = (GvEdge) node.getEnlaces().get(linkNum);

                                idSiguienteNodo = link.getIdNodeEnd();

                                toNode = graph.getNodeByID(idSiguienteNodo);

                                // 27_5_2004

                                // Si un arco tiene coste negativo, lo ignoramos

                                if (link.getWeight() < 0)

                                        continue;

                                // Fin arco con coste negativo

                                // NUEVO: 26-7-2003: Comprobamos si est? inicializado

                                if (toNode.getNumSoluc() != numSolucGlobal) {

                                        toNode.initialize();

                                }

                                else

                                {

                                        // System.out.println("Nodo ya inicializado");

                                }

                                // Miramos si ese nodo ya ha estado antes en la lista de

                                // candidatos

                                if (toNode.getStatus() != GvNode.statWasInList) {

                                        // Miramos a ver si podemos mejorar su best_cost

                                        newCost = node.getBestCost() + link.getWeight();

                                        // Miramos la lista de Giros de ese nodo

                                        bGiroProhibido = false;

                                        for (int idGiro = 0; idGiro < node.getTurns().size(); idGiro++) {

                                                // Si est? prohibido, a por otro

//                                                elGiro = (GvTurn) node.getTurns().get(idGiro);

                                                // TODO: HABILITAR ESTO

                                                // if ((elGiro.idTramoOrigen ==

                                                // Arcos[pNodo->from_link].idTramo) &&

                                                // (elGiro.idTramoDestino == pEnlace->idTramo))

                                                // {

                                                // if (elGiro.cost < 0)

                                                // {

                                                // bGiroProhibido = true;

                                                // // No podemos inicializar por completo el nodo porque

                                                // entonces

                                                // // perdemos el fromLink (el arco desde donde hemos

                                                // llegado hasta

                                                // // este nodo, que es necesario para calcular los

                                                // costes y generar

                                                // // el shape recorriendo hacia atr?s el camino

                                                // realizado.

                                                // // Si hab?a m?s de un nodo con costes prohibidos,

                                                // cab?a la posibilidad

                                                // // de que perdieramos este enlace.

                                                //                                                                        

                                                // // Para que pueda volver a entrar en c?lculos

                                                // pNodo->status = statNotInList;

                                                // pNodo->best_cost = INFINITO;

                                                //

                                                // }

                                                // else

                                                // newCost += elGiro.cost;

                                                // break; // Salimos del for porque ya hemos encontrado

                                                // el giro

                                                // }

                                        }

                                        // Si est? prohibido, vamos a por otro enlace, PERO

                                        // MARCAMOS EL NODO

                                        // COMO NO VISITADO PARA QUE PUEDA VOLVER A ENTRAR EN LA

                                        // LISTA DE CANDIDATOS

                                        // SI VENIMOS POR OTRO LADO.

                                        if (bGiroProhibido) {

                                                continue;

                                        }

                                        if (newCost < toNode.getBestCost()) {

                                                // Es una mejora, as? que actualizamos el vecino y

                                                // lo a?adimos a los candidatosSTL

                                                toNode.setBestCost(newCost);

                                                double newLength = node.getAccumulatedLength() + link.getDistance();

                                                toNode.setAccumulatedLength(newLength);

                                                toNode.setFromLink(link.getIdEdge());

                                                if (toNode.getStatus() != GvNode.statNowInList) {

                                                        toNode.setStatus(GvNode.statNowInList);

                                                        candidatos.add(toNode);

                                                }

                                        } // Si hay mejora

                                } // if ese nodo no ha estado en la lista de candidatosSTL

                        } // for linkNum

                } // while candidatosSTL

        }

        public GvFlag getSourceFlag() {

                return sourceFlag;

        }

        public void setSourceFlag(GvFlag sourceFlag) {

                this.sourceFlag = sourceFlag;

        }

}