Basic Usage (With Explanations)

DOSL uses graphs as the most basic form of discrete representation. In order to describe a graph to DOSL, the user needs to define two classes:

1. A class defining the type of node/vertex in the graph. This class needs to be derived from DOSL's [AlgName]::Node class (where[AlgName] is the name of the algorithm being used). The user must overload operator== for this class so that DOSL knows how to tell whether two nodes are the same or different.

2. A class defining the other aspects of the graph structure and the search problem. This class needs to be derived from DOSL's [AlgName]::Algorithm class. Typical members of this class (virtual members of [AlgName]::Algorithm) that the user needs to define are getSuccessors, getStartNodes, stopSearch and getHeuristics.

Below is a bare-bones example, with explanations in comments, illustrating the use of DOSL with the AStar algorithm:

// standard headers
#include <stdio.h>
#include <vector>
#include <iostream>

// DOSL headers:
#include <dosl/dosl>

// ==============================================================================
/* The following class defines the type of a vertex of the graph.
       Needs to be derived from DOSL-provided class template 'AStar::Node<node_type,cost_type>' */

class myNode : public AStar::Node<myNode,double>
{
public:
    int x, y; // (x,y) coordinates defining a point on plane.
    
    myNode () { }
    myNode (int xx, int yy) : x(xx), y(yy) { }
    
    // The comparison operator must be defined for the node type.
    bool operator==(const myNode& n) const { return (x==n.x && y==n.y); }
    
    // An efficint hash function, 'getHashBin', for node type is desired, but is optional.
    int getHashBin (void) { return (abs(((int)x>>4) + ((int)y<<3) + ((int)x<<4) + ((int)y>>3))); }
    
    // optional printing function, 'print':
    void print (std::string head="", std::string tail="") const
            { _dosl_cout << head << "x=" << x << ", y=" << y << _dosl_endl; }
};

// ==============================================================================
/* The following class contains the description of the graph (graph connectivity)
       and search problem description (start and stop criteria).
       Needs to be derived from DOSL-provided class template 'AStar::Algorithm<search_problem_class,node_type,cost_type>' */

class searchProblem : public AStar::Algorithm<searchProblem,myNode,double>
{
public:
    // user-defined problem parameters:
    myNode goal_node;
    // Constructors, if any
    searchProblem () { goal_node = myNode(150,100); }
    
    // -----------------------------------------------------------
    /* The following functions are use by the base class 'AStar::Algorithm' to determine 
           graph structure and search parameters. */
    
    /* Prototype for 'AStar::Algorithm<>::getSuccessors':
           void getSuccessors 
               (NodeType& n, std::vector<NodeType>* const s, std::vector<CostType>* const s);
       Description: Takes in a vertex, n, and returns its neighbors/successors, s, 
                    and the costs/distances of the edges, c. This defines graph connectivity. */
    
    void getSuccessors (myNode &n, std::vector<myNode>* s, std::vector<double>* c) {
        // This function should account for obstacles, constraints and size of environment.
        myNode tn;
        for (int a=-1; a<=1; a++)
            for (int b=-1; b<=1; b++) {
                if (a==0 && b==0) continue;
                
                tn.x = n.x + a;
                tn.y = n.y + b;
                
                s->push_back(tn);
                c->push_back(sqrt((double)(a*a+b*b))); 
            }
    }
    
    /* Prototype for 'AStar::Algorithm<>::getStartNodes':
           std::vector<NodeType> getStartNodes (void);
       Description: Should return the list of vertices(s) to start the search with. */
    
    std::vector<myNode> getStartNodes (void) {
        std::vector<myNode> startNodes;
        for (int a=0; a<1; ++a) {
            myNode tn (0, 0); // start node
            startNodes.push_back (tn);
        }
        return (startNodes);
    }
    
    // Optional Functions:
    
    /* Prototype for 'AStar::Algorithm<>::stopSearch':
           bool stopSearch (NodeType& n);
       Description: Determines whether to stop the search when 'n' is being expanded.
       Optional -- If not provided, search will terminate only when heap is empty. */
    
    bool stopSearch (myNode &n) {
        return (n==goal_node);
    }
    
    /* Prototype for 'AStar::Algorithm<>::getHeuristics':
           CostType getHeuristics (NodeType& n);
       Description: Heuristic function for the search.
       Optional -- If not provided, a zero heuristic is assumed. */
    
    double getHeuristics (myNode& n) {
        double dx = goal_node.x - n.x;
        double dy = goal_node.y - n.y;
        return (sqrt(dx*dx + dy*dy)); // Euclidean heuristic function
    }
};

// ==============================================================================

int main(int argc, char *argv[])
{
    searchProblem test_search_problem; // declare an instance of the search problem.
    test_search_problem.search(); // execute search.
    
    // get path from start to goal vertex.
    std::vector<myNode*> path = test_search_problem.reconstruct_pointer_path (test_search_problem.goal_node);
    
    // print path
    printf ("\nPath: \n[");
    for (int a=path.size()-1; a>=0; --a) {
        std::cout << "[" << path[a]->x << ", " << path[a]->y << "]";
        if (a>0) std::cout << "; ";
        else std::cout << "]\n\n";
    }
    
    return (1);
}