lib/fpa/Base/DijkstraBase.hxx

   1 // =========================================================================
   2 // @author Leonardo Florez Valencia
   3 // @email florez-l@javeriana.edu.co
   4 // =========================================================================
   5
   6 #ifndef __fpa__Base__DijkstraBase__hxx__
   7 #define __fpa__Base__DijkstraBase__hxx__
   8
   9 #include <algorithm>
  10 #include <limits>
  11
  12 // -------------------------------------------------------------------------
  13 template< class _TAlgorithm >
  14 itk::ModifiedTimeType fpa::Base::DijkstraBase< _TAlgorithm >::
  15 GetMTime( ) const
  16 {
  17   itk::ModifiedTimeType t = this->Superclass::GetMTime( );
  18   if( this->m_WeightFunction.IsNotNull( ) )
  19   {
  20     itk::ModifiedTimeType q = this->m_WeightFunction->GetMTime( );
  21     t = ( q < t )? q: t;
  22
  23   } // fi
  24   return( t );
  25 }
  26
  27 // -------------------------------------------------------------------------
  28 template< class _TAlgorithm >
  29 fpa::Base::DijkstraBase< _TAlgorithm >::
  30 DijkstraBase( )
  31   : Superclass( )
  32 {
  33   this->SetInitValue( std::numeric_limits< TOutputValue >::max( ) );
  34 }
  35
  36 // -------------------------------------------------------------------------
  37 template< class _TAlgorithm >
  38 fpa::Base::DijkstraBase< _TAlgorithm >::
  39 ~DijkstraBase( )
  40 {
  41 }
  42
  43 // -------------------------------------------------------------------------
  44 template< class _TAlgorithm >
  45 typename fpa::Base::DijkstraBase< _TAlgorithm >::
  46 TOutputValue fpa::Base::DijkstraBase< _TAlgorithm >::
  47 _ComputeOutputValue( const TNode& n )
  48 {
  49   TOutputValue c = this->m_WeightFunction->Evaluate( n.Vertex, n.Parent );
  50   return( c + this->_GetOutputValue( n.Parent ) );
  51 }
  52
  53 // -------------------------------------------------------------------------
  54 template< class _TAlgorithm >
  55 void fpa::Base::DijkstraBase< _TAlgorithm >::
  56 _QueueInit( )
  57 {
  58   typedef typename Superclass::TSeedsInterface::TSeeds::iterator _TIt;
  59
  60   this->Superclass::_QueueInit( );
  61   for( _TIt sIt = this->BeginSeeds( ); sIt != this->EndSeeds( ); ++sIt )
  62     sIt->Value = TOutputValue( 0 );
  63 }
  64
  65 // -------------------------------------------------------------------------
  66 template< class _TAlgorithm >
  67 void fpa::Base::DijkstraBase< _TAlgorithm >::
  68 _QueueClear( )
  69 {
  70   this->m_Queue.clear( );
  71 }
  72
  73 // -------------------------------------------------------------------------
  74 template< class _TAlgorithm >
  75 typename fpa::Base::DijkstraBase< _TAlgorithm >::
  76 TNode fpa::Base::DijkstraBase< _TAlgorithm >::
  77 _QueuePop( )
  78 {
  79   std::pop_heap(
  80     this->m_Queue.begin( ), this->m_Queue.end( ), this->m_QueueOrder
  81     );
  82   TNode n = this->m_Queue.back( );
  83   this->m_Queue.pop_back( );
  84   return( n );
  85 }
  86
  87 // -------------------------------------------------------------------------
  88 template< class _TAlgorithm >
  89 void fpa::Base::DijkstraBase< _TAlgorithm >::
  90 _QueuePush( const TNode& node )
  91 {
  92   bool push_needed =  ( node.Parent == node.Vertex );
  93   push_needed     |= !( node.Value < this->_GetOutputValue( node.Parent ) );
  94   if( push_needed )
  95   {
  96     this->m_Queue.push_back( node );
  97     std::push_heap(
  98       this->m_Queue.begin( ), this->m_Queue.end( ), this->m_QueueOrder
  99       );
 100
 101   } // fi
 102 }
 103
 104 // -------------------------------------------------------------------------
 105 template< class _TAlgorithm >
 106 unsigned long fpa::Base::DijkstraBase< _TAlgorithm >::
 107 _QueueSize( ) const
 108 {
 109   return( this->m_Queue.size( ) );
 110 }
 111
 112 #endif // __fpa__Base__DijkstraBase__hxx__
 113
 114 // eof - $RCSfile$