lib/fpa/Base/Algorithm.hxx

   1 #ifndef __FPA__BASE__ALGORITHM__HXX__
   2 #define __FPA__BASE__ALGORITHM__HXX__
   3
   4 #include <queue>
   5 #include <itkProcessObject.h>
   6
   7 // -------------------------------------------------------------------------
   8 template< class V, class C, class R, class S, class VC, class B >
   9 fpa::Base::Algorithm< V, C, R, S, VC, B >::_TNode::
  10 _TNode( )
  11   : Result( TResult( 0 ) ),
  12     FrontId( -1 ),
  13     Label( Self::FarLabel )
  14 {
  15 }
  16
  17 // -------------------------------------------------------------------------
  18 template< class V, class C, class R, class S, class VC, class B >
  19 fpa::Base::Algorithm< V, C, R, S, VC, B >::_TNode::
  20 ~_TNode( )
  21 {
  22 }
  23
  24 // -------------------------------------------------------------------------
  25 template< class V, class C, class R, class S, class VC, class B >
  26 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
  27 InvokeEvent( const itk::EventObject& e )
  28 {
  29   if( this->m_ThrowEvents )
  30     this->Superclass::InvokeEvent( e );
  31 }
  32
  33 // -------------------------------------------------------------------------
  34 template< class V, class C, class R, class S, class VC, class B >
  35 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
  36 InvokeEvent( const itk::EventObject& e ) const
  37 {
  38   if( this->m_ThrowEvents )
  39     this->Superclass::InvokeEvent( e );
  40 }
  41
  42 // -------------------------------------------------------------------------
  43 template< class V, class C, class R, class S, class VC, class B >
  44 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
  45 AddSeed( const TVertex& s, const TResult& r )
  46 {
  47   _TNode ns;
  48   ns.Parent = s;
  49   ns.Result = r;
  50   ns.FrontId = this->m_SeedVertices.size( );
  51   ns.Label = Self::FrontLabel;
  52   this->m_Seeds[ s ] = ns;
  53   this->m_SeedVertices.push_back( s );
  54   this->Modified( );
  55 }
  56
  57 // -------------------------------------------------------------------------
  58 template< class V, class C, class R, class S, class VC, class B >
  59 const typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
  60 TVertex& fpa::Base::Algorithm< V, C, R, S, VC, B >::
  61 GetSeed( const unsigned int& id ) const
  62 {
  63   return( this->m_SeedVertices[ id ] );
  64 }
  65
  66 // -------------------------------------------------------------------------
  67 template< class V, class C, class R, class S, class VC, class B >
  68 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
  69 ClearSeeds( )
  70 {
  71   this->m_Seeds.clear( );
  72   this->m_SeedVertices.clear( );
  73   this->Modified( );
  74 }
  75
  76 // -------------------------------------------------------------------------
  77 template< class V, class C, class R, class S, class VC, class B >
  78 unsigned long fpa::Base::Algorithm< V, C, R, S, VC, B >::
  79 GetNumberOfSeeds( ) const
  80 {
  81   return( this->m_Seeds.size( ) );
  82 }
  83
  84 // -------------------------------------------------------------------------
  85 template< class V, class C, class R, class S, class VC, class B >
  86 fpa::Base::Algorithm< V, C, R, S, VC, B >::
  87 Algorithm( )
  88   : Superclass( ),
  89     m_ThrowEvents( false ),
  90     m_StopAtOneFront( false )
  91 {
  92 }
  93
  94 // -------------------------------------------------------------------------
  95 template< class V, class C, class R, class S, class VC, class B >
  96 fpa::Base::Algorithm< V, C, R, S, VC, B >::
  97 ~Algorithm( )
  98 {
  99 }
 100
 101 // -------------------------------------------------------------------------
 102 template< class V, class C, class R, class S, class VC, class B >
 103 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
 104 GenerateData( )
 105 {
 106   unsigned long N = this->m_Seeds.size( );
 107   if( N == 0 )
 108     return;
 109
 110   this->InvokeEvent( TStartEvent( ) );
 111   this->_BeforeGenerateData( );
 112
 113   this->m_Collisions.clear( );
 114   this->m_Collisions.
 115     resize( N, _TCollisionsRow( N, _TCollision( TVertex( ), false ) ) );
 116   this->_InitResults( );
 117   this->_InitMarks( );
 118   this->_InitQueue( );
 119   this->_Loop( );
 120   this->_AfterGenerateData( );
 121   this->InvokeEvent( TEndEvent( ) );
 122 }
 123
 124 // -------------------------------------------------------------------------
 125 template< class V, class C, class R, class S, class VC, class B >
 126 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
 127 _Loop( )
 128 {
 129   this->InvokeEvent( TStartLoopEvent( ) );
 130   this->_BeforeLoop( );
 131   while( !( this->_IsQueueEmpty( ) ) )
 132   {
 133     // Get next candidate
 134     TVertex vertex;
 135     _TNode node;
 136     this->_QueuePop( vertex, node );
 137     if( this->_Node( vertex ).Label == Self::AliveLabel )
 138       continue;
 139
 140     // Mark it as "Alive" and update final result
 141     node.Label = Self::AliveLabel;
 142     this->_Mark( vertex, node );
 143     this->_SetResult( vertex, node );
 144     this->InvokeEvent( TAliveEvent( vertex, node.FrontId ) );
 145
 146     // Check if a forced stop condition arises
 147     if( !( this->_NeedToStop( ) ) )
 148     {
 149       // Compute neighborhood
 150       _TVertices neighborhood;
 151       this->_Neighborhood( neighborhood, vertex );
 152
 153       // Iterate over neighbors
 154       typename _TVertices::iterator nIt = neighborhood.begin( );
 155       while( nIt != neighborhood.end( ) )
 156       {
 157         _TNode neighbor = this->_Node( *nIt );
 158         if( neighbor.Label == Self::AliveLabel )
 159         {
 160           // Update collisions
 161           if( this->_UpdateCollisions( vertex, *nIt ) )
 162           {
 163             this->_QueueClear( );
 164             nIt = neighborhood.end( );
 165             continue;
 166
 167           } // fi
 168         }
 169         else
 170         {
 171           // Add new candidate to queue
 172           if( this->_ComputeNeighborResult( neighbor.Result, *nIt, vertex ) )
 173           {
 174             neighbor.FrontId = node.FrontId;
 175             neighbor.Parent = vertex;
 176             neighbor.Label = Self::FrontLabel;
 177             this->_QueuePush( *nIt, neighbor );
 178             this->_Mark( *nIt, neighbor );
 179             this->InvokeEvent( TFrontEvent( *nIt, node.FrontId ) );
 180           }
 181           else
 182             this->InvokeEvent( TFreezeEvent( *nIt, node.FrontId ) );
 183
 184         } // fi
 185         ++nIt;
 186
 187       } // elihw
 188     }
 189     else
 190       this->_QueueClear( );
 191
 192   } // elihw
 193   this->_AfterLoop( );
 194   this->InvokeEvent( TEndLoopEvent( ) );
 195 }
 196
 197 // -------------------------------------------------------------------------
 198 template< class V, class C, class R, class S, class VC, class B >
 199 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
 200 _BeforeGenerateData( )
 201 {
 202 }
 203
 204 // -------------------------------------------------------------------------
 205 template< class V, class C, class R, class S, class VC, class B >
 206 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
 207 _AfterGenerateData( )
 208 {
 209 }
 210
 211 // -------------------------------------------------------------------------
 212 template< class V, class C, class R, class S, class VC, class B >
 213 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
 214 _BeforeLoop( )
 215 {
 216 }
 217
 218 // -------------------------------------------------------------------------
 219 template< class V, class C, class R, class S, class VC, class B >
 220 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
 221 _AfterLoop( )
 222 {
 223 }
 224
 225 // -------------------------------------------------------------------------
 226 template< class V, class C, class R, class S, class VC, class B >
 227 bool fpa::Base::Algorithm< V, C, R, S, VC, B >::
 228 _UpdateCollisions( const TVertex& a, const TVertex& b )
 229 {
 230   bool ret = false;
 231   _TNode na = this->_Node( a );
 232   _TNode nb = this->_Node( b );
 233   long fa = na.FrontId;
 234   long fb = nb.FrontId;
 235
 236   if( fa != fb )
 237   {
 238     // Mark collision, if it is new
 239     bool exists = this->m_Collisions[ fa ][ fb ].second;
 240     exists     &= this->m_Collisions[ fb ][ fa ].second;
 241
 242     if( !exists )
 243     {
 244       this->m_Collisions[ fa ][ fb ].first = a;
 245       this->m_Collisions[ fa ][ fb ].second = true;
 246       this->m_Collisions[ fb ][ fa ].first = b;
 247       this->m_Collisions[ fb ][ fa ].second = true;
 248
 249       // Stop if one front is desired
 250       if( this->m_StopAtOneFront )
 251       {
 252         // Perform a depth-first iteration on front graph
 253         unsigned long N = this->GetNumberOfSeeds( );
 254         unsigned long count = 0;
 255         std::vector< bool > m( N, false );
 256         std::queue< unsigned long > q;
 257         q.push( 0 );
 258         while( !q.empty( ) )
 259         {
 260           unsigned long f = q.front( );
 261           q.pop( );
 262
 263           if( m[ f ] )
 264             continue;
 265           m[ f ] = true;
 266           count++;
 267
 268           for( unsigned int n = 0; n < N; ++n )
 269             if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
 270               q.push( n );
 271
 272         } // elihw
 273         ret = ( count == N );
 274
 275       } // fi
 276
 277     } // fi
 278
 279   } // fi
 280   return( ret );
 281 }
 282
 283 // -------------------------------------------------------------------------
 284 template< class V, class C, class R, class S, class VC, class B >
 285 bool fpa::Base::Algorithm< V, C, R, S, VC, B >::
 286 _NeedToStop( ) const
 287 {
 288   return( false );
 289 }
 290
 291 // -------------------------------------------------------------------------
 292 template< class V, class C, class R, class S, class VC, class B >
 293 typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
 294 _TNode& fpa::Base::Algorithm< V, C, R, S, VC, B >::
 295 _Node( const TVertex& v )
 296 {
 297   typename _TNodes::iterator vIt = this->m_Marks.find( v );
 298   if( vIt == this->m_Marks.end( ) )
 299   {
 300     _TNode new_node;
 301     new_node.Parent = v;
 302     new_node.Result = TResult( 0 );
 303     new_node.FrontId = -1;
 304     new_node.Label = Self::FarLabel;
 305     this->m_Marks[ v ] = new_node;
 306     vIt = this->m_Marks.find( v );
 307
 308   } // fi
 309   return( vIt->second );
 310 }
 311
 312 // -------------------------------------------------------------------------
 313 template< class V, class C, class R, class S, class VC, class B >
 314 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
 315 _SetResult( const TVertex& v, const _TNode& n )
 316 {
 317   // Do nothing at this hierarchy level
 318 }
 319
 320 // -------------------------------------------------------------------------
 321 template< class V, class C, class R, class S, class VC, class B >
 322 const typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
 323 _TNode& fpa::Base::Algorithm< V, C, R, S, VC, B >::
 324 _Node( const TVertex& v ) const
 325 {
 326   typename _TNodes::const_iterator vIt = this->m_Marks.find( v );
 327   return( vIt->second );
 328 }
 329
 330 // -------------------------------------------------------------------------
 331 template< class V, class C, class R, class S, class VC, class B >
 332 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
 333 _InitMarks( )
 334 {
 335   this->m_Marks.clear( );
 336 }
 337
 338 // -------------------------------------------------------------------------
 339 template< class V, class C, class R, class S, class VC, class B >
 340 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
 341 _Mark( const TVertex& v, const _TNode& node )
 342 {
 343   this->m_Marks[ v ] = node;
 344 }
 345
 346 // -------------------------------------------------------------------------
 347 template< class V, class C, class R, class S, class VC, class B >
 348 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
 349 _InitQueue( )
 350 {
 351   this->_QueueClear( );
 352   for(
 353     typename _TNodes::const_iterator sIt = this->m_Seeds.begin( );
 354     sIt != this->m_Seeds.end( );
 355     sIt++
 356     )
 357   {
 358     this->_QueuePush( sIt->first, sIt->second );
 359     this->_Mark( sIt->first, sIt->second );
 360
 361   } // rof
 362 }
 363
 364 #endif // __FPA__BASE__ALGORITHM__HXX__
 365
 366 // eof - $RCSfile$