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 _QueueClear( )
  57 {
  58   this->m_Queue.clear( );
  59 }
  60
  61 // -------------------------------------------------------------------------
  62 template< class _TAlgorithm >
  63 typename fpa::Base::DijkstraBase< _TAlgorithm >::
  64 TNode fpa::Base::DijkstraBase< _TAlgorithm >::
  65 _QueuePop( )
  66 {
  67   std::pop_heap(
  68     this->m_Queue.begin( ), this->m_Queue.end( ), this->m_QueueOrder
  69     );
  70   TNode n = this->m_Queue.back( );
  71   this->m_Queue.pop_back( );
  72   return( n );
  73 }
  74
  75 // -------------------------------------------------------------------------
  76 template< class _TAlgorithm >
  77 void fpa::Base::DijkstraBase< _TAlgorithm >::
  78 _QueuePush( const TNode& node )
  79 {
  80   bool push_needed =  ( node.Parent == node.Vertex );
  81   push_needed     |= !( node.Value < this->_GetOutputValue( node.Parent ) );
  82   if( push_needed )
  83   {
  84     this->m_Queue.push_back( node );
  85     std::push_heap(
  86       this->m_Queue.begin( ), this->m_Queue.end( ), this->m_QueueOrder
  87       );
  88
  89   } // fi
  90 }
  91
  92 // -------------------------------------------------------------------------
  93 template< class _TAlgorithm >
  94 unsigned long fpa::Base::DijkstraBase< _TAlgorithm >::
  95 _QueueSize( ) const
  96 {
  97   return( this->m_Queue.size( ) );
  98 }
  99
 100 // -------------------------------------------------------------------------
 101 template< class _TAlgorithm >
 102 void fpa::Base::DijkstraBase< _TAlgorithm >::
 103 _PrepareSeeds( TNodes& nodes )
 104 {
 105   typename TNodes::iterator nIt = nodes.begin( );
 106   for( ; nIt != nodes.end( ); ++nIt )
 107     nIt->Value = TOutputValue( 0 );
 108 }
 109
 110 #endif // __fpa__Base__DijkstraBase__hxx__
 111
 112 // eof - $RCSfile$