PathFind::FringeSearch< MARKER > Class Template Reference

#include <fringesearch.h>

Inheritance diagram for PathFind::FringeSearch< MARKER >:

[legend]Collaboration diagram for PathFind::FringeSearch< MARKER >:

[legend]List of all members.

---

Detailed Description

template<class MARKER = MarkerFastClear>
class PathFind::FringeSearch< MARKER >

IDA* like search keeping a list of the fringe nodes.

This avoids re-expansion of interior nodes at each new iteration.

Statistics (see Search::createStatistics and Search::getStatistics):

• "cpu_time"
• "iterations"
• "nodes_expanded"
• "nodes_visited"
• "path_cost"
• "path_length"

Definition at line 99 of file fringesearch.h.

Public Member Functions
	FringeSearch ()
StatisticsCollection	createStatistics ()
	Create a StatisticsCollection.
bool	findPath (const Environment &env, int start, int target)
	Find a path.
const vector< int > &	getPath () const
const StatisticsCollection &	getStatistics () const
	Get statistics of last search.
const vector< char > &	getVisitedNodes () const
	Get a vector with char labels for each visited node.
long long int	getNodesLimit () const
void	setNodesLimit (long long int nodesLimit)
	Set nodes limit for search engine.
Public Attributes
long long int	m_nodesLimit
Private Member Functions
void	addCache (int nodeId, int gValue, int iteration, int parent)
bool	checkCache (int nodeId, int gValue, int iteration) const
void	constructPath (int start)
void	getFromCache (int nodeId, int &gValue, int &parent) const
void	doIteration (int iteration, int fLimit, int &fMin)
void	init (int numberNodes)
void	markVisitedNode (int nodeId, int iteration)
Private Attributes
int	m_nodesExpanded
int	m_nodesVisited
int	m_target
const Environment *	m_env
Fringe	m_fringe
StatisticsCollection	m_statistics
vector< CacheElement >	m_cache
MARKER	m_isCacheValid
vector< char >	m_visitedNodes
vector< int >	m_path

---

Constructor & Destructor Documentation

template<class MARKER> PathFind::FringeSearch< MARKER >::FringeSearch (   )

Definition at line 179 of file fringesearch.h.

---

Member Function Documentation

template<class MARKER> void PathFind::FringeSearch< MARKER >::addCache (  int  nodeId, int  gValue, int  iteration, int  parent )  [private]

Definition at line 185 of file fringesearch.h. References PathFind::FringeSearch< MARKER >::m_cache, PathFind::FringeSearch< MARKER >::CacheElement::m_gValue, PathFind::FringeSearch< MARKER >::m_isCacheValid, PathFind::FringeSearch< MARKER >::CacheElement::m_iteration, and PathFind::FringeSearch< MARKER >::CacheElement::m_parent. Referenced by PathFind::FringeSearch< MARKER >::doIteration(), and PathFind::FringeSearch< MARKER >::findPath().

template<class MARKER> bool PathFind::FringeSearch< MARKER >::checkCache (  int  nodeId, int  gValue, int  iteration )  const [private]

Definition at line 196 of file fringesearch.h. References PathFind::FringeSearch< MARKER >::m_cache, PathFind::FringeSearch< MARKER >::CacheElement::m_gValue, PathFind::FringeSearch< MARKER >::m_isCacheValid, and PathFind::FringeSearch< MARKER >::CacheElement::m_iteration. Referenced by PathFind::FringeSearch< MARKER >::doIteration().

template<class MARKER> void PathFind::FringeSearch< MARKER >::constructPath (  int  start  )  [private]

Definition at line 209 of file fringesearch.h. References PathFind::FringeSearch< MARKER >::m_cache, PathFind::FringeSearch< MARKER >::m_isCacheValid, PathFind::FringeSearch< MARKER >::m_path, and PathFind::FringeSearch< MARKER >::m_target. Referenced by PathFind::FringeSearch< MARKER >::findPath().

template<class MARKER> StatisticsCollection PathFind::FringeSearch< MARKER >::createStatistics (   )  [virtual]

Create a StatisticsCollection. Contains Statistics instances for all values tracked. Useful for keeping accumulated statistics by creating the collection and merging the statistics of a search as returned by getStatistics(). Implements PathFind::Search. Definition at line 226 of file fringesearch.h. References PathFind::StatisticsCollection::create().

template<class MARKER> void PathFind::FringeSearch< MARKER >::doIteration (  int  iteration, int  fLimit, int &  fMin )  [private]

