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   this->InvokeEvent( TEndEvent( ) );
  99 }
 100
 101 // -------------------------------------------------------------------------
 102 template< class T, class B >
 103 void fpa::Base::Algorithm< T, B >::
 104 _BeforeMainLoop( )
 105 {
 106 }
 107
 108 // -------------------------------------------------------------------------
 109 template< class T, class B >
 110 void fpa::Base::Algorithm< T, B >::
 111 _AfterMainLoop( )
 112 {
 113 }
 114
 115 // -------------------------------------------------------------------------
 116 template< class T, class B >
 117 void fpa::Base::Algorithm< T, B >::
 118 _BeforeLoop( )
 119 {
 120 }
 121
 122 // -------------------------------------------------------------------------
 123 template< class T, class B >
 124 void fpa::Base::Algorithm< T, B >::
 125 _AfterLoop( )
 126 {
 127 }
 128
 129 // -------------------------------------------------------------------------
 130 template< class T, class B >
 131 void fpa::Base::Algorithm< T, B >::
 132 _Loop( )
 133 {
 134   this->_BeforeLoop( );
 135   while( !( this->_IsQueueEmpty( ) ) )
 136   {
 137     _TNode n = this->_QueuePop( );
 138     if( this->_IsMarked( n.Vertex ) )
 139       continue;
 140
 141     this->_Mark( n );
 142     this->InvokeEvent( TMarkEvent( n ) );
 143     if( this->_UpdateResult( n ) )
 144     {
 145       if( !( this->_CheckStopCondition( ) ) )
 146       {
 147         _TNodes N;
 148         this->_Neighs( n, N );
 149         typename _TNodes::iterator nnIt = N.begin( );
 150         while( nnIt != N.end( ) )
 151         {
 152           if( this->_IsMarked( nnIt->Vertex ) )
 153           {
 154             // Update real front identifier
 155             nnIt->FrontId = this->_FrontId( nnIt->Vertex );
 156
 157             // Update collisions
 158             if( this->_CheckCollisions( n, *nnIt ) )
 159             {
 160               if( this->m_StopAtOneFront )
 161               {
 162                 this->_QueueClear( );
 163                 nnIt = N.end( );
 164
 165               } // fi
 166
 167             } // fi
 168           }
 169           else
 170           {
 171             if( this->_UpdateNeigh( *nnIt, n ) )
 172             {
 173               nnIt->Parent = n.Vertex;
 174               this->_QueuePush( *nnIt );
 175               this->InvokeEvent( TFrontEvent( *nnIt ) );
 176
 177             } // fi
 178
 179           } // fi
 180           if( nnIt != N.end( ) )
 181             nnIt++;
 182
 183         } // elihw
 184       }
 185       else
 186         this->_QueueClear( );
 187
 188     } // fi
 189
 190   } // elihw
 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$