pathfinder.GraphSearch_DFS Class Reference

Inheritance diagram for pathfinder.GraphSearch_DFS:

Public Member Functions
	GraphSearch_DFS (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
	GraphSearch_DFS ()

Protected Attributes
Graph	graph
HashSet< Integer >	visited
HashMap< Integer, Integer >	settledNodes
Stack< GraphEdge >	stack
LinkedList< GraphNode >	route
HashSet< GraphEdge >	examinedEdges

Detailed Description

Depth First Search
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_DFS() [1/2]

pathfinder.GraphSearch_DFS.GraphSearch_DFS ( )

protected

Prevent creating an object without a graph

GraphSearch_DFS() [2/2]

pathfinder.GraphSearch_DFS.GraphSearch_DFS

(

Graph

graph

)

Create a search object that uses depth first search algorithm for the given graph.

Parameters

graph

the graph to use

Member Function Documentation

getExaminedEdges()

GraphEdge[] pathfinder.GraphSearch_DFS.getExaminedEdges

(

)

Get all the edges examined during the search.

Returns

edges examined or array size 0 if none found

Implements pathfinder.IGraphSearch.

getRoute()

GraphNode[] pathfinder.GraphSearch_DFS.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_DFS.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_DFS.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

examinedEdges

HashSet<GraphEdge> pathfinder.GraphSearch_DFS.examinedEdges

protected

Used to remember examined edges

route

LinkedList<GraphNode> pathfinder.GraphSearch_DFS.route

protected

List for routes nodes in order of travel

settledNodes

HashMap<Integer, Integer> pathfinder.GraphSearch_DFS.settledNodes

protected

Remember the route found to from

stack

Stack<GraphEdge> pathfinder.GraphSearch_DFS.stack

protected

Stack of graph edges to consider

visited

HashSet<Integer> pathfinder.GraphSearch_DFS.visited

protected

Used to remember which nodes had been visited

---

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

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