lib/fpa/Base/Dijkstra.hxx

   1 #ifndef __FPA__BASE__DIJKSTRA__HXX__
   2 #define __FPA__BASE__DIJKSTRA__HXX__
   3
   4 #include <algorithm>
   5
   6 // -------------------------------------------------------------------------
   7 template< class V, class C, class R, class S, class VC, class MST, class B >
   8 typename fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
   9 TMinimumSpanningTree* fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
  10 GetMinimumSpanningTree( )
  11 {
  12   return(
  13     dynamic_cast< TMinimumSpanningTree* >(
  14       this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
  15       )
  16     );
  17 }
  18
  19 // -------------------------------------------------------------------------
  20 template< class V, class C, class R, class S, class VC, class MST, class B >
  21 const typename fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
  22 TMinimumSpanningTree* fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
  23 GetMinimumSpanningTree( ) const
  24 {
  25   return(
  26     dynamic_cast< const TMinimumSpanningTree* >(
  27       this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
  28       )
  29     );
  30 }
  31
  32 // -------------------------------------------------------------------------
  33 template< class V, class C, class R, class S, class VC, class MST, class B >
  34 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
  35 GraftMinimumSpanningTree( itk::DataObject* obj )
  36 {
  37   TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
  38   if( mst != NULL )
  39     this->GraftNthOutput( this->m_MSTIdx, mst );
  40 }
  41
  42 // -------------------------------------------------------------------------
  43 template< class V, class C, class R, class S, class VC, class MST, class B >
  44 fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
  45 Dijkstra( )
  46   : Superclass( ),
  47     m_LocalCosts( false ),
  48     m_FillNodeQueue( false )
  49 {
  50   this->m_MSTIdx = this->GetNumberOfRequiredOutputs( );
  51   this->SetNumberOfRequiredOutputs( this->m_MSTIdx + 1 );
  52   this->itk::ProcessObject::SetNthOutput(
  53     this->m_MSTIdx, TMinimumSpanningTree::New( )
  54     );
  55 }
  56
  57 // -------------------------------------------------------------------------
  58 template< class V, class C, class R, class S, class VC, class MST, class B >
  59 fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
  60 ~Dijkstra( )
  61 {
  62 }
  63
  64 // -------------------------------------------------------------------------
  65 template< class V, class C, class R, class S, class VC, class MST, class B >
  66 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
  67 _BeforeGenerateData( )
  68 {
  69   this->Superclass::_BeforeGenerateData( );
  70   this->GetMinimumSpanningTree( )->SetFillNodeQueue( this->m_FillNodeQueue );
  71 }
  72
  73 // -------------------------------------------------------------------------
  74 template< class V, class C, class R, class S, class VC, class MST, class B >
  75 bool fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
  76 _ComputeNeighborResult(
  77   TResult& result, const TVertex& neighbor, const TVertex& parent
  78   ) const
  79 {
  80   result  = this->_Cost( neighbor, parent );
  81   result *= TResult( this->_Distance( neighbor, parent ) );
  82
  83   // WARNING: Dijkstra does not work on negative values!
  84   if( result >= TResult( 0 ) )
  85   {
  86     _TNode pn = this->_Node( parent );
  87     if( pn.Label == Self::AliveLabel && !this->m_LocalCosts )
  88       result += pn.Result;
  89     return( true );
  90   }
  91   else
  92     return( false );
  93 }
  94
  95 // -------------------------------------------------------------------------
  96 template< class V, class C, class R, class S, class VC, class MST, class B >
  97 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
  98 _SetResult( const TVertex& v, const _TNode& n )
  99 {
 100   this->GetMinimumSpanningTree( )->SetNode( v, n.Parent, n.FrontId, n.Result );
 101 }
 102
 103 // -------------------------------------------------------------------------
 104 template< class V, class C, class R, class S, class VC, class MST, class B >
 105 bool fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
 106 _IsQueueEmpty( ) const
 107 {
 108   return( this->m_Queue.empty( ) );
 109 }
 110
 111 // -------------------------------------------------------------------------
 112 template< class V, class C, class R, class S, class VC, class MST, class B >
 113 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
 114 _QueuePush( const TVertex& v, const _TNode& n )
 115 {
 116   _TQueueNode qn;
 117   qn.Vertex = v;
 118   qn.Node = n;
 119   this->m_Queue.push_back( qn );
 120   std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
 121 }
 122
 123 // -------------------------------------------------------------------------
 124 template< class V, class C, class R, class S, class VC, class MST, class B >
 125 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
 126 _QueuePop( TVertex& v, _TNode& n )
 127 {
 128   _TQueueNode qn = this->m_Queue.front( );
 129   std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
 130   this->m_Queue.pop_back( );
 131   v = qn.Vertex;
 132   n = qn.Node;
 133 }
 134
 135 // -------------------------------------------------------------------------
 136 template< class V, class C, class R, class S, class VC, class MST, class B >
 137 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
 138 _QueueClear( )
 139 {
 140   this->m_Queue.clear( );
 141 }
 142
 143 #endif // __FPA__BASE__DIJKSTRA__HXX__
 144
 145 // eof - $RCSfile$