Revision 35157
| trunk/extensions/extGraph/src/org/gvsig/graph/core/GvNode.java | ||
|---|---|---|
| 42 | 42 |
|
| 43 | 43 |
import java.util.ArrayList; |
| 44 | 44 |
|
| 45 |
public class GvNode {
|
|
| 45 |
import org.gvsig.fmap.algorithm.triangulation.visad.SetException; |
|
| 46 |
|
|
| 47 |
public class GvNode implements Comparable<GvNode> {
|
|
| 46 | 48 |
public final static int statNotInList = 0; |
| 47 | 49 |
public final static int statNowInList = 1; |
| 48 | 50 |
public final static int statWasInList = 2; |
| ... | ... | |
| 485 | 487 |
|
| 486 | 488 |
// TODO: provisional. QUITAR bestCost como atributo |
| 487 | 489 |
// best_cost = 0; |
| 488 |
|
|
| 490 |
setStimation(0); |
|
| 489 | 491 |
} |
| 490 | 492 |
|
| 491 | 493 |
/** |
| ... | ... | |
| 571 | 573 |
turnCosts = new ArrayList<GvTurn>(); |
| 572 | 574 |
|
| 573 | 575 |
} |
| 576 |
|
|
| 577 |
public int compareTo(GvNode o) {
|
|
| 578 |
return Double.compare(getStimation(), o.getStimation()); |
|
| 579 |
} |
|
| 580 |
|
|
| 574 | 581 |
} |
| 575 | 582 |
|
| 576 | 583 |
|
| trunk/extensions/extGraph/src/org/gvsig/graph/solvers/ShortestPathSolverAStar.java | ||
|---|---|---|
| 41 | 41 |
package org.gvsig.graph.solvers; |
| 42 | 42 |
|
| 43 | 43 |
import java.util.ArrayList; |
| 44 |
import java.util.PriorityQueue; |
|
| 44 | 45 |
|
| 45 | 46 |
import org.gvsig.exceptions.BaseException; |
| 46 | 47 |
import org.gvsig.graph.core.GlobalCounter; |
| ... | ... | |
| 163 | 164 |
node.calculateStimation(finalNode, 0); |
| 164 | 165 |
|
| 165 | 166 |
// Priority Queue |
| 166 |
FibHeap pq = new FibHeap(graph.numVertices());
|
|
| 167 |
pq.insert(node, node.getStimation());
|
|
| 167 |
PriorityQueue<GvNode> pq = new PriorityQueue<GvNode>();
|
|
| 168 |
pq.add(node);
|
|
| 168 | 169 |
|
| 169 | 170 |
|
| 170 | 171 |
// Mientras que la lista de candidatosSTL no est? vac?a, procesamos |
| 171 | 172 |
// Nodos |
| 172 | 173 |
double bestStimation; |
| 173 | 174 |
|
| 174 |
while ((!bExit) && (!pq.empty())) {
|
|
| 175 |
while ((!bExit) && (!pq.isEmpty())) {
|
|
| 175 | 176 |
// Buscamos el nodo con m?nimo coste |
| 176 | 177 |
// node = (GvNode) candidatos.get(0); |
| 177 | 178 |
// bestNode = node; |
| ... | ... | |
| 186 | 187 |
// } |
| 187 | 188 |
// } // for nodeNum candidatosSTL |
| 188 | 189 |
|
| 189 |
node = (GvNode) pq.extract_min(); // get the lowest-weightSum Vertex 'u',
|
|
| 190 |
node = pq.poll(); // get the lowest-weightSum Vertex 'u',
|
|
| 190 | 191 |
// node = bestNode; |
| 191 | 192 |
// Borramos el mejor nodo de la lista de candidatosSTL |
| 192 | 193 |
node.setStatus(GvNode.statWasInList); |
| ... | ... | |
| 295 | 296 |
|
| 296 | 297 |
if (toNode.getStatus() != GvNode.statNowInList) {
|
| 297 | 298 |
toNode.setStatus(GvNode.statNowInList); |
| 298 |
pq.insert_or_dec_key(toNode, toNode.getStimation());
|
|
| 299 |
pq.add(toNode);
|
|
| 299 | 300 |
// candidatos.add(toNode); |
| 300 | 301 |
} |
| 301 | 302 |
} // Si hay mejora |
| trunk/extensions/extGraph/src/org/gvsig/graph/solvers/ShortestPathSolverDijkstra.java | ||
|---|---|---|
| 41 | 41 |
package org.gvsig.graph.solvers; |
| 42 | 42 |
|
| 43 | 43 |
import java.util.ArrayList; |
| 44 |
import java.util.PriorityQueue; |
|
| 44 | 45 |
|
| 45 | 46 |
import org.gvsig.exceptions.BaseException; |
| 46 | 47 |
import org.gvsig.graph.core.AbstractNetSolver; |
| ... | ... | |
| 153 | 154 |
node.setStatus(GvNode.statNowInList); |
| 154 | 155 |
bestCost = Double.MAX_VALUE; |
| 155 | 156 |
// Priority Queue |
| 156 |
FibHeap pq = new FibHeap(graph.numVertices());
|
|
| 157 |
pq.insert(node, 0);
|
|
| 157 |
PriorityQueue<GvNode> pq = new PriorityQueue<GvNode>();
|
|
| 158 |
pq.add(node);
|
|
| 158 | 159 |
|
| 159 | 160 |
// Mientras que la lista de candidatosSTL no est? vac?a, procesamos |
| 160 | 161 |
// Nodos |
| 161 | 162 |
|
| 162 |
while ((!bExit) && (!pq.empty())) {
|
|
| 163 |
while ((!bExit) && (!pq.isEmpty())) {
|
|
| 163 | 164 |
// Buscamos el nodo con m?nimo coste |
| 164 | 165 |
// node = (GvNode) candidatos.get(0); |
| 165 | 166 |
// bestNode = node; |
| ... | ... | |
| 174 | 175 |
// |
| 175 | 176 |
// |
| 176 | 177 |
// node = bestNode; |
| 177 |
node = (GvNode) pq.extract_min(); // get the lowest-weightSum Vertex 'u',
|
|
| 178 |
node = pq.poll(); // get the lowest-weightSum Vertex 'u',
|
|
| 178 | 179 |
// Borramos el mejor nodo de la lista de candidatosSTL |
| 179 | 180 |
node.setStatus(GvNode.statWasInList); |
| 180 | 181 |
// TODO: BORRAR POR INDEX, NO AS?. ES M?S LENTO QUE SI BORRAMOS EL i-?simo. |
| ... | ... | |
| 245 | 246 |
|
| 246 | 247 |
if (toNode.getStatus() != GvNode.statNowInList) {
|
| 247 | 248 |
toNode.setStatus(GvNode.statNowInList); |
| 248 |
pq.insert_or_dec_key(toNode, newCost); |
|
| 249 |
toNode.setStimation(newCost); |
|
| 250 |
pq.add(toNode); |
|
| 249 | 251 |
//candidatos.add(toNode); |
| 250 | 252 |
} |
| 251 | 253 |
} // Si hay mejora |
Also available in: Unified diff