game2dai.graph.GraphSearch_Dijkstra Class Reference

Inheritance diagram for game2dai.graph.GraphSearch_Dijkstra:

Classes
class	GraphNodeCost

Public Member Functions
	GraphSearch_Dijkstra (Graph graph)
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	getCost (GraphNode node)

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

Package Functions
public< T > T[]	getExaminedEdges (T[] array)
public< T > T[]	getRoute (T[] array)

Private Member Functions
void	clear ()

Constructor & Destructor Documentation

GraphSearch_Dijkstra()

game2dai.graph.GraphSearch_Dijkstra.GraphSearch_Dijkstra

(

Graph

graph

)

Create a search object that uses Dijkstra's algorithm for the given graph.

Parameters

graph

the graph to use

Member Function Documentation

clear()

void game2dai.graph.GraphSearch_Dijkstra.clear ( )

private

Clears all data related to a search so this object can be reused for another search

getCost()

double game2dai.graph.GraphSearch_Dijkstra.getCost ( GraphNode  node )

protected

Used by the search method

getExaminedEdges() [1/2]

GraphEdge[] game2dai.graph.GraphSearch_Dijkstra.getExaminedEdges

(

)

Get all the edges examined during the search.

Returns

edges examined or array size 0 if none found

Implements game2dai.graph.IGraphSearch.

getExaminedEdges() [2/2]

public< T > T[] game2dai.graph.GraphSearch_Dijkstra.getExaminedEdges ( T[]  array )

package

Get all the edges examined during the search.
The type of each element in the array will be of type Object if the parameter is null otherwise it is T (where T is GraphEdge or any class that extends GraphEdge.

Parameters

array

the array to populate

Returns

edges examined or array size 0 if none found

Implements game2dai.graph.IGraphSearch.

getRoute() [1/2]

GraphNode[] game2dai.graph.GraphSearch_Dijkstra.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 game2dai.graph.IGraphSearch.

getRoute() [2/2]

public< T > T[] game2dai.graph.GraphSearch_Dijkstra.getRoute ( T[]  array )

package

Get the path found as an array of T(s) in start->end order.
The type of each element in the array will be of type Object if the parameter is null otherwise it is T (where T is GraphNode or any class that extends GraphNode.

Parameters

array

the array to populate

Returns

path found or array size 0 if none found

Implements game2dai.graph.IGraphSearch.

search() [1/2]

LinkedList< GraphNode > game2dai.graph.GraphSearch_Dijkstra.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 game2dai.graph.IGraphSearch.

search() [2/2]

LinkedList< GraphNode > game2dai.graph.GraphSearch_Dijkstra.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 game2dai.graph.IGraphSearch.

Member Data Documentation

examinedEdges

HashSet<GraphEdge> game2dai.graph.GraphSearch_Dijkstra.examinedEdges

protected

Used to remember examined edges

graphCostToNode

HashMap<GraphNode, Double> game2dai.graph.GraphSearch_Dijkstra.graphCostToNode

protected

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

parent

HashMap<GraphNode, GraphNode> game2dai.graph.GraphSearch_Dijkstra.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> game2dai.graph.GraphSearch_Dijkstra.route

protected

List for routes nodes in order of travel

settledNodes

HashSet<GraphNode> game2dai.graph.GraphSearch_Dijkstra.settledNodes

protected

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

unsettledNodes

PriorityQueue<GraphNodeCost> game2dai.graph.GraphSearch_Dijkstra.unsettledNodes

protected

The unsettled nodes

---

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

• /Users/peter/git/ai4games-repos/AI_4_2D_Games/src/game2dai/graph/GraphSearch_Dijkstra.java