Note we will implement both forward and backward methods. In the implementation code, first we initiliaze the static constants POS_INF and NEG_INF.
\include "dp.h" double DP::NEG_INF = -1.0e+7; double DP::POS_INF = 1.0e+7;
and set up or usual overloaded stream operators:
istream& operator>>(istream& in, DP& A)
{A.grab(in); return(in);}
istream& operator>>(istream& in, DP* A)
{A->grab(in); return(in);}
ostream& operator<<(ostream& out,const DP& A)
{A.print(out); return(out);}
ostream& operator<<(ostream& out,const DP* A)
{A->print(out); return(out);}
where we simply stub the grab method as it is not very useful to us at this point and we use the print method to simply output the underlying graph G in the DP object.
istream& DP::grab(istream& input)
{
//stub as not implemented
cout << "This overloaded operator is not implemented." << endl;
exit(1);
}
ostream& DP::print(ostream& output) const
{
output << "Graph: " << endl;
output << *G << endl;
return output;
}
There is no need to explicitly call destructors of the underlying graph object G .
DP::~DP()
{
//stub
}
next, we build a variety of methods that enable us to either get or alter node data fields. These methods require explicit casts to the type of Node Struct we are using. Note that the access methods are not needed here.
double DP::get_node_value(Gnode* gnode)
{
DPNodeStruct *T = (DPNodeStruct *)(G->node_data(gnode));
return (T->value);
}
void DP::load_node_value(Gnode* gnode,double x)
{
( (DPNodeStruct *)(G->node_data(gnode)) )->value = x;
}
double DP::get_previous_node_value(Gnode* gnode)
{
DPNodeStruct *T = (DPNodeStruct *)(G->node_data(gnode));
return (T->previous_value);
}
void DP::load_previous_node_value(Gnode* gnode,double x)
{
( (DPNodeStruct *)(G->node_data(gnode)) )->previous_value = x;
}
Gedge * DP::get_control(Gnode* gnode)
{
DPNodeStruct *T = (DPNodeStruct *)(G->node_data(gnode));
return (T->control);
}
void DP::load_control(Gnode* gnode,Gedge *choice)
{
( (DPNodeStruct *)(G->node_data(gnode)) )->control = choice;
}
These methods required that we add a new method to the graph class:
Arbent node_data(Gnode *gnode){ return gnode->data;};
The forward and backward dynamic programming algorithms are straightforward to build within this graph context as we have easy to use iterator tools to help us with our graph traversals. Roughly speaking, the backward algorithm works like this (the forward algorithm can be described in a similar way. We start with the backward_solve method: first, we do some initializations:
void DP::backward_solve(double DP_Tolerance,const int Loop_Size,char *goal)
{
int check = 0;
//set initial node values
int NumberNodes = G->NumberNodes();
DPNodeStruct *node_data = new DPNodeStruct[NumberNodes];
for(int i = 0;i< NumberNodes; ++i){
node_data[i].value = 1.0e+7;
node_data[i].previous_value = 1.0e+7;
node_data[i].control = NULL;
}
//Fill Node Data
G->FillNodeData(node_data,sizeof(DPNodeStruct));
Note that here we use a new graph method, FillNodeData(). The original FillData() was split into the two methods FillNodeData() and FillEdgeData() as the DP class needed these operations to be done separately. The need code is quite similar:
Graph& Graph::FillNodeData(Arbent node_data,int size_node)
{
int check = 0;
int i = 0;
GnodePtrBagIter nit(nodes());
for( ; nit; ++nit){
nit()->node_access->entry(&(nit()->data),node_data + i*size_node);
if(check==1)
nit()->node_access->show(cout,nit()->data);
++i;
}
return *this;
}
Graph& Graph::FillEdgeData(Arbent edge_data,int size_edge)
{
int i = 0;
for(GedgePtrBagIter eit(edges());eit;++eit){
eit()->edge_access->entry(&(eit()->data), edge_data + i*size_edge);
eit()->edge_access->show(cout,eit()->data);
++i;
}
return *this;
}
and we must add these two methods to the header file of course.
Next, we set the goal cost to 0.0.
//set goal node cost load_node_value(G->findNode(goal),0.0); load_previous_node_value(G->findNode(goal),0.0);
Then we begin the loop which will sweep through all the nodes in the graph and call the backward_value_iteration method which implements the standard dynamic programming node update algorithm.
//dp iteration
int finish = 1;
Gnode *Stop;
Stop = G->findNode(goal);
Gnode *T;
int tau = 0;
while(tau<Loop_Size && finish == 1){
finish = 0;
//do value iteration pass
backward_value_iteration(goal);
GnodePtrBagIter nit(G->nodes());
double diff;
double max_diff = 0.0;
for(; nit; ++nit){
T = nit();
if(T!=Stop){
diff = fabs(get_node_value(T) - get_previous_node_value(T));
if(diff > max_diff)
max_diff = diff;
if( diff > DP_Tolerance )
finish = 1;
}
}
++tau;
}
}
We use a while loop to call the backward_value_iteration method on the goal node. Each time it is called, we then use the node iterator to compute the largest difference between the old and current node values and make a decision about whether we should continue another step.
for(; nit; ++nit){
T = nit();
if(T!=Stop){
//get differnece between old and current node value
diff = fabs(get_node_value(T) - get_previous_node_value(T));
//set max_diff to largest individual difference for graph
if(diff > max_diff)
max_diff = diff;
//if any diff is bigger than stopping tolerance, we set finish to
//1 so while loop will continue
if( diff > DP_Tolerance )
finish = 1;
}
}
The backward_value_iteration method uses the edge iterators we have made part of our general graph class object.
void DP::backward_value_iteration(char *goal)
{
Gnode *T;
for(GnodePtrBagIter nit(G->nodes()); nit; ++nit){
T = nit();
if(!(T==G->findNode(goal)) ){
//compute local minimum calculation
backward_local_min(T);
}
}
}
The term G- >nodes() returns the bag of nodes for this graph G. We then iterate over the nodes and call the backward_local_min method. Note we don't call the backward_local_min method for the goal node. Now to implement the backward_local_min method, we will need edge iterators.
void DP::backward_local_min(Gnode* gnode)
{
double path_cost;
double min = POS_INF;
double current_value = get_node_value(gnode);
for(GedgePtrBagIter it(gnode->edges()); it;++it){
//set to and from node
Gnode *to_node = it()->to();
Gnode *from_node = it()->from();
if(from_node==gnode){
path_cost = it()->weight()+get_node_value(to_node);
if(path_cost>=POS_INF) path_cost = POS_INF;
if(path_cost < min ){
min = path_cost;
load_control(gnode,it());
}
}
}
load_previous_node_value(gnode,current_value);
load_node_value(gnode,min);
}end{listing}
\noindent
Let's look at this code closely:
first, consider the line:
\begin{verbatim}
for(GedgePtrBagIter it(gnode->edges()); it;++it){
}
Each node has a bag of edges associated with it which are stored every time we use the addEdge() graph method. So above, we set up an iterator to cylce over all the edges associated with this node. Now each such edge has a from and a to node which we can grab using the methods:
Gnode *to_node = it()->to();
Gnode *from_node = it()->from();
Now for backward dynamic programming, we need to look at the successor set of nodes associated with the given node. Hence, we only want to look at the edges in the edge bag whose from node matches the given node. So we test the from node:
if(from_node==gnode){
..further tests
}
Finally, if we have found the right edge, we calculate the new path cost, see if it is an improvement and if so update the control for this node.
path_cost = it()->weight()+get_node_value(to_node);
if(path_cost>=POS_INF) path_cost = POS_INF;
if(path_cost < min ){
min = path_cost;
load_control(gnode,it());
}
Let's see it all together now:
for(GedgePtrBagIter it(gnode->edges()); it;++it){
//set to and from node
Gnode *to_node = it()->to();
Gnode *from_node = it()->from();
if(from_node==gnode){
path_cost = it()->weight()+get_node_value(to_node);
if(path_cost>=POS_INF) path_cost = POS_INF;
if(path_cost < min ){
min = path_cost;
load_control(gnode,it());
}
}
}
As mentioned earlier, we can explain the forward algorithm in a similar way. The source for the three required methods is listed below:
void DP::forward_local_min(Gnode* gnode)
{
double path_cost;
double min = POS_INF;
double current_value = get_node_value(gnode);
char *start = "n1";
for(GedgePtrBagIter it(gnode->edges()); it;++it){
//set to and from node
Gnode *to_node = it()->to();
Gnode *from_node = it()->from();
if(to_node==gnode){
path_cost = it()->weight()+get_node_value(from_node);
if(path_cost>=POS_INF) path_cost = POS_INF;
if(path_cost < min ){
min = path_cost;
load_control(gnode,it());
}
}
}
load_previous_node_value(gnode,current_value);
load_node_value(gnode,min);
}
void DP::forward_value_iteration(char *start)
{
int check = 0;
Gnode *T;
for(GnodePtrBagIter nit(G->nodes()); nit; ++nit){
T = nit();
if( !(T==G->findNode(start)) ){
//compute local minimum calculation
forward_local_min(T);
}
}
}
void DP::forward_solve(double DP_Tolerance,const int Loop_Size,char *start)
{
//set initial node values
int NumberNodes = G->NumberNodes();
DPNodeStruct *node_data = new DPNodeStruct[NumberNodes];
for(int i = 0;i< NumberNodes; ++i){
node_data[i].value = 1.0e+7;
node_data[i].previous_value = 1.0e+7;
node_data[i].control = NULL;
}
//Fill Node Data
G->FillNodeData(node_data,sizeof(DPNodeStruct));
//set start node cost
load_node_value(G->findNode(start),0.0);
load_previous_node_value(G->findNode(start),0.0);
//dp iteration
int finish = 1;
Gnode *Stop;
Stop = G->findNode(start);
Gnode *T;
int tau = 0;
while(tau<Loop_Size && finish == 1){
finish = 0;
//do value iteration pass
forward_value_iteration(start);
GnodePtrBagIter nit(G->nodes());
double diff;
double max_diff = 0.0;
for(; nit; ++nit){
T = nit();
if(T!=Stop){
diff = fabs(get_node_value(T) - get_previous_node_value(T));
if(diff > max_diff)
max_diff = diff;
if( diff > DP_Tolerance )
finish = 1;
}
}
cout << "Maximum Node Value Difference = " << max_diff << endl;
++tau;
}
}
Finally, there is the need to print out the optimal paths. The next two methods print out ASCII versions of this information. Later, we will implement the methods to draw the optimal path information in the GUI window.
void DP::BackwardPathPrint(Gnode *start,Gnode *goal)
{
cout << "Start Node: " << start->name() << endl;
cout << "Optimal Path Cost Start to Goal " << goal->name() << " is "
<< get_node_value(start) << endl;
cout << "Path to Goal is: " << endl;
cout << start->name();
Gedge *next = get_control(start);
while(next!=NULL){
cout << "--" << next->weight() << "-->" << next->to()->name();
if(next->to()==goal) break;
next = get_control(next->to());
}
cout << endl;
}
void DP::ForwardPathPrint(Gnode *start,Gnode *goal)
{
cout << "Start Node: " << start->name() << endl;
cout << "Optimal Path Cost Start to Goal " << goal->name() << " is "
<< get_node_value(goal) << endl;
cout << "Path to Goal is: " << endl;
cout << goal->name();
Gedge *next = get_control(goal);
while(next!=NULL){
cout << "--" << next->weight() << "-->" << next->from()->name();
if(next->from()==start) break;
next = get_control(next->from());
}
cout << endl;
}