CSC 318 -- WINDOWS PROGRAMMING WITH MFC
                      DYKSTRA PROJECT

  Goal: Implement a graphical interface for finding the single
        source shortest path using Dykstra's algorithm.

  Suggested menu entries: 

   -- File. Leave as is for if serialization is implemented.

   -- EndPoints.  Submenu items: Set Start Node, Set Destination Node.

   -- Define Nodes.  Now user clicks left mouse button to repeatedly to
      define locations of nodes.

   -- Define Edges.  Now user clicks left mouse button to select two nodes
      as start and end nodes of the edge.  A custom dialog then appears
      to allow user to enter the cost of the edge.

   -- Find Minimum Cost Path.   Performs methods DoDykstra and ShowBestPath.

  
  Here are the suggested class definitions:

  The CNode and CEdge objects defined below are added to CArray arrays in
  the view class (or into the document class if serialization is used).
  Here are suggested definitions:

  // At the top of view.h file (or document.h file if serialization is
  // used.
  #include <afxtempl.h>
  #include "Node.h"
  #include "Edge.h"

  // In view or document class definition:
  CArray<CNode, CNode&> nodearray;
  CArray<CEdge, CEdge&> edgearray;

  // In Node.h file.
  class CNode : public CObject
  {
  public:
      CPoint loc;           // Location of node on form.
      BOOL permanent;       // Set to TRUE if node made permanent.
      int total_cost;       // Current total cost from source to node.
      int prev_node_on_path;// Previous node on temporary best path.
      int n_edges_out;      // Number of edges going out from node.
      int edge_out[5]       // Indices of edges going out from node.
  public:
      void CNode(CPoint);   // Pass in location of node on form.
                            // Initialize other fields to default values.

      void ResetNode();     // Initialize nodes (except location) to 
                            //    default values.

      void Display(CDC *);  // Display node on form.
      void MakePermanent(); // Set permanent field in node to TRUE.
      void SetPrevNode(int);// Set value of prev_node_on_path.   
  };

  // In Edge.h file.
  class CEdge : public CObject   // Implements a directed edge.
  {
  public:
      int from, to;         // Edge goes from from node to to node.
      int cost;             // Cost of traversing edge.
  private:
      CEdge(int, int, int); // Pass in from and to indices and edge cost.
      void Display(CDC *);  // Display edge on form.
  };

  When an edge is referenced in a CNode object the index in the edge array
  is used. When a node is referenced in a CEdge object the index in the 
  edge array is used.

  Data members added to the view class definition:

  public:
      int startnode;           // The index of the start node.
      int destnode;            // The index of the destination node.
      int last_made_permanent; // The index of node last made permanent.
      
  Methods added to the view class

  void DoDykstra();    // perform Dykstras algorithm.  Here is suggested
                       // pseudocode.
  
  The pseudocode uses these constant definitions
  const int INFINITY = 0x7fffffff;
  const int NONE = -1;

  Check if startnode and destnode have been set.
  Set total_cost for each node in node array to INFINITY.
  Set permanent field for each node in node array to FALSE.
  Set previous_node_on_path field for each node to NONE.
  Set total_cost field for start node to 0.
  Set permanent field for start node to TRUE.
  Set last_made_permanent to startnode.

  While permanent field for node with index destnode equals FALSE

      For each edge_out of node last_made_permanent
          Update total_cost of node joined by edge_out as 
               min(current total cost of node joined by edge_out, 
                   total_cost of node with index last_made_permanent + 
                   cost of edge_out).
      End For

      Compute min_index as the index of the minimum total_cost 
          nonpermanent node.
      Set the prev_node_on_path field in the node with index min_index
          to last_made_permanent. 
      Make permanent the node with index min_index.

  End While             
                
  void ShowBestPath(); // After DoDykstra is called, show best path 
                       // computed by tracing from the destination node 
                       // back to the source node via the
                       // prev_node_on_path field in each node.

  Information will be given later on how to serialize the classes in this
  assignment.  This will give the classes the persistance property.