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 _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
   8 const _TVertexCompare fpa::Base::
   9 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
  10 TNode::VertexCompare = _TVertexCompare( );
  11
  12 // -------------------------------------------------------------------------
  13 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
  14 void fpa::Base::
  15 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
  16 InvokeEvent( const itk::EventObject& e )
  17 {
  18   if( this->m_ThrowEvents )
  19     this->Superclass::InvokeEvent( e );
  20 }
  21
  22 // -------------------------------------------------------------------------
  23 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
  24 void fpa::Base::
  25 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
  26 InvokeEvent( const itk::EventObject& e ) const
  27 {
  28   if( this->m_ThrowEvents )
  29     this->Superclass::InvokeEvent( e );
  30 }
  31
  32 // -------------------------------------------------------------------------
  33 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
  34 unsigned long fpa::Base::
  35 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
  36 GetNumberOfSeeds( ) const
  37 {
  38   return( this->m_Seeds.size( ) );
  39 }
  40
  41 // -------------------------------------------------------------------------
  42 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
  43 void fpa::Base::
  44 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
  45 AddSeed( const TVertex& s, const TScalar& v )
  46 {
  47   TNode n;
  48   n.Vertex = s;
  49   n.Parent = s;
  50   n.Result = v;
  51   n.Label = Self::FrontLabel;
  52   this->AddSeed( n );
  53 }
  54
  55 // -------------------------------------------------------------------------
  56 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
  57 void fpa::Base::
  58 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
  59 AddSeed( const TNode& n )
  60 {
  61   this->m_Seeds.insert( n );
  62   this->Modified( );
  63 }
  64
  65 // -------------------------------------------------------------------------
  66 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
  67 void fpa::Base::
  68 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
  69 RemoveSeed( const TVertex& s )
  70 {
  71   TNode n;
  72   n.Vertex = s;
  73   typename TNodes::iterator i = this->m_Seeds.find( n );
  74   if( i != this->m_Seeds.end( ) )
  75   {
  76     this->m_Seeds.erase( i );
  77     this->Modified( );
  78
  79   } // fi
  80 }
  81
  82 // -------------------------------------------------------------------------
  83 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
  84 void fpa::Base::
  85 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
  86 RemoveAllSeeds( )
  87 {
  88   this->m_Seeds.clear( );
  89   this->Modified( );
  90 }
  91
  92 // -------------------------------------------------------------------------
  93 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
  94 fpa::Base::
  95 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
  96 Algorithm( )
  97   : Superclass( ),
  98     m_StopAtOneFront( false ),
  99     m_ThrowEvents( false )
 100 {
 101 }
 102
 103
 104 // -------------------------------------------------------------------------
 105 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 106 fpa::Base::
 107 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 108 ~Algorithm( )
 109 {
 110 }
 111
 112 // -------------------------------------------------------------------------
 113 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 114 void fpa::Base::
 115 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 116 GenerateData( )
 117 {
 118   this->InvokeEvent( TStartEvent( ) );
 119   this->_BeforeGenerateData( );
 120
 121   unsigned int N = this->m_Seeds.size( );
 122   if( N > 0 )
 123   {
 124     // Enumerate seeds
 125     typename TNodes::iterator nIt = this->m_Seeds.begin( );
 126     for( unsigned long i = 1; nIt != this->m_Seeds.end( ); ++nIt, ++i )
 127       nIt->FrontId = i;
 128
 129     // Prepare collisions
 130     TCollision coll( TVertex( ), false );
 131     TCollisionsRow row( N, coll );
 132     this->m_Collisions.clear( );
 133     this->m_Collisions.resize( N, row );
 134
 135     // Put seeds on queue
 136     this->_QueueClear( );
 137     for( nIt = this->m_Seeds.begin( ); nIt != this->m_Seeds.end( ); ++nIt )
 138       this->_QueuePush( *nIt );
 139
 140     // Init marks and results
 141     this->_InitMarks( );
 142     this->_InitResults( );
 143
 144     // Main loop
 145     this->_BeforeLoop( );
 146     this->_Loop( );
 147     this->_AfterLoop( );
 148
 149     // Deallocate any memory
 150     this->_DeallocateAuxiliary( );
 151
 152   } // fi
 153
 154   this->_AfterGenerateData( );
 155   this->InvokeEvent( TEndEvent( ) );
 156 }
 157
 158 // -------------------------------------------------------------------------
 159 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 160 void fpa::Base::
 161 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 162 _Loop( )
 163 {
 164   this->InvokeEvent( TStartLoopEvent( ) );
 165   this->_BeforeLoop( );
 166
 167   while( !( this->_IsQueueEmpty( ) ) )
 168   {
 169     // Extract next candidate
 170     TNode node = this->_QueuePop( );
 171
 172     // Check if it has been visited
 173     if( this->_GetMark( node ) > 0 )
 174       continue;
 175
 176     // Mark it as visited
 177     this->_Visit( node );
 178     this->InvokeEvent( TAliveEvent( node.Vertex, node.FrontId ) );
 179
 180     // Check if there is an external stop condition
 181     if( this->_NeedToStop( ) )
 182     {
 183       this->_QueueClear( );
 184       continue;
 185
 186     } // fi
 187
 188     // Get neighborhood
 189     TVertices neighborhood = this->_GetNeighborhood( node );
 190
 191     // Update neighborhood
 192     auto neighIt = neighborhood.begin( );
 193     bool stop = false;
 194     for( ; neighIt != neighborhood.end( ); ++neighIt )
 195     {
 196       if( this->_GetMark( *neighIt ) == 0 )
 197       {
 198         TNode neigh;
 199         neigh.Vertex = *neighIt;
 200         neigh.Parent = node.Vertex;
 201         neigh.FrontId = node.FrontId;
 202         if( this->_Result( neigh, node ) )
 203         {
 204           this->_QueuePush( neigh );
 205           this->InvokeEvent( TFrontEvent( *neighIt, node.FrontId ) );
 206
 207         } // fi
 208       }
 209       else
 210         stop |= this->_UpdateCollisions( node.Vertex, *neighIt );
 211
 212     } // rof
 213
 214     if( stop )
 215       this->_QueueClear( );
 216
 217   } // elihw
 218
 219   this->_AfterLoop( );
 220   this->InvokeEvent( TEndLoopEvent( ) );
 221 }
 222
 223 // -------------------------------------------------------------------------
 224 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 225 void fpa::Base::
 226 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 227 _BeforeGenerateData( )
 228 {
 229 }
 230
 231 // -------------------------------------------------------------------------
 232 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 233 void fpa::Base::
 234 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 235 _AfterGenerateData( )
 236 {
 237 }
 238
 239 // -------------------------------------------------------------------------
 240 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 241 void fpa::Base::
 242 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 243 _BeforeLoop( )
 244 {
 245 }
 246
 247 // -------------------------------------------------------------------------
 248 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 249 void fpa::Base::
 250 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 251 _AfterLoop( )
 252 {
 253 }
 254
 255 // -------------------------------------------------------------------------
 256 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 257 typename fpa::Base::
 258 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 259 TFrontId fpa::Base::
 260 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 261 _GetMark( const TNode& v )
 262 {
 263   return( this->_GetMark( v.Vertex ) );
 264 }
 265
 266 // -------------------------------------------------------------------------
 267 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 268 bool fpa::Base::
 269 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 270 _NeedToStop( )
 271 {
 272   return( false );
 273 }
 274
 275 // -------------------------------------------------------------------------
 276 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 277 typename fpa::Base::
 278 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 279 TVertices fpa::Base::
 280 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 281 _GetNeighborhood( const TNode& n ) const
 282 {
 283   return( this->_GetNeighborhood( n.Vertex ) );
 284 }
 285
 286 // -------------------------------------------------------------------------
 287 template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
 288 bool fpa::Base::
 289 Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
 290 _UpdateCollisions( const TVertex& a, const TVertex& b )
 291 {
 292   auto ma = this->_GetMark( a );
 293   auto mb = this->_GetMark( b );
 294   if( ma == mb || ma == 0 || mb == 0 )
 295     return( false );
 296   ma--;
 297   mb--;
 298
 299   // Mark collision, if it is new
 300   bool ret = false;
 301   bool exists = this->m_Collisions[ ma ][ mb ].second;
 302   exists     &= this->m_Collisions[ mb ][ ma ].second;
 303   if( !exists )
 304   {
 305     this->m_Collisions[ ma ][ mb ].first = a;
 306     this->m_Collisions[ ma ][ mb ].second = true;
 307     this->m_Collisions[ mb ][ ma ].first = b;
 308     this->m_Collisions[ mb ][ ma ].second = true;
 309
 310     // Stop if one front is desired
 311     if( this->m_StopAtOneFront )
 312     {
 313       // Perform a depth-first iteration on front graph
 314       unsigned long N = this->GetNumberOfSeeds( );
 315       unsigned long count = 0;
 316       std::vector< bool > m( N, false );
 317       std::queue< unsigned long > q;
 318       q.push( 0 );
 319       while( !q.empty( ) )
 320       {
 321         unsigned long f = q.front( );
 322         q.pop( );
 323
 324         if( m[ f ] )
 325           continue;
 326         m[ f ] = true;
 327         count++;
 328
 329         for( unsigned int n = 0; n < N; ++n )
 330           if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
 331             q.push( n );
 332
 333       } // elihw
 334       ret = ( count == N );
 335       this->InvokeEvent( TCollisionEvent( a, ma + 1 ) );
 336       this->InvokeEvent( TCollisionEvent( b, mb + 1 ) );
 337
 338     } // fi
 339
 340   } // fi
 341   return( ret );
 342 }
 343
 344 #endif // __FPA__BASE__ALGORITHM__HXX__
 345
 346 // eof - $RCSfile$