Quick Reference to the AStar Class (with Detailed Explanation)

---

For the AStar search algorithm, DOSL provides two class templates: AStar::Node<> and AStar::Algorithm<>. The declarations are as follows:

template <class nodeType, class costType=double>  class AStar::Node;
template <class AlgDerived, class nodeType, class costType=double>  class AStar::Algorithm;

In order to use DOSL, a user needs to define two classes: i. A class describing a node (vertex) type, and, ii. a class describing the complete search problem. A user-defined node type should derive from the AStar::Node<> template, while the user-defined search problem class should derive from the AStar::Algorithm<> template. For example,

class userNodeClass : public AStar::Node <userNodeClass, int>
{ /* (user code) */ }

class userSearchProblemClass : public AStar::Algorithm <userSearchProblemClass, userNodeClass, int>
{ /* (user code) */ }

In either of the templates, AStar::Node<> or AStar::Algorithm<>, the first template parameter is the derived class that is being defined. The last parameter is the type of the cost (usually a number type like integer of a floating-point type).

Note how in the declaration of the user-defined classes the first template parameter is the name of the class itself which is being declared. This syntax is known as a Curiously Recurring Template Pattern (CRTP), and although it looks strange, it is a valid C++ semantic.

Inside the user-defined node class and the user-defined search problem class, the user needs to define some specific functions that give DOSL information about the problem such as structure of the graph, cost of edges, etc. Below we list the members of each of these classes that should or can be defined inside each of these user-defined classes, along with brief explanation for each:

Member Functions to be Defined in User-defined Derived Node Class

/* Required (the user-defined node class should define the following): */
bool operator==(const userNodeClass& n) const;

/* Optional if defined in user-defined search problem class (superseded 
   by homonymous members of user-defined search problem class, if defined): */
int getHashBin (void); // <- recommended here than in the search problem class
void getSuccessors (std::vector<userNodeClass>* s, std::vector<CostType>* c);

/* Optional (superseded by homonymous members of user-defined search
   problem class, if defined): */
CostType getHeuristics (void);
CostType getHeapKey (double subopEps);
bool stopSearch (void);
bool bookmarkNode (void);
void nodeEvent (unsigned int e);
void print (std::string head, std::string tail);

Member Functions to be Defined in User-defined Derived Search Problem Class

/* Required: */
std::vector<userNodeClass> getStartNodes (void);

/* All the following members, if defined, supersedes any homonymous 
   members in the user-defined node class. */

/* Required, if not defined as a member of the user-defined node class: */
void getSuccessors (userNodeClass &n, std::vector<userNodeClass>* const s, std::vector<CostType>* const c);

/* Highly recommended, if not defined as a member of the user-defined node class: */
int getHashBin (userNodeClass &n);

/* Optional: */
CostType getHeuristics (userNodeClass& n);
CostType getHeapKey (userNodeClass& n);
bool stopSearch (userNodeClass &n);
bool bookmarkNode (userNodeClass &n);
void nodeEvent (userNodeClass &n, unsigned int e);
void print (userNodeClass &n, std::string head);

Brief description of each of the member functions:

• userNodeClass::operator== gives the recipe for comparing two instances of the user-defined node type. It should return true if and only if two nodes in the graph are considered to be the same.
• getSuccessors should describe the local structure of the graph for a given node. For a node it should generate its successors (the vector pointer s) and the costs/lengths of edges connecting to those. In implementation of getSuccessors, assume that *s and *c are defined and are empty vectors.
• getHashBin should compute an efficient hash function for the node. If not provided, all nodes will be put into a single hash bin.

---

Use: Derive user-defined node type from AStar::Node<> using CRTP template parameters.

Example:

class userDefinedNode : public AStar::Node <userDefinedNode,int>
{ /* (user code) */ }

Member Functions to be Overwritten in User-defined Derived Node Type

AStar::Node<> contains declaration of member functions that can or should be overwritten by the derived user-defined node type. These functions are used by DOSL.

• (Required) operator== gives the recipe for comparing two instances of the user-defined node type:

  bool operator==(const userDefinedNode& n) const;

• (Recommended) getHashBin should compute an efficient hash function for the node:

  int getHashBin (void);

• (Optional) The following are optional, an can instead be defined in the class derived from AStar::Algorithm:

    void getSuccessors (std::vector<nodeType>* s, std::vector<CostType>* c);
    CostType getHeuristics (void);
    bool stopSearch (void);
    nodeEvent (unsigned int e);
    CostType getHeapKey (double subopEps);

---

Class AStar::Algorithm

Template Declared by DOSL:

template <class nodeType, class costType=double>  class AStar::Algorithm;

Use: Derive user-defined search class from AStar::Algorithm<> using CRTP template parameters.

Example:

class userSearchProblemClass : public AStar::Algorithm <userSearchProblemClass,userDefinedNode,int>
{ /* (user code) */ }

Member Functions to be Overwritten in User-defined Derived Search Class

AStar::Algorithm<> contains declaration of (virtual) member functions that can or should be overwritten by the derived user-defined search class. These functions are used by DOSL.

[In the prototypes below, CostType is the second template parameter used with AStar::Algorithm<> or AStar::Node<>.]

• (Required) getSuccessors should describe the local structure of the graph for a given node. It takes in a node, n and should generate the successors of that node (the vector pointer s) and the costs/lengths of edges connecting to those:

  void getSuccessors (userDefinedNode &n, std::vector<userDefinedNode>* const s, std::vector<CostType>* const c);

  In implementation of getSuccessors, assume that *s and *c are empty vectors.

• (Required) getStartNodes should return a vector of nodes with which the algorithm should start the search:

  std::vector<userDefinedNode> getStartNodes (void);

• (Optional) stopSearch should return true when it is intended to stop the search. The input n is the node being expanded by the algorithm:

  bool stopSearch (userDefinedNode &n);

  If stopSearch is not defined, the search will continue until the heap (open list) is empty.

• (Optional) getHeuristics returns the heuristics or getHeapKey returns the heap (open list) key:

  CostType getHeuristics (userDefinedNode& n);
  CostType getHeapKey (userDefinedNode& n);

  If neither is not defined, a zero heuristics will be used.