lib/fpa/Filters/DijkstraBase.hxx

   1 // =========================================================================
   2 // @author Leonardo Florez Valencia
   3 // @email florez-l@javeriana.edu.co
   4 // =========================================================================
   5 #ifndef __fpa__Filters__DijkstraBase__hxx__
   6 #define __fpa__Filters__DijkstraBase__hxx__
   7
   8 #include <algorithm>
   9 #include <limits>
  10
  11 // -------------------------------------------------------------------------
  12 template< class _TTraits >
  13 void fpa::Filters::DijkstraBase< _TTraits >::
  14 SetWeightFunction( TScalarWeight* w )
  15 {
  16   if( this->m_ScalarWeight.GetPointer( ) != w )
  17   {
  18     this->_Deassociate( this->m_ScalarWeight );
  19     this->m_ScalarWeight = w;
  20     this->_Associate( this->m_ScalarWeight );
  21     this->Modified( );
  22
  23   } // fi
  24 }
  25
  26 // -------------------------------------------------------------------------
  27 template< class _TTraits >
  28 void fpa::Filters::DijkstraBase< _TTraits >::
  29 SetWeightFunction( TVertexWeight* w )
  30 {
  31   if( this->m_VertexWeight.GetPointer( ) != w )
  32   {
  33     this->_Deassociate( this->m_VertexWeight );
  34     this->m_VertexWeight = w;
  35     this->_Associate( this->m_VertexWeight );
  36     this->Modified( );
  37
  38   } // fi
  39 }
  40
  41 // -------------------------------------------------------------------------
  42 template< class _TTraits >
  43 fpa::Filters::DijkstraBase< _TTraits >::
  44 DijkstraBase( )
  45   : Superclass( )
  46 {
  47   this->SetInitValue( TOutputValue( 0 ) );
  48 }
  49
  50 // -------------------------------------------------------------------------
  51 template< class _TTraits >
  52 fpa::Filters::DijkstraBase< _TTraits >::
  53 ~DijkstraBase( )
  54 {
  55 }
  56
  57 // -------------------------------------------------------------------------
  58 template< class _TTraits >
  59 void fpa::Filters::DijkstraBase< _TTraits >::
  60 _UpdateOutputValue( TNode& n )
  61 {
  62   // Do nothing
  63 }
  64
  65 // -------------------------------------------------------------------------
  66 template< class _TTraits >
  67 void fpa::Filters::DijkstraBase< _TTraits >::
  68 _QueueClear( )
  69 {
  70   this->m_Queue.clear( );
  71 }
  72
  73 // -------------------------------------------------------------------------
  74 template< class _TTraits >
  75 typename fpa::Filters::DijkstraBase< _TTraits >::
  76 TNode fpa::Filters::DijkstraBase< _TTraits >::
  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 _TTraits >
  89 void fpa::Filters::DijkstraBase< _TTraits >::
  90 _QueuePush( const TNode& n )
  91 {
  92   bool push_needed =  ( n.Parent == n.Vertex );
  93   push_needed     |= !( n.Value < this->_GetOutputValue( n.Parent ) );
  94   if( push_needed )
  95   {
  96     this->m_Queue.push_back( n );
  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 _TTraits >
 106 unsigned long fpa::Filters::DijkstraBase< _TTraits >::
 107 _QueueSize( ) const
 108 {
 109   return( this->m_Queue.size( ) );
 110 }
 111
 112 // -------------------------------------------------------------------------
 113 template< class _TTraits >
 114 void fpa::Filters::DijkstraBase< _TTraits >::
 115 _ComputeOutputValue( TNode& n )
 116 {
 117   if( this->m_VertexWeight.IsNotNull( ) )
 118   {
 119     TOutputValue c = this->m_VertexWeight->Evaluate( n.Vertex, n.Parent );
 120     if( this->m_ScalarWeight.IsNotNull( ) )
 121       c = this->m_ScalarWeight->Evaluate( c );
 122     n.Value = c + this->_GetOutputValue( n.Parent );
 123   }
 124   else
 125     n.Value = TOutputValue( -1 );
 126 }
 127
 128 #endif // __fpa__Filters__DijkstraBase__hxx__
 129 // eof - $RCSfile$