Run-Time Results:

Consider as application code our usual callback function run() altered to set up and compute optimal paths in a graph using dynamic programming.

  ...usual startup code
  
  //instantiate the access functions
  ACCESS_DPEDGESTRUCT *EdgeAccess = new ACCESS_DPEDGESTRUCT;
  ACCESS_DPNODESTRUCT *NodeAccess = new ACCESS_DPNODESTRUCT;
            
  //construct Graph 
  if(T->T==NULL){
    printf("Building the Graph object.\n");
    T->T = new Graph(EdgeAccess,NodeAccess,
                     T->radius,T->center,        //node circle
                     T->foreground,              //fg
                     T->background,              //bg
                     graph_colors,               //graph colors
                     T->display,                 //graphics
                     T->drawable,
                     T->pixmap,
                     T->pixmap2,
                     T->gc);          
    }
  
  //Construct RandomGraph
  cout << "Generating Random Graph" << endl;
  T->T->GenerateRandomGraph("RandomGraph");
  	     
  //Read in Random Graph
  cout << "Reading Random Graph from file" << endl;   
  T->T->ReadInputFile("RandomGraph");  
   
  int NumberNodes = T->T->NumberNodes();
  int NumberEdges = T->T->NumberEdges();
  cout << "Number of Nodes in the Graph is " << NumberNodes << endl;
  cout << "Number of Edges in the Graph is " << NumberEdges << endl;
  
  //initialize EdgeData
  DPEdgeStruct * EdgeData = new DPEdgeStruct[NumberEdges];
  for(int i=0;i<NumberEdges;++i)
    EdgeData[i] .time = 1.0;
  T->T->FillEdgeData(EdgeData,sizeof(DPEdgeStruct));

  //Construct DP object
  DP dp(T->T);
  
  char start_name[20];
  char goal_name[20];
  char prefix = 'n';
   
  sprintf(start_name,"%c%d",prefix,1);
  sprintf(goal_name,"%c%d",prefix,NumberNodes);
  
  Gnode *start = T->T->findNode(start_name);
  Gnode *goal = T->T->findNode(goal_name);
                            
  //Call Backward DP and print final path
  dp.backward_solve(0.0001,10,goal_name);
  dp.BackwardPathPrint(start,goal);
  
  //Call Forward DP and print final path
  dp.forward_solve(0.0001,10,start_name);
  dp.ForwardPathPrint(start,goal);
   
  //initialize pixmaps and compute image
  T->T->erase(T->pixmap);
  T->T->draw(T->pixmap);
  T->T->erase(T->pixmap2);
  T->T->draw(T->pixmap2);
  image(w,T);
}

That's all there is to it! The run-time output is as follows:

Building the Graph object.
Generating Random Graph
How many nodes do you want in the graph?
26
You have chosen 26 for this graph
We will generate a random number of edges between nodes. 
This number will be between a lower and upper bound.
Enter the lower bound for the number of edges:
3
Enter the upper bound for the number of edges:
5
Your design parameter is 3 < number of edges < 5
We will generate a random edge weight between chosen nodes.
This number will be between a lower and upper bound.
Enter the lower bound for the edge weight:
0.5
Enter the upper bound for the edge weight:
12.5
Your design parameter is 0.5 < edge_weight < 12.5
number_of_nodes = 26
Reading Random Graph from file
number_of_nodes = 26
number_of_edges = 92

*************************************************  
**   Backward value iteration pass 0           **
*************************************************

Maximum Node Value Difference = 1e+07
*************************************************  
**   Backward value iteration pass 1           **
*************************************************

Maximum Node Value Difference = 9.99999e+06
*************************************************  
**   Backward value iteration pass 2           **
*************************************************

Maximum Node Value Difference = 9.99998e+06
*************************************************
**  Backward value iteration pass 3            **
*************************************************

Maximum Node Value Difference = 9.99997e+06
*************************************************
**  Backward value iteration pass 4            **
*************************************************

Maximum Node Value Difference = 3.31903
*************************************************
**  Backward value iteration pass 5            **
*************************************************

Maximum Node Value Difference = 0
Start Node: n1
Optimal Path Cost Start to Goal n26 is 28.6879
Path to Goal is: 
n1--5.34375-->n25--1.89138-->n14--1.90485-->
n4--7.58231-->n11--7.35726-->n2--4.60837-->n26


**************************************************
**  Forward value iteration pass 0              **
**************************************************

Maximum Node Value Difference = 9.99999e+06
**************************************************
**  Forward value iteration pass 1              **
**************************************************

Maximum Node Value Difference = 9.99999e+06
**************************************************
**  Forward value iteration pass 2              **
**************************************************

Maximum Node Value Difference = 9.99998e+06
**************************************************
**  Forward value iteration pass 3              **
**************************************************

Maximum Node Value Difference = 0
Start Node: n1
Optimal Path Cost Start to Goal n26 is 28.6879
Path to Goal is: 
n26--4.60837-->n2--7.35726-->n11--7.58231-->
n4--1.90485-->n14--1.89138-->n25--5.34375-->n1

The objects make it easy to set up the problem.