com.kuka.graph.alg
Class AStar<N,E extends Edge<N>>

java.lang.Object
  com.kuka.graph.alg.AStar<N,E>

Type Parameters:

N - the node type

E - the edge type

public class AStar<N,E extends Edge<N>>
extends Object

Implementation of the A* path finding algorithm.

Constructor Summary

AStar(Graph<N,E> graph, CostFunction<N,E> cost, N start, N goal)
Instantiates a new A*.

AStar(Graph<N,E> graph, CostFunction<N,E> cost, N start, N goal, GraphElementFilter<N> nodeFilter)
Instantiates a new A*.

AStar(Graph<N,E> graph, CostFunction<N,E> cost, N start, N goal, GraphElementFilter<N> nodeFilter, GraphElementFilter<Edge<N>> edgeFilter)
Instantiates a new A*.

Method Summary

Path<N,E>

getShortestPath() Determines the shortest path, i.e. the path with minimum overall cost from start to goal.

Methods inherited from class java.lang.Object

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

Constructor Detail

AStar

public AStar(Graph<N,E> graph,
             CostFunction<N,E> cost,
             N start,
             N goal)

Instantiates a new A*.

Parameters:

graph - the graph to find a path in

cost - the function providing information about graph traversal costs

start - the start node in the graph

goal - the goal node in the graph

AStar

public AStar(Graph<N,E> graph,
             CostFunction<N,E> cost,
             N start,
             N goal,
             GraphElementFilter<N> nodeFilter)

Instantiates a new A*.

Parameters:

graph - the graph to find a path in

cost - the function providing information about graph traversal costs

start - the start node in the graph

goal - the goal node in the graph

nodeFilter - the filter specifying whether a node may be traversed or must not be included in the path

AStar

public AStar(Graph<N,E> graph,
             CostFunction<N,E> cost,
             N start,
             N goal,
             GraphElementFilter<N> nodeFilter,
             GraphElementFilter<Edge<N>> edgeFilter)

Instantiates a new A*.

Parameters:

graph - the graph to find a path in

cost - the function providing information about graph traversal costs

start - the start node in the graph

goal - the goal node in the graph

nodeFilter - the filter specifying whether a node may be traversed or must not be included in the path

edgeFilter - the filter specifying whether an edge may be traversed or must not be included in the path

Method Detail

getShortestPath

public Path<N,E> getShortestPath()

Determines the shortest path, i.e. the path with minimum overall cost from start to goal. I no path can be found, the returned path is empty.

Returns:

the shortest path