1 #ifndef __FPA__BASE__ALGORITHM__HXX__
2 #define __FPA__BASE__ALGORITHM__HXX__
5 #include <itkProcessObject.h>
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::
11 : Result( TResult( 0 ) ),
13 Label( Self::FarLabel )
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::
24 // -------------------------------------------------------------------------
25 template< class V, class C, class R, class S, class VC, class B >
26 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
27 InvokeEvent( const itk::EventObject& e )
29 if( this->m_ThrowEvents )
30 this->Superclass::InvokeEvent( e );
33 // -------------------------------------------------------------------------
34 template< class V, class C, class R, class S, class VC, class B >
35 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
36 InvokeEvent( const itk::EventObject& e ) const
38 if( this->m_ThrowEvents )
39 this->Superclass::InvokeEvent( e );
42 // -------------------------------------------------------------------------
43 template< class V, class C, class R, class S, class VC, class B >
44 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
45 AddSeed( const TVertex& s, const TResult& r )
50 ns.FrontId = this->m_SeedVertices.size( );
51 ns.Label = Self::FrontLabel;
52 this->m_Seeds[ s ] = ns;
53 this->m_SeedVertices.push_back( s );
57 // -------------------------------------------------------------------------
58 template< class V, class C, class R, class S, class VC, class B >
59 const typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
60 TVertex& fpa::Base::Algorithm< V, C, R, S, VC, B >::
61 GetSeed( const unsigned int& id ) const
63 return( this->m_SeedVertices[ id ] );
66 // -------------------------------------------------------------------------
67 template< class V, class C, class R, class S, class VC, class B >
68 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
71 this->m_Seeds.clear( );
72 this->m_SeedVertices.clear( );
76 // -------------------------------------------------------------------------
77 template< class V, class C, class R, class S, class VC, class B >
78 unsigned long fpa::Base::Algorithm< V, C, R, S, VC, B >::
79 GetNumberOfSeeds( ) const
81 return( this->m_Seeds.size( ) );
84 // -------------------------------------------------------------------------
85 template< class V, class C, class R, class S, class VC, class B >
86 fpa::Base::Algorithm< V, C, R, S, VC, B >::
89 m_ThrowEvents( false ),
90 m_StopAtOneFront( false )
94 // -------------------------------------------------------------------------
95 template< class V, class C, class R, class S, class VC, class B >
96 fpa::Base::Algorithm< V, C, R, S, VC, B >::
101 // -------------------------------------------------------------------------
102 template< class V, class C, class R, class S, class VC, class B >
103 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
106 unsigned long N = this->m_Seeds.size( );
110 this->InvokeEvent( TStartEvent( ) );
111 this->_BeforeGenerateData( );
113 this->m_Collisions.clear( );
115 resize( N, _TCollisionsRow( N, _TCollision( TVertex( ), false ) ) );
116 this->_InitResults( );
120 this->_AfterGenerateData( );
121 this->InvokeEvent( TEndEvent( ) );
124 // -------------------------------------------------------------------------
125 template< class V, class C, class R, class S, class VC, class B >
126 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
129 this->InvokeEvent( TStartLoopEvent( ) );
130 this->_BeforeLoop( );
131 while( !( this->_IsQueueEmpty( ) ) )
133 // Get next candidate
136 this->_QueuePop( vertex, node );
137 if( this->_Node( vertex ).Label == Self::AliveLabel )
140 // Mark it as "Alive" and update final result
141 node.Label = Self::AliveLabel;
142 this->_Mark( vertex, node );
143 this->_SetResult( vertex, node );
144 this->InvokeEvent( TAliveEvent( vertex, node.FrontId ) );
146 // Check if a forced stop condition arises
147 if( !( this->_NeedToStop( ) ) )
149 // Compute neighborhood
150 _TVertices neighborhood;
151 this->_Neighborhood( neighborhood, vertex );
153 // Iterate over neighbors
154 typename _TVertices::iterator nIt = neighborhood.begin( );
155 while( nIt != neighborhood.end( ) )
157 _TNode neighbor = this->_Node( *nIt );
158 if( neighbor.Label == Self::AliveLabel )
161 if( this->_UpdateCollisions( vertex, *nIt ) )
163 this->_QueueClear( );
164 nIt = neighborhood.end( );
171 // Add new candidate to queue
172 if( this->_ComputeNeighborResult( neighbor.Result, *nIt, vertex ) )
174 neighbor.FrontId = node.FrontId;
175 neighbor.Parent = vertex;
176 neighbor.Label = Self::FrontLabel;
177 this->_QueuePush( *nIt, neighbor );
178 this->_Mark( *nIt, neighbor );
179 this->InvokeEvent( TFrontEvent( *nIt, node.FrontId ) );
182 this->InvokeEvent( TFreezeEvent( *nIt, node.FrontId ) );
190 this->_QueueClear( );
194 this->InvokeEvent( TEndLoopEvent( ) );
197 // -------------------------------------------------------------------------
198 template< class V, class C, class R, class S, class VC, class B >
199 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
200 _BeforeGenerateData( )
204 // -------------------------------------------------------------------------
205 template< class V, class C, class R, class S, class VC, class B >
206 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
207 _AfterGenerateData( )
211 // -------------------------------------------------------------------------
212 template< class V, class C, class R, class S, class VC, class B >
213 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
218 // -------------------------------------------------------------------------
219 template< class V, class C, class R, class S, class VC, class B >
220 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
225 // -------------------------------------------------------------------------
226 template< class V, class C, class R, class S, class VC, class B >
227 bool fpa::Base::Algorithm< V, C, R, S, VC, B >::
228 _UpdateCollisions( const TVertex& a, const TVertex& b )
231 _TNode na = this->_Node( a );
232 _TNode nb = this->_Node( b );
233 long fa = na.FrontId;
234 long fb = nb.FrontId;
238 // Mark collision, if it is new
239 bool exists = this->m_Collisions[ fa ][ fb ].second;
240 exists &= this->m_Collisions[ fb ][ fa ].second;
244 this->m_Collisions[ fa ][ fb ].first = a;
245 this->m_Collisions[ fa ][ fb ].second = true;
246 this->m_Collisions[ fb ][ fa ].first = b;
247 this->m_Collisions[ fb ][ fa ].second = true;
249 // Stop if one front is desired
250 if( this->m_StopAtOneFront )
252 // Perform a depth-first iteration on front graph
253 unsigned long N = this->GetNumberOfSeeds( );
254 unsigned long count = 0;
255 std::vector< bool > m( N, false );
256 std::queue< unsigned long > q;
260 unsigned long f = q.front( );
268 for( unsigned int n = 0; n < N; ++n )
269 if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
273 ret = ( count == N );
283 // -------------------------------------------------------------------------
284 template< class V, class C, class R, class S, class VC, class B >
285 bool fpa::Base::Algorithm< V, C, R, S, VC, B >::
291 // -------------------------------------------------------------------------
292 template< class V, class C, class R, class S, class VC, class B >
293 typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
294 _TNode& fpa::Base::Algorithm< V, C, R, S, VC, B >::
295 _Node( const TVertex& v )
297 typename _TNodes::iterator vIt = this->m_Marks.find( v );
298 if( vIt == this->m_Marks.end( ) )
302 new_node.Result = TResult( 0 );
303 new_node.FrontId = -1;
304 new_node.Label = Self::FarLabel;
305 this->m_Marks[ v ] = new_node;
306 vIt = this->m_Marks.find( v );
309 return( vIt->second );
312 // -------------------------------------------------------------------------
313 template< class V, class C, class R, class S, class VC, class B >
314 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
315 _SetResult( const TVertex& v, const _TNode& n )
317 // Do nothing at this hierarchy level
320 // -------------------------------------------------------------------------
321 template< class V, class C, class R, class S, class VC, class B >
322 const typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
323 _TNode& fpa::Base::Algorithm< V, C, R, S, VC, B >::
324 _Node( const TVertex& v ) const
326 typename _TNodes::const_iterator vIt = this->m_Marks.find( v );
327 return( vIt->second );
330 // -------------------------------------------------------------------------
331 template< class V, class C, class R, class S, class VC, class B >
332 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
335 this->m_Marks.clear( );
338 // -------------------------------------------------------------------------
339 template< class V, class C, class R, class S, class VC, class B >
340 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
341 _Mark( const TVertex& v, const _TNode& node )
343 this->m_Marks[ v ] = node;
346 // -------------------------------------------------------------------------
347 template< class V, class C, class R, class S, class VC, class B >
348 void fpa::Base::Algorithm< V, C, R, S, VC, B >::
351 this->_QueueClear( );
353 typename _TNodes::const_iterator sIt = this->m_Seeds.begin( );
354 sIt != this->m_Seeds.end( );
358 this->_QueuePush( sIt->first, sIt->second );
359 this->_Mark( sIt->first, sIt->second );
364 #endif // __FPA__BASE__ALGORITHM__HXX__