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
  92   this->_BeforeMainLoop( );
  93   this->_InitializeMarks( );
  94   this->_InitializeResults( );
  95   this->_InitializeQueue( );
  96   this->_Loop( );
  97   this->_AfterMainLoop( );
  98 }
  99
 100 // -------------------------------------------------------------------------
 101 template< class T, class B >
 102 void fpa::Base::Algorithm< T, B >::
 103 _BeforeMainLoop( )
 104 {
 105 }
 106
 107 // -------------------------------------------------------------------------
 108 template< class T, class B >
 109 void fpa::Base::Algorithm< T, B >::
 110 _AfterMainLoop( )
 111 {
 112 }
 113
 114 // -------------------------------------------------------------------------
 115 template< class T, class B >
 116 void fpa::Base::Algorithm< T, B >::
 117 _BeforeLoop( )
 118 {
 119 }
 120
 121 // -------------------------------------------------------------------------
 122 template< class T, class B >
 123 void fpa::Base::Algorithm< T, B >::
 124 _AfterLoop( )
 125 {
 126 }
 127
 128 // -------------------------------------------------------------------------
 129 template< class T, class B >
 130 void fpa::Base::Algorithm< T, B >::
 131 _Loop( )
 132 {
 133   this->_BeforeLoop( );
 134   while( !( this->_IsQueueEmpty( ) ) )
 135   {
 136     _TNode n = this->_QueuePop( );
 137     if( this->_IsMarked( n.Vertex ) )
 138       continue;
 139
 140     this->_Mark( n );
 141     this->InvokeEvent( TMarkEvent( n ) );
 142     if( this->_UpdateResult( n ) )
 143     {
 144       if( !( this->_CheckStopCondition( ) ) )
 145       {
 146         _TNodes N;
 147         this->_Neighs( n, N );
 148         typename _TNodes::iterator nnIt = N.begin( );
 149         while( nnIt != N.end( ) )
 150         {
 151           if( this->_IsMarked( nnIt->Vertex ) )
 152           {
 153             // Update real front identifier
 154             nnIt->FrontId = this->_FrontId( nnIt->Vertex );
 155
 156             // Update collisions
 157             if( this->_CheckCollisions( n, *nnIt ) )
 158             {
 159               if( this->m_StopAtOneFront )
 160               {
 161                 this->_QueueClear( );
 162                 nnIt = N.end( );
 163
 164               } // fi
 165
 166             } // fi
 167           }
 168           else
 169           {
 170             if( this->_UpdateNeigh( *nnIt, n ) )
 171             {
 172               nnIt->Parent = n.Vertex;
 173               this->_QueuePush( *nnIt );
 174               this->InvokeEvent( TFrontEvent( *nnIt ) );
 175
 176             } // fi
 177
 178           } // fi
 179           if( nnIt != N.end( ) )
 180             nnIt++;
 181
 182         } // elihw
 183       }
 184       else
 185         this->_QueueClear( );
 186
 187     } // fi
 188
 189   } // elihw
 190   this->InvokeEvent( TEndEvent( ) );
 191   this->_AfterLoop( );
 192 }
 193
 194 // -------------------------------------------------------------------------
 195 template< class T, class B >
 196 bool fpa::Base::Algorithm< T, B >::
 197 _CheckCollisions( const _TNode& a, const _TNode& b )
 198 {
 199   bool ret = false;
 200   if( a.FrontId != b.FrontId )
 201   {
 202     // Mark collision, if it is new
 203     bool exists = this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second;
 204     exists     &= this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second;
 205     if( !exists )
 206     {
 207       this->m_CollisionSites[ a.FrontId ][ b.FrontId ].first = a.Vertex;
 208       this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second = true;
 209       this->m_CollisionSites[ b.FrontId ][ a.FrontId ].first = b.Vertex;
 210       this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second = true;
 211
 212       // Stop if one front is desired
 213       if( this->m_StopAtOneFront )
 214       {
 215         // Perform a depth-first iteration on front graph
 216         unsigned long N = this->GetNumberOfSeeds( );
 217         unsigned long C = 0;
 218         std::vector< bool > m( N, false );
 219         std::queue< unsigned long > q;
 220         q.push( 0 );
 221         while( !q.empty( ) )
 222         {
 223           unsigned long f = q.front( );
 224           q.pop( );
 225
 226           if( m[ f ] )
 227             continue;
 228           m[ f ] = true;
 229           C++;
 230
 231           for( unsigned int n = 0; n < N; ++n )
 232             if( this->m_CollisionSites[ f ][ n ].second && !m[ n ] )
 233               q.push( n );
 234
 235         } // elihw
 236         ret = ( C == N );
 237
 238       } // fi
 239
 240     } // fi
 241
 242   } // fi
 243   return( ret );
 244 }
 245
 246 // -------------------------------------------------------------------------
 247 template< class T, class B >
 248 bool fpa::Base::Algorithm< T, B >::
 249 _CheckStopCondition( )
 250 {
 251   return( false );
 252 }
 253
 254 // -------------------------------------------------------------------------
 255 template< class T, class B >
 256 bool fpa::Base::Algorithm< T, B >::
 257 _UpdateResult( _TNode& n )
 258 {
 259   return( true );
 260 }
 261
 262 // -------------------------------------------------------------------------
 263 template< class T, class B >
 264 void fpa::Base::Algorithm< T, B >::
 265 _InitializeMarks( )
 266 {
 267   this->m_Marks.clear( );
 268 }
 269
 270 // -------------------------------------------------------------------------
 271 template< class T, class B >
 272 bool  fpa::Base::Algorithm< T, B >::
 273 _IsMarked( const TVertex& v ) const
 274 {
 275   return( this->m_Marks.find( v ) != this->m_Marks.end( ) );
 276 }
 277
 278 // -------------------------------------------------------------------------
 279 template< class T, class B >
 280 typename fpa::Base::Algorithm< T, B >::
 281 _TFrontId fpa::Base::Algorithm< T, B >::
 282 _FrontId( const TVertex& v ) const
 283 {
 284   typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
 285   if( mIt != this->m_Marks.end( ) )
 286     return( mIt->second.FrontId );
 287   else
 288     return( std::numeric_limits< _TFrontId >::max( ) );
 289 }
 290
 291 // -------------------------------------------------------------------------
 292 template< class T, class B >
 293 typename fpa::Base::Algorithm< T, B >::
 294 TVertex fpa::Base::Algorithm< T, B >::
 295 _Parent( const TVertex& v ) const
 296 {
 297   typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
 298   if( mIt == this->m_Marks.end( ) )
 299     return( TVertex( ) );
 300   else
 301     return( mIt->second.Parent );
 302 }
 303
 304 // -------------------------------------------------------------------------
 305 template< class T, class B >
 306 void  fpa::Base::Algorithm< T, B >::
 307 _Mark( const _TNode& n )
 308 {
 309   this->m_Marks[ n.Vertex ] = n;
 310 }
 311
 312 #endif // __FPA__BASE__ALGORITHM__HXX__
 313
 314 // eof - $RCSfile$