/*
 * (C) Copyright 2016-2017, by Dimitrios Michail and Contributors.
 *
 * JGraphT : a free Java graph-theory library
 *
 * This program and the accompanying materials are dual-licensed under
 * either
 *
 * (a) the terms of the GNU Lesser General Public License version 2.1
 * as published by the Free Software Foundation, or (at your option) any
 * later version.
 *
 * or (per the licensee's choosing)
 *
 * (b) the terms of the Eclipse Public License v1.0 as published by
 * the Eclipse Foundation.
 */
package org.jgrapht.alg.shortestpath;

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.alg.interfaces.*;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm.*;
import org.jgrapht.alg.util.*;
import org.jgrapht.graph.*;

/**
 * An admissible heuristic for the A* algorithm using a set of landmarks and the triangle
 * inequality. Assumes that the graph contains non-negative edge weights.
 *
 * 

* The heuristic requires a set of input nodes from the graph, which are used as landmarks. During a * pre-processing phase, which requires two shortest path computations per landmark using Dijkstra's * algorithm, all distances to and from these landmark nodes are computed and stored. Afterwards, * the heuristic estimates the distance from a vertex to another vertex using the already computed * distances to and from the landmarks and the fact that shortest path distances obey the * triangle-inequality. The heuristic's space requirement is O(n) per landmark where n is the number * of vertices of the graph. In case of undirected graphs only one Dijkstra's algorithm execution is * performed per landmark. * *

* The method generally abbreviated as ALT (from A*, Landmarks and Triangle inequality) is described * in detail in the following * paper which also contains a discussion on landmark selection strategies. *

* *

* Note that using this heuristic does not require the edge weights to satisfy the * triangle-inequality. The method depends on the triangle inequality with respect to the shortest * path distances in the graph, not an embedding in Euclidean space or some other metric, which need * not be present. * *

* In general more landmarks will speed up A* but will need more space. Given an A* query with * vertices source and target, a good landmark appears "before" source or "after" target where * before and after are relative to the "direction" from source to target. * * @author Dimitrios Michail * * @param the graph vertex type * @param the graph edge type */ public class ALTAdmissibleHeuristic implements AStarAdmissibleHeuristic { private final Graph graph; private final Comparator comparator; private final Map> fromLandmark; private final Map> toLandmark; private final boolean directed; /** * Constructs a new {@link AStarAdmissibleHeuristic} using a set of landmarks. * * @param graph the graph * @param landmarks a set of vertices of the graph which will be used as landmarks * * @throws IllegalArgumentException if no landmarks are provided * @throws IllegalArgumentException if the graph contains edges with negative weights */ public ALTAdmissibleHeuristic(Graph graph, Set landmarks) { this.graph = Objects.requireNonNull(graph, "Graph cannot be null"); Objects.requireNonNull(landmarks, "Landmarks cannot be null"); if (landmarks.isEmpty()) { throw new IllegalArgumentException("At least one landmark must be provided"); } this.fromLandmark = new HashMap<>(); if (graph instanceof DirectedGraph) { this.directed = true; this.toLandmark = new HashMap<>(); } else if (graph instanceof UndirectedGraph) { this.directed = false; this.toLandmark = this.fromLandmark; } else { throw new IllegalArgumentException("Graph must be directed or undirected"); } this.comparator = new ToleranceDoubleComparator(); // precomputation and validation for (V v : landmarks) { for (E e : graph.edgesOf(v)) { if (comparator.compare(graph.getEdgeWeight(e), 0d) < 0) { throw new IllegalArgumentException("Graph edge weights cannot be negative"); } } precomputeToFromLandmark(v); } } /** * An admissible heuristic estimate from a source vertex to a target vertex. The estimate is * always non-negative and never overestimates the true distance. * * @param u the source vertex * @param t the target vertex * * @return an admissible heuristic estimate */ @Override public double getCostEstimate(V u, V t) { double maxEstimate = 0d; /* * Special case, source equals target */ if (u.equals(t)) { return maxEstimate; } /* * Special case, source is landmark */ if (fromLandmark.containsKey(u)) { return fromLandmark.get(u).get(t); } /* * Special case, target is landmark */ if (toLandmark.containsKey(t)) { return toLandmark.get(t).get(u); } /* * Compute from landmarks */ for (V l : fromLandmark.keySet()) { double estimate; Map from = fromLandmark.get(l); if (directed) { Map to = toLandmark.get(l); estimate = Math.max(to.get(u) - to.get(t), from.get(t) - from.get(u)); } else { estimate = Math.abs(from.get(u) - from.get(t)); } // max over all landmarks if (Double.isFinite(estimate)) { maxEstimate = Math.max(maxEstimate, estimate); } } return maxEstimate; } /** * Compute all distances to and from a landmark * * @param landmark the landmark */ private void precomputeToFromLandmark(V landmark) { // compute distances from landmark SingleSourcePaths fromLandmarkPaths = new DijkstraShortestPath<>(graph).getPaths(landmark); Map fromLandMarkDistances = new HashMap<>(); for (V v : graph.vertexSet()) { fromLandMarkDistances.put(v, fromLandmarkPaths.getWeight(v)); } fromLandmark.put(landmark, fromLandMarkDistances); // compute distances to landmark (using reverse graph) if (directed) { DirectedGraph reverseGraph = new EdgeReversedGraph<>((DirectedGraph) graph); SingleSourcePaths toLandmarkPaths = new DijkstraShortestPath<>(reverseGraph).getPaths(landmark); Map toLandMarkDistances = new HashMap<>(); for (V v : graph.vertexSet()) { toLandMarkDistances.put(v, toLandmarkPaths.getWeight(v)); } toLandmark.put(landmark, toLandMarkDistances); } } }

Ads help maintain this website.