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