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       while( nIt != neighborhood.end( ) )
 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             continue;
 163
 164           } // fi
 165         }
 166         else
 167         {
 168           // Add new candidate to queue
 169           if(
 170             this->_ComputeNeighborResult(
 171               neighbor.Result, *nIt, candidate.Vertex
 172               )
 173             )
 174           {
 175             neighbor.FrontId = candidate.FrontId;
 176             neighbor.Parent = candidate.Vertex;
 177             neighbor.Label = Self::FrontLabel;
 178             this->_QueuePush( neighbor );
 179             this->_Mark( neighbor );
 180             this->InvokeEvent( TFrontEvent( *nIt, candidate.FrontId ) );
 181           }
 182           else
 183             this->InvokeEvent( TFreezeEvent( *nIt, candidate.FrontId ) );
 184
 185         } // fi
 186         ++nIt;
 187
 188       } // elihw
 189     }
 190     else
 191       this->_QueueClear( );
 192
 193   } // elihw
 194   this->_AfterLoop( );
 195   this->InvokeEvent( TEndLoopEvent( ) );
 196 }
 197
 198 // -------------------------------------------------------------------------
 199 template< class V, class C, class R, class B >
 200 void fpa::Base::Algorithm< V, C, R, B >::
 201 _BeforeGenerateData( )
 202 {
 203 }
 204
 205 // -------------------------------------------------------------------------
 206 template< class V, class C, class R, class B >
 207 void fpa::Base::Algorithm< V, C, R, B >::
 208 _AfterGenerateData( )
 209 {
 210 }
 211
 212 // -------------------------------------------------------------------------
 213 template< class V, class C, class R, class B >
 214 void fpa::Base::Algorithm< V, C, R, B >::
 215 _BeforeLoop( )
 216 {
 217 }
 218
 219 // -------------------------------------------------------------------------
 220 template< class V, class C, class R, class B >
 221 void fpa::Base::Algorithm< V, C, R, B >::
 222 _AfterLoop( )
 223 {
 224 }
 225
 226 // -------------------------------------------------------------------------
 227 template< class V, class C, class R, class B >
 228 bool fpa::Base::Algorithm< V, C, R, B >::
 229 _UpdateCollisions( const TVertex& a, const TVertex& b )
 230 {
 231   bool ret = false;
 232   _TNode na = this->_Node( a );
 233   _TNode nb = this->_Node( b );
 234   long fa = na.FrontId;
 235   long fb = nb.FrontId;
 236
 237   if( fa != fb )
 238   {
 239     // Mark collision, if it is new
 240     bool exists = this->m_Collisions[ fa ][ fb ].second;
 241     exists     &= this->m_Collisions[ fb ][ fa ].second;
 242
 243     if( !exists )
 244     {
 245       this->m_Collisions[ fa ][ fb ].first = na.Vertex;
 246       this->m_Collisions[ fa ][ fb ].second = true;
 247       this->m_Collisions[ fb ][ fa ].first = nb.Vertex;
 248       this->m_Collisions[ fb ][ fa ].second = true;
 249
 250       // Stop if one front is desired
 251       if( this->m_StopAtOneFront )
 252       {
 253         // Perform a depth-first iteration on front graph
 254         unsigned long N = this->GetNumberOfSeeds( );
 255         unsigned long count = 0;
 256         std::vector< bool > m( N, false );
 257         std::queue< unsigned long > q;
 258         q.push( 0 );
 259         while( !q.empty( ) )
 260         {
 261           unsigned long f = q.front( );
 262           q.pop( );
 263
 264           if( m[ f ] )
 265             continue;
 266           m[ f ] = true;
 267           count++;
 268
 269           for( unsigned int n = 0; n < N; ++n )
 270             if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
 271               q.push( n );
 272
 273         } // elihw
 274         ret = ( count == N );
 275
 276       } // fi
 277
 278     } // fi
 279
 280   } // fi
 281   return( ret );
 282 }
 283
 284 // -------------------------------------------------------------------------
 285 template< class V, class C, class R, class B >
 286 bool fpa::Base::Algorithm< V, C, R, B >::
 287 _NeedToStop( ) const
 288 {
 289   return( false );
 290 }
 291
 292 // -------------------------------------------------------------------------
 293 template< class V, class C, class R, class B >
 294 void fpa::Base::Algorithm< V, C, R, B >::
 295 _InitQueue( )
 296 {
 297   this->_QueueClear( );
 298   for(
 299     typename _TNodes::const_iterator sIt = this->m_Seeds.begin( );
 300     sIt != this->m_Seeds.end( );
 301     sIt++
 302     )
 303   {
 304     this->_QueuePush( *sIt );
 305     this->_Mark( *sIt );
 306
 307   } // rof
 308 }
 309
 310 #endif // __FPA__BASE__ALGORITHM__HXX__
 311
 312 // eof - $RCSfile$