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 _TSuperclass >
   8 const typename fpa::Base::Dijkstra< _TSuperclass >::TDijkstraCmp
   9 fpa::Base::Dijkstra< _TSuperclass >::DijkstraCmp =
  10 fpa::Base::Dijkstra< _TSuperclass >::TDijkstraCmp( );
  11
  12 // -------------------------------------------------------------------------
  13 template< class _TSuperclass >
  14 typename fpa::Base::Dijkstra< _TSuperclass >::
  15 TMinimumSpanningTree* fpa::Base::Dijkstra< _TSuperclass >::
  16 GetMinimumSpanningTree( )
  17 {
  18   return(
  19     dynamic_cast< TMinimumSpanningTree* >(
  20       this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
  21       )
  22     );
  23 }
  24
  25 // -------------------------------------------------------------------------
  26 template< class _TSuperclass >
  27 const typename fpa::Base::Dijkstra< _TSuperclass >::
  28 TMinimumSpanningTree* fpa::Base::Dijkstra< _TSuperclass >::
  29 GetMinimumSpanningTree( ) const
  30 {
  31   return(
  32     dynamic_cast< const TMinimumSpanningTree* >(
  33       this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
  34       )
  35     );
  36 }
  37
  38 // -------------------------------------------------------------------------
  39 template< class _TSuperclass >
  40 void fpa::Base::Dijkstra< _TSuperclass >::
  41 GraftMinimumSpanningTree( itk::DataObject* obj )
  42 {
  43   TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
  44   if( mst != NULL )
  45     this->GraftNthOutput( this->m_MSTIdx, mst );
  46 }
  47
  48 // -------------------------------------------------------------------------
  49 template< class _TSuperclass >
  50 fpa::Base::Dijkstra< _TSuperclass >::
  51 Dijkstra( )
  52   : Superclass( ),
  53     m_CostConversionFunction( NULL )
  54 {
  55   this->m_MSTIdx = this->GetNumberOfRequiredOutputs( );
  56   this->SetNumberOfRequiredOutputs( this->m_MSTIdx + 1 );
  57   typename TMinimumSpanningTree::Pointer mst = TMinimumSpanningTree::New( );
  58   this->itk::ProcessObject::SetNthOutput( this->m_MSTIdx, mst );
  59 }
  60
  61 // -------------------------------------------------------------------------
  62 template< class _TSuperclass >
  63 fpa::Base::Dijkstra< _TSuperclass >::
  64 ~Dijkstra( )
  65 {
  66 }
  67
  68 // -------------------------------------------------------------------------
  69 template< class _TSuperclass >
  70 void fpa::Base::Dijkstra< _TSuperclass >::
  71 _AfterGenerateData( )
  72 {
  73   this->Superclass::_AfterGenerateData( );
  74   this->GetMinimumSpanningTree( )->SetCollisions( this->m_Collisions );
  75 }
  76
  77 // -------------------------------------------------------------------------
  78 template< class _TSuperclass >
  79 void fpa::Base::Dijkstra< _TSuperclass >::
  80 _Visit( const TNode& n )
  81 {
  82   this->Superclass::_Visit( n );
  83   this->GetMinimumSpanningTree( )->SetNode(
  84     n.Vertex, n.Parent, n.FrontId, n.Result
  85     );
  86 }
  87
  88 // -------------------------------------------------------------------------
  89 template< class _TSuperclass >
  90 bool fpa::Base::Dijkstra< _TSuperclass >::
  91 _Result( TNode& node, const TNode& parent )
  92 {
  93   node.Result = this->_Cost( node.Vertex, parent.Vertex );
  94   if( node.Result >= TScalar( 0 ) )
  95   {
  96     if( this->m_CostConversionFunction.IsNotNull( ) )
  97       node.Result = this->m_CostConversionFunction->Evaluate( node.Result );
  98     node.Result += parent.Result;
  99     return( true );
 100   }
 101   else
 102     return( false );
 103 }
 104
 105 // -------------------------------------------------------------------------
 106 template< class _TSuperclass >
 107 void fpa::Base::Dijkstra< _TSuperclass >::
 108 _QueueClear( )
 109 {
 110   this->m_Queue.clear( );
 111 }
 112
 113 // -------------------------------------------------------------------------
 114 template< class _TSuperclass >
 115 void fpa::Base::Dijkstra< _TSuperclass >::
 116 _QueuePush( const TNode& node )
 117 {
 118   this->m_Queue.push_back( node );
 119   std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ), DijkstraCmp );
 120 }
 121
 122 // -------------------------------------------------------------------------
 123 template< class _TSuperclass >
 124 typename fpa::Base::Dijkstra< _TSuperclass >::
 125 TNode fpa::Base::Dijkstra< _TSuperclass >::
 126 _QueuePop( )
 127 {
 128   std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ), DijkstraCmp );
 129   TNode n = this->m_Queue.back( );
 130   this->m_Queue.pop_back( );
 131   return( n );
 132 }
 133
 134 // -------------------------------------------------------------------------
 135 template< class _TSuperclass >
 136 bool fpa::Base::Dijkstra< _TSuperclass >::
 137 _IsQueueEmpty( ) const
 138 {
 139   return( this->m_Queue.size( ) == 0 );
 140 }
 141
 142 #endif // __FPA__BASE__DIJKSTRA__HXX__
 143
 144 // eof - $RCSfile$