lib/fpa/Base/Algorithm.hxx

   1 #ifndef __FPA__BASE__ALGORITHM__HXX__
   2 #define __FPA__BASE__ALGORITHM__HXX__
   3
   4 #include <algorithm>
   5 #include <limits>
   6 #include <queue>
   7
   8 // -------------------------------------------------------------------------
   9 template< class T, class B >
  10 void fpa::Base::Algorithm< T, B >::
  11 InvokeEvent( const itk::EventObject& e )
  12 {
  13   if( this->m_ThrowEvents )
  14     this->Superclass::InvokeEvent( e );
  15 }
  16
  17 // -------------------------------------------------------------------------
  18 template< class T, class B >
  19 void fpa::Base::Algorithm< T, B >::
  20 InvokeEvent( const itk::EventObject& e ) const
  21 {
  22   if( this->m_ThrowEvents )
  23     this->Superclass::InvokeEvent( e );
  24 }
  25
  26 // -------------------------------------------------------------------------
  27 template< class T, class B >
  28 void fpa::Base::Algorithm< T, B >::
  29 AddSeed( const TVertex& s, const TResult& v )
  30 {
  31   this->m_Seeds.push_back( _TNode( s, v, this->m_Seeds.size( ) ) );
  32   this->Modified( );
  33 }
  34
  35 // -------------------------------------------------------------------------
  36 template< class T, class B >
  37 const typename fpa::Base::Algorithm< T, B >::
  38 TVertex& fpa::Base::Algorithm< T, B >::
  39 GetSeed( const unsigned long& i ) const
  40 {
  41   return( this->m_Seeds[ i ].Vertex );
  42 }
  43
  44 // -------------------------------------------------------------------------
  45 template< class T, class B >
  46 void fpa::Base::Algorithm< T, B >::
  47 ClearSeeds( )
  48 {
  49   this->m_Seeds.clear( );
  50   this->Modified( );
  51 }
  52
  53 // -------------------------------------------------------------------------
  54 template< class T, class B >
  55 unsigned long fpa::Base::Algorithm< T, B >::
  56 GetNumberOfSeeds( ) const
  57 {
  58   return( this->m_Seeds.size( ) );
  59 }
  60
  61 // -------------------------------------------------------------------------
  62 template< class T, class B >
  63 fpa::Base::Algorithm< T, B >::
  64 Algorithm( )
  65   : Superclass( ),
  66     m_StopAtOneFront( false ),
  67     m_ThrowEvents( false )
  68 {
  69 }
  70
  71 // -------------------------------------------------------------------------
  72 template< class T, class B >
  73 fpa::Base::Algorithm< T, B >::
  74 ~Algorithm( )
  75 {
  76 }
  77
  78 // -------------------------------------------------------------------------
  79 template< class T, class B >
  80 void fpa::Base::Algorithm< T, B >::
  81 GenerateData( )
  82 {
  83   this->AllocateOutputs( );
  84
  85   unsigned long N = this->m_Seeds.size( );
  86   if( N == 0 )
  87     return;
  88   this->m_CollisionSites.clear( );
  89   this->m_CollisionSites.
  90     resize( N, _TCollisionSitesRow( N, _TCollision( TVertex( ), false ) ) );
  91   this->_BeforeLoop( );
  92   this->_Loop( );
  93   this->_AfterLoop( );
  94 }
  95
  96 // -------------------------------------------------------------------------
  97 template< class T, class B >
  98 void fpa::Base::Algorithm< T, B >::
  99 _BeforeLoop( )
 100 {
 101 }
 102
 103 // -------------------------------------------------------------------------
 104 template< class T, class B >
 105 void fpa::Base::Algorithm< T, B >::
 106 _AfterLoop( )
 107 {
 108 }
 109
 110 // -------------------------------------------------------------------------
 111 template< class T, class B >
 112 void fpa::Base::Algorithm< T, B >::
 113 _Loop( )
 114 {
 115   this->_InitializeMarks( );
 116   this->_InitializeResults( );
 117   this->_InitializeQueue( );
 118   while( !( this->_IsQueueEmpty( ) ) )
 119   {
 120     _TNode n = this->_QueuePop( );
 121     if( this->_IsMarked( n.Vertex ) )
 122       continue;
 123
 124     this->_Mark( n );
 125     this->InvokeEvent( TMarkEvent( n ) );
 126     if( this->_UpdateResult( n ) )
 127     {
 128       if( !( this->_CheckStopCondition( ) ) )
 129       {
 130         _TNodes N;
 131         this->_Neighs( n, N );
 132         typename _TNodes::iterator nnIt = N.begin( );
 133         while( nnIt != N.end( ) )
 134         {
 135           if( this->_IsMarked( nnIt->Vertex ) )
 136           {
 137             // Update real front identifier
 138             nnIt->FrontId = this->_FrontId( nnIt->Vertex );
 139
 140             // Update collisions
 141             if( this->_CheckCollisions( n, *nnIt ) )
 142             {
 143               if( this->m_StopAtOneFront )
 144               {
 145                 this->_QueueClear( );
 146                 nnIt = N.end( );
 147
 148               } // fi
 149
 150             } // fi
 151           }
 152           else
 153           {
 154             if( this->_UpdateNeigh( *nnIt, n ) )
 155             {
 156               nnIt->Parent = n.Vertex;
 157               this->_QueuePush( *nnIt );
 158               this->InvokeEvent( TFrontEvent( *nnIt ) );
 159
 160             } // fi
 161
 162           } // fi
 163           if( nnIt != N.end( ) )
 164             nnIt++;
 165
 166         } // elihw
 167       }
 168       else
 169         this->_QueueClear( );
 170
 171     } // fi
 172
 173   } // elihw
 174   this->InvokeEvent( TEndEvent( ) );
 175 }
 176
 177 // -------------------------------------------------------------------------
 178 template< class T, class B >
 179 bool fpa::Base::Algorithm< T, B >::
 180 _CheckCollisions( const _TNode& a, const _TNode& b )
 181 {
 182   bool ret = false;
 183   if( a.FrontId != b.FrontId )
 184   {
 185     // Mark collision, if it is new
 186     bool exists = this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second;
 187     exists     &= this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second;
 188     if( !exists )
 189     {
 190       this->m_CollisionSites[ a.FrontId ][ b.FrontId ].first = a.Vertex;
 191       this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second = true;
 192       this->m_CollisionSites[ b.FrontId ][ a.FrontId ].first = b.Vertex;
 193       this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second = true;
 194
 195       // Stop if one front is desired
 196       if( this->m_StopAtOneFront )
 197       {
 198         // Perform a depth-first iteration on front graph
 199         unsigned long N = this->GetNumberOfSeeds( );
 200         unsigned long C = 0;
 201         std::vector< bool > m( N, false );
 202         std::queue< unsigned long > q;
 203         q.push( 0 );
 204         while( !q.empty( ) )
 205         {
 206           unsigned long f = q.front( );
 207           q.pop( );
 208
 209           if( m[ f ] )
 210             continue;
 211           m[ f ] = true;
 212           C++;
 213
 214           for( unsigned int n = 0; n < N; ++n )
 215             if( this->m_CollisionSites[ f ][ n ].second && !m[ n ] )
 216               q.push( n );
 217
 218         } // elihw
 219         ret = ( C == N );
 220
 221       } // fi
 222
 223     } // fi
 224
 225   } // fi
 226   return( ret );
 227 }
 228
 229 // -------------------------------------------------------------------------
 230 template< class T, class B >
 231 bool fpa::Base::Algorithm< T, B >::
 232 _CheckStopCondition( )
 233 {
 234   return( false );
 235 }
 236
 237 // -------------------------------------------------------------------------
 238 template< class T, class B >
 239 bool fpa::Base::Algorithm< T, B >::
 240 _UpdateResult( _TNode& n )
 241 {
 242   return( true );
 243 }
 244
 245 // -------------------------------------------------------------------------
 246 template< class T, class B >
 247 void fpa::Base::Algorithm< T, B >::
 248 _InitializeMarks( )
 249 {
 250   this->m_Marks.clear( );
 251 }
 252
 253 // -------------------------------------------------------------------------
 254 template< class T, class B >
 255 bool  fpa::Base::Algorithm< T, B >::
 256 _IsMarked( const TVertex& v ) const
 257 {
 258   return( this->m_Marks.find( v ) != this->m_Marks.end( ) );
 259 }
 260
 261 // -------------------------------------------------------------------------
 262 template< class T, class B >
 263 typename fpa::Base::Algorithm< T, B >::
 264 _TFrontId fpa::Base::Algorithm< T, B >::
 265 _FrontId( const TVertex& v ) const
 266 {
 267   typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
 268   if( mIt != this->m_Marks.end( ) )
 269     return( mIt->second.FrontId );
 270   else
 271     return( std::numeric_limits< _TFrontId >::max( ) );
 272 }
 273
 274 // -------------------------------------------------------------------------
 275 template< class T, class B >
 276 typename fpa::Base::Algorithm< T, B >::
 277 TVertex fpa::Base::Algorithm< T, B >::
 278 _Parent( const TVertex& v ) const
 279 {
 280   typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
 281   if( mIt == this->m_Marks.end( ) )
 282   {
 283     TVertex v;
 284     return( v );
 285   }
 286   else
 287     return( mIt->second.Parent );
 288 }
 289
 290 // -------------------------------------------------------------------------
 291 template< class T, class B >
 292 void  fpa::Base::Algorithm< T, B >::
 293 _Mark( const _TNode& n )
 294 {
 295   this->m_Marks[ n.Vertex ] = n;
 296 }
 297
 298 #endif // __FPA__BASE__ALGORITHM__HXX__
 299
 300 // eof - $RCSfile$