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