pathfinder.GraphSearch_Astar Class Reference

Inheritance diagram for pathfinder.GraphSearch_Astar:

Public Member Functions
	GraphSearch_Astar (Graph graph)
	GraphSearch_Astar (Graph graph, AstarHeuristic ash)
LinkedList< GraphNode >	search (int startID, int targetID)
LinkedList< GraphNode >	search (int startID, int targetID, boolean remember)
GraphEdge[]	getExaminedEdges ()
GraphNode[]	getRoute ()
LinkedList< GraphNode >	search (int startID, int targetID)
LinkedList< GraphNode >	search (int startID, int targetID, boolean remember)
GraphEdge[]	getExaminedEdges ()
public< T > T[]	getExaminedEdges (T[] array)
GraphNode[]	getRoute ()
public< T > T[]	getRoute (T[] array)

Protected Member Functions
double	getGraphCost (GraphNode node)
double	getFullCost (GraphNode node)

Protected Attributes
Graph	graph
HashSet< GraphNode >	settledNodes
PriorityQueue< GraphNodeCost >	unsettledNodes
HashMap< GraphNode, GraphNode >	parent
HashMap< GraphNode, Double >	graphCostToNode
HashMap< GraphNode, Double >	fullCostAtNode
LinkedList< GraphNode >	route
AstarHeuristic	ash
HashSet< GraphEdge >	examinedEdges

Detailed Description

A Star
Objects of this class are used to search a graph and find a path between two nodes using this algorithm.

Author

Peter Lager

Constructor & Destructor Documentation

GraphSearch_Astar() [1/2]

pathfinder.GraphSearch_Astar.GraphSearch_Astar

(

Graph

graph

)

Create a search object that uses the A* algorithm for the given graph.
By default it uses the crow-flies heuristic.

Parameters

graph

the graph to use

GraphSearch_Astar() [2/2]

pathfinder.GraphSearch_Astar.GraphSearch_Astar	(	Graph	graph,
		AstarHeuristic	ash
	)

Create a search object that uses the A* algorithm for the given graph using the given heuristic.

Parameters

graph	the graph to use
ash	the heuristic to use

Member Function Documentation

getExaminedEdges()

GraphEdge[] pathfinder.GraphSearch_Astar.getExaminedEdges

(

)

Get all the edges examined during the search.

Returns

edges examined or array size 0 if none found

Implements pathfinder.IGraphSearch.

getFullCost()

double pathfinder.GraphSearch_Astar.getFullCost ( GraphNode  node )

protected

Used during search.

Parameters

node

Returns

getGraphCost()

double pathfinder.GraphSearch_Astar.getGraphCost ( GraphNode  node )

protected

Used during search.

Parameters

node

Returns

getRoute()

GraphNode[] pathfinder.GraphSearch_Astar.getRoute

(

)

Get the path found as an array of GraphNode(s) in start->end order

Returns

path found or array size 0 if none found

Implements pathfinder.IGraphSearch.

search() [1/2]

LinkedList< GraphNode > pathfinder.GraphSearch_Astar.search	(	int	startID,
		int	targetID
	)

Search for a route from node startID and ends at targetID.
This will return a linkedlist of the nodes that make up the route from start to end order.
If either the start or target node does not exist or if a route can't be found the returned list is empty.

Parameters

startID	id of the start node
targetID	id of the target node

Returns

the route as a list of nodes

Implements pathfinder.IGraphSearch.

search() [2/2]

LinkedList< GraphNode > pathfinder.GraphSearch_Astar.search	(	int	startID,
		int	targetID,
		boolean	remember
	)

Search for a route from node startID and ends at targetID.
This will return a linkedlist of the nodes that make up the route from start to end order.
If either the start or target node does not exist or if a route can't be found the returned list is empty.

Parameters

startID	id of the start node
targetID	id of the target node
remember	whether to remember the examined edges.

Returns

the route as a list of nodes

Implements pathfinder.IGraphSearch.

Member Data Documentation

ash

AstarHeuristic pathfinder.GraphSearch_Astar.ash

protected

The heuristic used to estimate cost to target.

examinedEdges

HashSet<GraphEdge> pathfinder.GraphSearch_Astar.examinedEdges

protected

Used to remember examined edges

fullCostAtNode

HashMap<GraphNode, Double> pathfinder.GraphSearch_Astar.fullCostAtNode

protected

Stores the smallest full cost (path cost + heuristic cost) found so far for a given node.

graphCostToNode

HashMap<GraphNode, Double> pathfinder.GraphSearch_Astar.graphCostToNode

protected

Stores the smallest path cost found so far for a given node

parent

HashMap<GraphNode, GraphNode> pathfinder.GraphSearch_Astar.parent

protected

Indicates the predecessor node for a given node. This is used to store the shortest path. <node of interest, node where the edge originated>

route

LinkedList<GraphNode> pathfinder.GraphSearch_Astar.route

protected

List for routes nodes in order of travel

settledNodes

HashSet<GraphNode> pathfinder.GraphSearch_Astar.settledNodes

protected

The settled nodes - the nodes whose shortest distances from the source have been found.

unsettledNodes

PriorityQueue<GraphNodeCost> pathfinder.GraphSearch_Astar.unsettledNodes

protected

The unsettled nodes

---

The documentation for this class was generated from the following file:

• /Users/peter/git/path-finder-repos/Path Finder/src/pathfinder/GraphSearch_Astar.java