Package com.jgalgo.alg.shortestpath

Class ShortestPathHeuristicStAbstract

java.lang.Object

com.jgalgo.alg.shortestpath.ShortestPathHeuristicStAbstract

All Implemented Interfaces:

ShortestPathHeuristicSt

Direct Known Subclasses:

ShortestPathAStar

public abstract class ShortestPathHeuristicStAbstract
extends Object
implements ShortestPathHeuristicSt

Abstract class for computing shortest path between a source and a target with a heuristic.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
ShortestPathHeuristicStAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V,E> Path<V,E>	computeShortestPath(Graph<V,E> g, WeightFunction<E> w, V source, V target, ToDoubleFunction<V> vHeuristic)	Compute the shortest path between two vertices in a graph.
IPath	computeShortestPath(IntGraph g, IWeightFunction w, int source, int target, IntToDoubleFunction vHeuristic)	Compute the shortest path between two vertices in an int graph.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ShortestPathHeuristicStAbstract

public ShortestPathHeuristicStAbstract()

Default constructor.

Method Detail

computeShortestPath

public <V,E> Path<V,E> computeShortestPath(Graph<V,E> g,
                                                       WeightFunction<E> w,
                                                       V source,
                                                       V target,
                                                       ToDoubleFunction<V> vHeuristic)

Description copied from interface: ShortestPathHeuristicSt

Compute the shortest path between two vertices in a graph.

If g is an IntGraph, a IPath object will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

Specified by:

computeShortestPath in interface ShortestPathHeuristicSt

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

source - a source vertex

target - a target vertex

vHeuristic - a heuristic function that map each vertex to double. The heuristic should be close to the real distance of each vertex to the target.

Returns:

the short path found from source to target

computeShortestPath

public IPath computeShortestPath(IntGraph g,
                                 IWeightFunction w,
                                 int source,
                                 int target,
                                 IntToDoubleFunction vHeuristic)

Description copied from interface: ShortestPathHeuristicSt

Compute the shortest path between two vertices in an int graph.

Specified by:

computeShortestPath in interface ShortestPathHeuristicSt

Parameters:

g - a graph

w - an edge weight function

source - a source vertex

target - a target vertex

vHeuristic - a heuristic function that map each vertex to double. The heuristic should be close to the real distance of each vertex to the target.

Returns:

the short path found from source to target