lib/fpa/Base/Algorithm.hxx

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