Definition at line 239 of file fringesearch.h. References PathFind::Statistics::add(), PathFind::FringeSearch< MARKER >::addCache(), PathFind::FringeSearch< MARKER >::checkCache(), PathFind::StatisticsCollection::get(), PathFind::Fringe::getCurrentNode(), PathFind::FringeSearch< MARKER >::getFromCache(), PathFind::Environment::getHeuristic(), PathFind::Environment::getSuccessors(), PathFind::Fringe::insertNode(), PathFind::Environment::Successor::m_cost, PathFind::FringeSearch< MARKER >::m_env, PathFind::FringeSearch< MARKER >::m_fringe, PathFind::FringeSearch< MARKER >::m_nodesExpanded, PathFind::FringeSearch< MARKER >::m_nodesVisited, PathFind::FringeSearch< MARKER >::m_statistics, PathFind::Environment::Successor::m_target, PathFind::FringeSearch< MARKER >::m_target, PathFind::FringeSearch< MARKER >::markVisitedNode(), PathFind::Fringe::nextNode(), PathFind::Fringe::removeCurrentNode(), and PathFind::Fringe::startIteration(). Referenced by PathFind::FringeSearch< MARKER >::findPath().

template<class MARKER> bool PathFind::FringeSearch< MARKER >::findPath (  const Environment &  env, int  start, int  target )  [virtual]

Find a path. Returns: false, if search was aborted due to node limit. Implements PathFind::Search. Definition at line 287 of file fringesearch.h. References PathFind::Statistics::add(), PathFind::FringeSearch< MARKER >::addCache(), PathFind::FringeSearch< MARKER >::constructPath(), PathFind::FringeSearch< MARKER >::doIteration(), PathFind::StatisticsCollection::get(), PathFind::FringeSearch< MARKER >::init(), PathFind::Fringe::insertNode(), PathFind::Environment::isValidNodeId(), PathFind::FringeSearch< MARKER >::m_env, PathFind::FringeSearch< MARKER >::m_fringe, PathFind::FringeSearch< MARKER >::m_isCacheValid, PathFind::FringeSearch< MARKER >::m_nodesExpanded, PathFind::FringeSearch< MARKER >::m_nodesVisited, PathFind::FringeSearch< MARKER >::m_path, PathFind::FringeSearch< MARKER >::m_statistics, and PathFind::FringeSearch< MARKER >::m_target.

template<class MARKER> void PathFind::FringeSearch< MARKER >::getFromCache (  int  nodeId, int &  gValue, int &  parent )  const [private]

Definition at line 324 of file fringesearch.h. References PathFind::FringeSearch< MARKER >::m_cache, PathFind::FringeSearch< MARKER >::CacheElement::m_gValue, PathFind::FringeSearch< MARKER >::m_isCacheValid, and PathFind::FringeSearch< MARKER >::CacheElement::m_parent. Referenced by PathFind::FringeSearch< MARKER >::doIteration().

long long int PathFind::Search::getNodesLimit (   )  const [inline, inherited]

Definition at line 48 of file search.h. References PathFind::Search::m_nodesLimit.

template<class MARKER = MarkerFastClear> const vector<int>& PathFind::FringeSearch< MARKER >::getPath (   )  const [inline, virtual]

Implements PathFind::Search. Definition at line 109 of file fringesearch.h. References PathFind::FringeSearch< MARKER >::m_path.

template<class MARKER> const StatisticsCollection & PathFind::FringeSearch< MARKER >::getStatistics (   )  const [virtual]

Get statistics of last search. Implements PathFind::Search. Definition at line 334 of file fringesearch.h. References PathFind::FringeSearch< MARKER >::m_statistics.

template<class MARKER = MarkerFastClear> const vector<char>& PathFind::FringeSearch< MARKER >::getVisitedNodes (   )  const [inline, virtual]

Get a vector with char labels for each visited node. Space char means not visited, otherwise the char can have different values and meanings depending on the concrete search engine. Implements PathFind::Search. Definition at line 116 of file fringesearch.h. References PathFind::FringeSearch< MARKER >::m_visitedNodes.

template<class MARKER> void PathFind::FringeSearch< MARKER >::init (  int  numberNodes  )  [private]

Definition at line 340 of file fringesearch.h. References PathFind::StatisticsCollection::clear(), PathFind::Fringe::init(), PathFind::FringeSearch< MARKER >::m_cache, PathFind::FringeSearch< MARKER >::m_fringe, PathFind::FringeSearch< MARKER >::m_isCacheValid, PathFind::FringeSearch< MARKER >::m_statistics, and PathFind::FringeSearch< MARKER >::m_visitedNodes. Referenced by PathFind::FringeSearch< MARKER >::findPath().

template<class MARKER> void PathFind::FringeSearch< MARKER >::markVisitedNode (  int  nodeId, int  iteration )  [private]

