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