1 #ifndef __FPA__BASE__ALGORITHM__HXX__
2 #define __FPA__BASE__ALGORITHM__HXX__
8 // -------------------------------------------------------------------------
9 template< class T, class B >
10 void fpa::Base::Algorithm< T, B >::
11 InvokeEvent( const itk::EventObject& e )
13 if( this->m_ThrowEvents )
14 this->Superclass::InvokeEvent( e );
17 // -------------------------------------------------------------------------
18 template< class T, class B >
19 void fpa::Base::Algorithm< T, B >::
20 InvokeEvent( const itk::EventObject& e ) const
22 if( this->m_ThrowEvents )
23 this->Superclass::InvokeEvent( e );
26 // -------------------------------------------------------------------------
27 template< class T, class B >
28 void fpa::Base::Algorithm< T, B >::
29 AddSeed( const TVertex& s, const TResult& v )
31 this->m_Seeds.push_back( _TNode( s, v, this->m_Seeds.size( ) ) );
35 // -------------------------------------------------------------------------
36 template< class T, class B >
37 const typename fpa::Base::Algorithm< T, B >::
38 TVertex& fpa::Base::Algorithm< T, B >::
39 GetSeed( const unsigned long& i ) const
41 return( this->m_Seeds[ i ].Vertex );
44 // -------------------------------------------------------------------------
45 template< class T, class B >
46 void fpa::Base::Algorithm< T, B >::
49 this->m_Seeds.clear( );
53 // -------------------------------------------------------------------------
54 template< class T, class B >
55 unsigned long fpa::Base::Algorithm< T, B >::
56 GetNumberOfSeeds( ) const
58 return( this->m_Seeds.size( ) );
61 // -------------------------------------------------------------------------
62 template< class T, class B >
63 fpa::Base::Algorithm< T, B >::
66 m_StopAtOneFront( false ),
67 m_ThrowEvents( false )
71 // -------------------------------------------------------------------------
72 template< class T, class B >
73 fpa::Base::Algorithm< T, B >::
78 // -------------------------------------------------------------------------
79 template< class T, class B >
80 void fpa::Base::Algorithm< T, B >::
83 this->AllocateOutputs( );
85 unsigned long N = this->m_Seeds.size( );
88 this->m_CollisionSites.clear( );
89 this->m_CollisionSites.
90 resize( N, _TCollisionSitesRow( N, _TCollision( TVertex( ), false ) ) );
92 this->_BeforeMainLoop( );
93 this->_InitializeMarks( );
94 this->_InitializeResults( );
95 this->_InitializeQueue( );
97 this->_AfterMainLoop( );
98 this->InvokeEvent( TEndEvent( ) );
101 // -------------------------------------------------------------------------
102 template< class T, class B >
103 void fpa::Base::Algorithm< T, B >::
108 // -------------------------------------------------------------------------
109 template< class T, class B >
110 void fpa::Base::Algorithm< T, B >::
115 // -------------------------------------------------------------------------
116 template< class T, class B >
117 void fpa::Base::Algorithm< T, B >::
122 // -------------------------------------------------------------------------
123 template< class T, class B >
124 void fpa::Base::Algorithm< T, B >::
129 // -------------------------------------------------------------------------
130 template< class T, class B >
131 void fpa::Base::Algorithm< T, B >::
134 this->_BeforeLoop( );
135 while( !( this->_IsQueueEmpty( ) ) )
137 _TNode n = this->_QueuePop( );
138 if( this->_IsMarked( n.Vertex ) )
142 this->InvokeEvent( TMarkEvent( n ) );
143 if( this->_UpdateResult( n ) )
145 if( !( this->_CheckStopCondition( ) ) )
148 this->_Neighs( n, N );
149 typename _TNodes::iterator nnIt = N.begin( );
150 while( nnIt != N.end( ) )
152 if( this->_IsMarked( nnIt->Vertex ) )
154 // Update real front identifier
155 nnIt->FrontId = this->_FrontId( nnIt->Vertex );
158 if( this->_CheckCollisions( n, *nnIt ) )
160 if( this->m_StopAtOneFront )
162 this->_QueueClear( );
171 if( this->_UpdateNeigh( *nnIt, n ) )
173 nnIt->Parent = n.Vertex;
174 this->_QueuePush( *nnIt );
175 this->InvokeEvent( TFrontEvent( *nnIt ) );
180 if( nnIt != N.end( ) )
186 this->_QueueClear( );
194 // -------------------------------------------------------------------------
195 template< class T, class B >
196 bool fpa::Base::Algorithm< T, B >::
197 _CheckCollisions( const _TNode& a, const _TNode& b )
200 if( a.FrontId != b.FrontId )
202 // Mark collision, if it is new
203 bool exists = this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second;
204 exists &= this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second;
207 this->m_CollisionSites[ a.FrontId ][ b.FrontId ].first = a.Vertex;
208 this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second = true;
209 this->m_CollisionSites[ b.FrontId ][ a.FrontId ].first = b.Vertex;
210 this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second = true;
212 // Stop if one front is desired
213 if( this->m_StopAtOneFront )
215 // Perform a depth-first iteration on front graph
216 unsigned long N = this->GetNumberOfSeeds( );
218 std::vector< bool > m( N, false );
219 std::queue< unsigned long > q;
223 unsigned long f = q.front( );
231 for( unsigned int n = 0; n < N; ++n )
232 if( this->m_CollisionSites[ f ][ n ].second && !m[ n ] )
246 // -------------------------------------------------------------------------
247 template< class T, class B >
248 bool fpa::Base::Algorithm< T, B >::
249 _CheckStopCondition( )
254 // -------------------------------------------------------------------------
255 template< class T, class B >
256 bool fpa::Base::Algorithm< T, B >::
257 _UpdateResult( _TNode& n )
262 // -------------------------------------------------------------------------
263 template< class T, class B >
264 void fpa::Base::Algorithm< T, B >::
267 this->m_Marks.clear( );
270 // -------------------------------------------------------------------------
271 template< class T, class B >
272 bool fpa::Base::Algorithm< T, B >::
273 _IsMarked( const TVertex& v ) const
275 return( this->m_Marks.find( v ) != this->m_Marks.end( ) );
278 // -------------------------------------------------------------------------
279 template< class T, class B >
280 typename fpa::Base::Algorithm< T, B >::
281 _TFrontId fpa::Base::Algorithm< T, B >::
282 _FrontId( const TVertex& v ) const
284 typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
285 if( mIt != this->m_Marks.end( ) )
286 return( mIt->second.FrontId );
288 return( std::numeric_limits< _TFrontId >::max( ) );
291 // -------------------------------------------------------------------------
292 template< class T, class B >
293 typename fpa::Base::Algorithm< T, B >::
294 TVertex fpa::Base::Algorithm< T, B >::
295 _Parent( const TVertex& v ) const
297 typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
298 if( mIt == this->m_Marks.end( ) )
299 return( TVertex( ) );
301 return( mIt->second.Parent );
304 // -------------------------------------------------------------------------
305 template< class T, class B >
306 void fpa::Base::Algorithm< T, B >::
307 _Mark( const _TNode& n )
309 this->m_Marks[ n.Vertex ] = n;
312 #endif // __FPA__BASE__ALGORITHM__HXX__