lib/fpa/Base/Dijkstra.hxx

   1 #ifndef __FPA__BASE__DIJKSTRA__HXX__
   2 #define __FPA__BASE__DIJKSTRA__HXX__
   3
   4 #include <algorithm>
   5
   6 // -------------------------------------------------------------------------
   7 template< class V, class C, class R, class VC, class B >
   8 fpa::Base::Dijkstra< V, C, R, VC, B >::
   9 Dijkstra( )
  10   : Superclass( )
  11 {
  12 }
  13
  14 // -------------------------------------------------------------------------
  15 template< class V, class C, class R, class VC, class B >
  16 fpa::Base::Dijkstra< V, C, R, VC, B >::
  17 ~Dijkstra( )
  18 {
  19 }
  20
  21 // -------------------------------------------------------------------------
  22 template< class V, class C, class R, class VC, class B >
  23 bool fpa::Base::Dijkstra< V, C, R, VC, B >::
  24 _ComputeNeighborResult(
  25   TResult& result, const TVertex& neighbor, const TVertex& parent
  26   ) const
  27 {
  28   result  = this->_Cost( neighbor, parent );
  29   result *= TResult( this->_Distance( neighbor, parent ) );
  30
  31   // WARNING: Dijkstra does not work on negative values!
  32   if( result >= TResult( 0 ) )
  33   {
  34     _TNode pn = this->_Node( parent );
  35     if( pn.Label == Self::AliveLabel )
  36       result += pn.Result;
  37     return( true );
  38   }
  39   else
  40     return( false );
  41 }
  42
  43 // -------------------------------------------------------------------------
  44 template< class V, class C, class R, class VC, class B >
  45 bool fpa::Base::Dijkstra< V, C, R, VC, B >::
  46 _IsQueueEmpty( ) const
  47 {
  48   return( this->m_Queue.empty( ) );
  49 }
  50
  51 // -------------------------------------------------------------------------
  52 template< class V, class C, class R, class VC, class B >
  53 void fpa::Base::Dijkstra< V, C, R, VC, B >::
  54 _QueuePush( const TVertex& v, const _TNode& n )
  55 {
  56   _TQueueNode qn;
  57   qn.Vertex = v;
  58   qn.Node = n;
  59   this->m_Queue.push_back( qn );
  60   std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
  61 }
  62
  63 // -------------------------------------------------------------------------
  64 template< class V, class C, class R, class VC, class B >
  65 void fpa::Base::Dijkstra< V, C, R, VC, B >::
  66 _QueuePop( TVertex& v, _TNode& n )
  67 {
  68   _TQueueNode qn = this->m_Queue.front( );
  69   std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
  70   this->m_Queue.pop_back( );
  71   v = qn.Vertex;
  72   n = qn.Node;
  73 }
  74
  75 // -------------------------------------------------------------------------
  76 template< class V, class C, class R, class VC, class B >
  77 void fpa::Base::Dijkstra< V, C, R, VC, B >::
  78 _QueueClear( )
  79 {
  80   this->m_Queue.clear( );
  81 }
  82
  83 #endif // __FPA__BASE__DIJKSTRA__HXX__
  84
  85 // eof - $RCSfile$