Algorithm Alley
by Timothy Rolfe


Listing One
class CGraph
  {
     ...
     protected:
     ...
        CEdge**  *m_Road;      // Dynamic 2-d array of pointers
        CVertex  *m_City;      // Dynamic array of vertices
        CPair    *m_Sequence;  // Sequence of edges
        int       m_Size;      // Number of cities
        int       m_NRoads;    // Number of roads
        int       m_NextEdge;  // Used in filling m_Sequence
  };


Listing Two
// Recursive Depth-First Traversal
void CGraph::depthRecur ( int Src, int Dst )
{  CPair Edge(Src, Dst);
   m_Sequence[m_NextEdge++] = Edge;
// Save position in the list
   m_City[Dst].setFlag(m_NextEdge);
   Src = Dst;        // Check outbound edges
   for ( Dst = 0; Dst < m_Size; Dst++ )
      if ( m_Road[Src][Dst] != NULL )
      {  int Flag = m_City[Dst].getFlag();
         if (Flag == Unvisited )
            depthRecur (Src, Dst);
      }
}

Listing Three
// Breadth-First Traversal
void CGraph::breadth1st ( int First )
{  CPair Edge;
   Deque Work;
   Edge.set(-1, First); // Pseudo-edge for entry point
   Work.enqueue(Edge);
// remove returns "true" if the operation succeeds
   while ( Work.remove(Edge) )
   {  int Src = Edge.get1(),
          Dst = Edge.get2();
      if ( m_City[Dst].getFlag() != Unvisited )
         continue;      // Already done.  Get next one
      m_Sequence[m_NextEdge++] = Edge;
//    Save position in the list
      m_City[Dst].setFlag(m_NextEdge);
      Src = Dst;        // Check outbound edges
      for ( Dst = 0; Dst < m_Size; Dst++ )
         if ( m_Road[Src][Dst] != NULL )
         {  int Flag = m_City[Dst].getFlag();
            Edge.set(Src, Dst);
            if ( Flag == Unvisited )
            {  Work.enqueue(Edge); }
         }
   }
}

Listing Four
class Deque   // Double-ended queue (stack AND queue behaviors)
{  public:
      Deque (void): m_Front(NULL), m_Back(NULL) { }
     ~Deque (void);     // Return dynamic memory allocations
      void push(const CPair&);     // Stack discipline
      void enqueue(const CPair&);  // Queue discipline
      bool remove (CPair&);        // Single removal point
      bool empty(void) { return m_Front == NULL; }
   private:
      struct DQnode
      {  CPair   m_Edge;
         DQnode *m_Next;
         DQnode(const CPair &V, DQnode *Nxt = NULL)
         :  m_Edge(V), m_Next(Nxt)  {  }
      };
      DQnode *m_Front, *m_Back;
};

Listing Five
class MinHeap // Priority queue with smallest entry at root
{ public:
      MinHeap(int Size = 0);
     ~MinHeap(void);
      void enter (const CPair&, int);
      bool remove(CPair&, int &);
      int  empty(void) { return m_N == 0; }
   private:
      struct MinHnode
      {  CPair m_Edge;
         int   m_Dist;
      };
      void  upHeap (int P);  // Correct from P upwards
      void downHeap(int P);  // Correct from P downwards
      MinHnode *m_Heap;      // Dynamic array
      int m_Size;            // Physical size (allocated cells)
      int m_N;               // Logical size (cells in use)
};

Listing Six  
void CGraph::Dijkstra ( int First )
{  CPair    Edge;
   MinHeap  Work;
   int      Distance = 0;
// Zero distance to the starting city, of course!
   m_City[First].setDistance(0);
   Edge.set(-1, First); // Pseudo-edge for entry point
   Work.enter(Edge, Distance);
// remove returns "true" if the operation succeeds
   while ( Work.remove(Edge, Distance) )
   {  int Src = Edge.get1(),
          Dst = Edge.get2();
      if ( m_City[Dst].getFlag() != Unvisited )
         continue;      // Already done.  Get next one
      m_Sequence[m_NextEdge++] = Edge;
//    Save position in the list
      m_City[Dst].setFlag(m_NextEdge);
      Src = Dst;        // Check outbound edges
      for ( Dst = 0; Dst < m_Size; Dst++ )
         if ( m_Road[Src][Dst] != NULL )
         {  int Flag = m_City[Dst].getFlag();
            Edge.set(Src, Dst);
            Distance = m_Road[Src][Dst]->length();
            Distance += m_City[Src].getDistance();
//          setFlags initializes distances to MAX_INT
            if ( Flag == Unvisited &&
                 m_City[Dst].getDistance() > Distance)
            {//Enter the edge; update to the shorter distance
               Work.enter(Edge, Distance);
               m_City[Dst].setDistance(Distance);
            }
         }
   }
}

Listing Seven
//  All-Paths Algorithm 
//  Based on Program 8-4 in J. L. Antonakos and K. C. Mansfield, 
// "Practical Data Structures Using C/C++" (1999), pp. 268-69.
void CGraphAll::allPaths(int Src, int Dst)
{  int ChkWt = ( m_Road[Src][Dst] != NULL ?
                 m_Road[Src][Dst]->length() : 0 );
   if ( ChkWt > 0 )     // Does the path terminate at Dst?
   {//Enter final edge into the sequence
      m_Sequence[m_NextEdge++] = CPair(Src, Dst);
      edgeList(cout);
      m_NextEdge--;     // Remove edge from the sequence
   }
   for (int k=0; k<m_Size; k++)   // Check all edges from Src
   {  ChkWt = ( m_Road[Src][k] != NULL ?
                m_Road[Src][k]->length() : 0 );
      if ( ChkWt > 0 )            // this IS an unused edge
      {//Enter this edge into the sequence
         m_Sequence[m_NextEdge++] = CPair(Src, k);
//       [Src][k] AND [k][Src] reference the SAME object
         *m_Road[Src][k] *= -1;   // Mark edge as used
         allPaths ( k, Dst );     // Recursive call
         *m_Road[Src][k] *= -1;   // Mark edge as UNused
         m_NextEdge--;            // Remove this edge
      }
   }
}

Listing Eight 
// Traveling Salesman Problem Solution
void CGraphAll::travelSales(int Src, int Dst)
{  int ChkWt = ( m_Road[Src][Dst] != NULL ?
                 m_Road[Src][Dst]->length() : 0 );
   if ( ChkWt > 0 )     // Does the path terminate at Dst?
   {  bool Found = true;
      m_City[Dst].incFlag();
      for ( k = 0; Found && k < m_Size; k++ )
      {  Found = Found && m_City[k].getFlag()!=Unvisited; }
      if ( Found )
      {  m_Sequence[m_NextEdge++] = CPair(Src, Dst);
         minSeq(0);     // Update minimum sequence
         m_NextEdge--;
      }
   }
   for (int k=0; k<m_Size; k++)   // Check all edges from Src
   {  ChkWt = ( m_Road[Src][k] != NULL ?
                m_Road[Src][k]->length() : 0 );

      if ( ChkWt > 0 )            // This IS an unused edge.
      {  m_City[k].incFlag();     // Count UP on flag use
         m_Sequence[m_NextEdge++] = CPair(Src, k);
//       [Src][k] AND [k][Src] reference the SAME object
         *m_Road[Src][k] *= -1;   // Mark edges as used
         travelSales ( k, Dst );  // Recursive call
         *m_Road[Src][k] *= -1;   // Mark edges as UNused
         m_NextEdge--;            // Remove from path
         m_City[k].decFlag();     // Back off on flag use
      }
   }
}









1