Definition at line 351 of file fringesearch.h. References PathFind::getVisitedNodeLabel(), and PathFind::FringeSearch< MARKER >::m_visitedNodes. Referenced by PathFind::FringeSearch< MARKER >::doIteration().

void PathFind::Search::setNodesLimit (  long long int  nodesLimit  )  [inline, inherited]

Set nodes limit for search engine. The default is -1 and means unlimited search. The nodes limit is a hint only, the search engine may ignore it. Reimplemented in PathFind::AStar< MARKER, CLOSED >. Definition at line 71 of file search.h. References PathFind::Search::m_nodesLimit.

---

Member Data Documentation

template<class MARKER = MarkerFastClear> vector<CacheElement> PathFind::FringeSearch< MARKER >::m_cache [private]

Definition at line 146 of file fringesearch.h. Referenced by PathFind::FringeSearch< MARKER >::addCache(), PathFind::FringeSearch< MARKER >::checkCache(), PathFind::FringeSearch< MARKER >::constructPath(), PathFind::FringeSearch< MARKER >::getFromCache(), and PathFind::FringeSearch< MARKER >::init().

template<class MARKER = MarkerFastClear> const Environment* PathFind::FringeSearch< MARKER >::m_env [private]

Definition at line 140 of file fringesearch.h. Referenced by PathFind::FringeSearch< MARKER >::doIteration(), and PathFind::FringeSearch< MARKER >::findPath().

template<class MARKER = MarkerFastClear> Fringe PathFind::FringeSearch< MARKER >::m_fringe [private]

Definition at line 142 of file fringesearch.h. Referenced by PathFind::FringeSearch< MARKER >::doIteration(), PathFind::FringeSearch< MARKER >::findPath(), and PathFind::FringeSearch< MARKER >::init().

template<class MARKER = MarkerFastClear> MARKER PathFind::FringeSearch< MARKER >::m_isCacheValid [private]

Definition at line 148 of file fringesearch.h. Referenced by PathFind::FringeSearch< MARKER >::addCache(), PathFind::FringeSearch< MARKER >::checkCache(), PathFind::FringeSearch< MARKER >::constructPath(), PathFind::FringeSearch< MARKER >::findPath(), PathFind::FringeSearch< MARKER >::getFromCache(), and PathFind::FringeSearch< MARKER >::init().

template<class MARKER = MarkerFastClear> int PathFind::FringeSearch< MARKER >::m_nodesExpanded [private]

Definition at line 134 of file fringesearch.h. Referenced by PathFind::FringeSearch< MARKER >::doIteration(), and PathFind::FringeSearch< MARKER >::findPath().

long long int PathFind::Search::m_nodesLimit [inherited]

Definition at line 78 of file search.h. Referenced by PathFind::Search::getNodesLimit(), PathFind::Search::Search(), PathFind::IDAStar::searchPathIdaStar(), PathFind::Search::setNodesLimit(), and PathFind::AStar< MARKER, CLOSED >::setNodesLimit().

template<class MARKER = MarkerFastClear> int PathFind::FringeSearch< MARKER >::m_nodesVisited [private]

Definition at line 136 of file fringesearch.h. Referenced by PathFind::FringeSearch< MARKER >::doIteration(), and PathFind::FringeSearch< MARKER >::findPath().

template<class MARKER = MarkerFastClear> vector<int> PathFind::FringeSearch< MARKER >::m_path [private]

Definition at line 152 of file fringesearch.h. Referenced by PathFind::FringeSearch< MARKER >::constructPath(), PathFind::FringeSearch< MARKER >::findPath(), and PathFind::FringeSearch< MARKER >::getPath().

template<class MARKER = MarkerFastClear> StatisticsCollection PathFind::FringeSearch< MARKER >::m_statistics [private]

Definition at line 144 of file fringesearch.h. Referenced by PathFind::FringeSearch< MARKER >::doIteration(), PathFind::FringeSearch< MARKER >::findPath(), PathFind::FringeSearch< MARKER >::getStatistics(), and PathFind::FringeSearch< MARKER >::init().

template<class MARKER = MarkerFastClear> int PathFind::FringeSearch< MARKER >::m_target [private]

Definition at line 138 of file fringesearch.h. Referenced by PathFind::FringeSearch< MARKER >::constructPath(), PathFind::FringeSearch< MARKER >::doIteration(), and PathFind::FringeSearch< MARKER >::findPath().

template<class MARKER = MarkerFastClear> vector<char> PathFind::FringeSearch< MARKER >::m_visitedNodes [private]

Definition at line 150 of file fringesearch.h. Referenced by PathFind::FringeSearch< MARKER >::getVisitedNodes(), PathFind::FringeSearch< MARKER >::init(), and PathFind::FringeSearch< MARKER >::markVisitedNode().

---

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

• fringesearch.h

---