lib/fpa/Base/Dijkstra.hxx

   1 #ifndef __fpa__Base__Dijkstra__hxx__
   2 #define __fpa__Base__Dijkstra__hxx__
   3
   4 #include <algorithm>
   5 #include <limits>
   6
   7 // -------------------------------------------------------------------------
   8 template< class _TSuperclass, class _TMST >
   9 _TMST* fpa::Base::Dijkstra< _TSuperclass, _TMST >::
  10 GetMinimumSpanningTree( )
  11 {
  12   return(
  13     dynamic_cast< _TMST* >(
  14       this->itk::ProcessObject::GetOutput( this->m_MSTIndex )
  15       )
  16     );
  17 }
  18
  19 // -------------------------------------------------------------------------
  20 template< class _TSuperclass, class _TMST >
  21 const _TMST* fpa::Base::Dijkstra< _TSuperclass, _TMST >::
  22 GetMinimumSpanningTree( ) const
  23 {
  24   return(
  25     dynamic_cast< const _TMST* >(
  26       this->itk::ProcessObject::GetOutput( this->m_MSTIndex )
  27       )
  28     );
  29 }
  30
  31 // -------------------------------------------------------------------------
  32 template< class _TSuperclass, class _TMST >
  33 fpa::Base::Dijkstra< _TSuperclass, _TMST >::
  34 Dijkstra( )
  35   : Superclass( )
  36 {
  37   this->m_InitResult = TOutput( 0 );
  38   this->m_MSTIndex = this->GetNumberOfRequiredOutputs( );
  39   this->SetNumberOfRequiredOutputs( this->m_MSTIndex + 1 );
  40   this->itk::ProcessObject::SetNthOutput( this->m_MSTIndex, _TMST::New( ) );
  41 }
  42
  43 // -------------------------------------------------------------------------
  44 template< class _TSuperclass, class _TMST >
  45 fpa::Base::Dijkstra< _TSuperclass, _TMST >::
  46 ~Dijkstra( )
  47 {
  48 }
  49
  50 // -------------------------------------------------------------------------
  51 template< class _TSuperclass, class _TMST >
  52 void fpa::Base::Dijkstra< _TSuperclass, _TMST >::
  53 _AfterGenerateData( )
  54 {
  55   this->Superclass::_AfterGenerateData( );
  56
  57   auto mst = this->GetMinimumSpanningTree( );
  58   mst->ClearSeeds( );
  59   for( auto s = this->m_Seeds.begin( ); s != this->m_Seeds.end( ); ++s )
  60     mst->AddSeed( s->Vertex );
  61   mst->SetCollisions( this->m_Collisions );
  62 }
  63
  64 // -------------------------------------------------------------------------
  65 template< class _TSuperclass, class _TMST >
  66 void fpa::Base::Dijkstra< _TSuperclass, _TMST >::
  67 _UpdateResult( const _TQueueNode& n )
  68 {
  69   this->Superclass::_UpdateResult( n );
  70   this->GetMinimumSpanningTree( )->SetParent( n.Vertex, n.Parent );
  71 }
  72
  73 // -------------------------------------------------------------------------
  74 template< class _TSuperclass, class _TMST >
  75 bool fpa::Base::Dijkstra< _TSuperclass, _TMST >::
  76 _UpdateValue( _TQueueNode& v, const _TQueueNode& p )
  77 {
  78   v.Result = this->m_CostFunction->Evaluate( p.Vertex, v.Vertex );
  79   if( this->m_CostConversionFunction.IsNotNull( ) )
  80     v.Result = this->m_CostConversionFunction->Evaluate( v.Result );
  81   if( v.Result >= TOutput( 0 ) )
  82   {
  83     v.Result += p.Result;
  84     return( true );
  85   }
  86   else
  87   {
  88     v.Result = this->m_InitResult;
  89     return( false );
  90
  91   } // fi
  92 }
  93
  94 // -------------------------------------------------------------------------
  95 template< class _TSuperclass, class _TMST >
  96 unsigned long fpa::Base::Dijkstra< _TSuperclass, _TMST >::
  97 _QueueSize( ) const
  98 {
  99   return( this->m_Queue.size( ) );
 100 }
 101
 102 // -------------------------------------------------------------------------
 103 template< class _TSuperclass, class _TMST >
 104 void fpa::Base::Dijkstra< _TSuperclass, _TMST >::
 105 _QueueClear( )
 106 {
 107   this->m_Queue.clear( );
 108 }
 109
 110 // -------------------------------------------------------------------------
 111 template< class _TSuperclass, class _TMST >
 112 void fpa::Base::Dijkstra< _TSuperclass, _TMST >::
 113 _QueuePush( const _TQueueNode& node )
 114 {
 115   static _TQueueNodeCompare cmp;
 116   this->m_Queue.push_back( node );
 117   std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ), cmp );
 118 }
 119
 120 // -------------------------------------------------------------------------
 121 template< class _TSuperclass, class _TMST >
 122 typename fpa::Base::Dijkstra< _TSuperclass, _TMST >::
 123 _TQueueNode fpa::Base::Dijkstra< _TSuperclass, _TMST >::
 124 _QueuePop( )
 125 {
 126   static _TQueueNodeCompare cmp;
 127   std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ), cmp );
 128   _TQueueNode f = this->m_Queue.back( );
 129   this->m_Queue.pop_back( );
 130   return( f );
 131 }
 132
 133 #endif // __fpa__Base__Dijkstra__hxx__
 134
 135 // eof - $RCSfile$