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 VV, class VC, class B >
   8 fpa::Base::Dijkstra< V, C, VV, VC, B >::
   9 Dijkstra( )
  10   : Superclass( )
  11 {
  12 }
  13
  14 // -------------------------------------------------------------------------
  15 template< class V, class C, class VV, class VC, class B >
  16 fpa::Base::Dijkstra< V, C, VV, VC, B >::
  17 ~Dijkstra( )
  18 {
  19 }
  20
  21 // -------------------------------------------------------------------------
  22 template< class V, class C, class VV, class VC, class B >
  23 void fpa::Base::Dijkstra< V, C, VV, VC, B >::
  24 _InitializeQueue( )
  25 {
  26   for(
  27     typename _TNodes::const_iterator vIt = this->m_Seeds.begin( );
  28     vIt != this->m_Seeds.end( );
  29     vIt++
  30     )
  31     this->_QueuePush( *vIt );
  32 }
  33
  34 // -------------------------------------------------------------------------
  35 template< class V, class C, class VV, class VC, class B >
  36 bool fpa::Base::Dijkstra< V, C, VV, VC, B >::
  37 _IsQueueEmpty( ) const
  38 {
  39   return( this->m_Queue.empty( ) );
  40 }
  41
  42 // -------------------------------------------------------------------------
  43 template< class V, class C, class VV, class VC, class B >
  44 void fpa::Base::Dijkstra< V, C, VV, VC, B >::
  45 _QueuePush( const _TNode& n )
  46 {
  47   this->m_Queue.push_back( n );
  48   std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
  49 }
  50
  51 // -------------------------------------------------------------------------
  52 template< class V, class C, class VV, class VC, class B >
  53 typename fpa::Base::Dijkstra< V, C, VV, VC, B >::
  54 _TNode fpa::Base::Dijkstra< V, C, VV, VC, B >::
  55 _QueuePop( )
  56 {
  57   _TNode n;
  58   if( !( this->m_Queue.empty( ) ) )
  59   {
  60     // n = *( this->m_Queue.begin( ) );
  61     n = this->m_Queue.front( );
  62     std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
  63     this->m_Queue.pop_back( );
  64
  65   } // fi
  66   return( n );
  67 }
  68
  69 // -------------------------------------------------------------------------
  70 template< class V, class C, class VV, class VC, class B >
  71 void fpa::Base::Dijkstra< V, C, VV, VC, B >::
  72 _QueueClear( )
  73 {
  74   this->m_Queue.clear( );
  75 }
  76
  77 // -------------------------------------------------------------------------
  78 template< class V, class C, class VV, class VC, class B >
  79 bool fpa::Base::Dijkstra< V, C, VV, VC, B >::
  80 _UpdateNeigh( _TNode& nn, const _TNode& n )
  81 {
  82   TCost nc = this->_Cost( nn.Vertex, n.Vertex );
  83   if( C( 0 ) <= nc )
  84   {
  85     nn.Cost = n.Cost + nc;
  86     nn.Result = nn.Cost;
  87     return( true );
  88   }
  89   else
  90     return( false );
  91 }
  92
  93 #endif // __FPA__BASE__DIJKSTRA__HXX__
  94
  95 // eof - $RCSfile$