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