1 #ifndef __FPA__BASE__ALGORITHM__HXX__
2 #define __FPA__BASE__ALGORITHM__HXX__
6 // -------------------------------------------------------------------------
7 template< class V, class C, class R, class B >
8 fpa::Base::Algorithm< V, C, R, B >::_TNode::
10 : Result( TResult( 0 ) ),
12 Label( Self::FarLabel )
16 // -------------------------------------------------------------------------
17 template< class V, class C, class R, class B >
18 fpa::Base::Algorithm< V, C, R, B >::_TNode::
23 // -------------------------------------------------------------------------
24 template< class V, class C, class R, class B >
25 void fpa::Base::Algorithm< V, C, R, B >::
26 InvokeEvent( const itk::EventObject& e )
28 if( this->m_ThrowEvents )
29 this->Superclass::InvokeEvent( e );
32 // -------------------------------------------------------------------------
33 template< class V, class C, class R, class B >
34 void fpa::Base::Algorithm< V, C, R, B >::
35 InvokeEvent( const itk::EventObject& e ) const
37 if( this->m_ThrowEvents )
38 this->Superclass::InvokeEvent( e );
41 // -------------------------------------------------------------------------
42 template< class V, class C, class R, class B >
43 void fpa::Base::Algorithm< V, C, R, B >::
44 AddSeed( const TVertex& s, const TResult& r )
50 ns.FrontId = this->m_Seeds.size( );
51 ns.Label = Self::FrontLabel;
52 this->m_Seeds.push_back( ns );
56 // -------------------------------------------------------------------------
57 template< class V, class C, class R, class B >
58 const typename fpa::Base::Algorithm< V, C, R, B >::
59 TVertex& fpa::Base::Algorithm< V, C, R, B >::
60 GetSeed( const unsigned int& id ) const
62 return( this->m_Seeds[ id ].Vertex );
65 // -------------------------------------------------------------------------
66 template< class V, class C, class R, class B >
67 void fpa::Base::Algorithm< V, C, R, B >::
70 this->m_Seeds.clear( );
74 // -------------------------------------------------------------------------
75 template< class V, class C, class R, class B >
76 unsigned long fpa::Base::Algorithm< V, C, R, B >::
77 GetNumberOfSeeds( ) const
79 return( this->m_Seeds.size( ) );
82 // -------------------------------------------------------------------------
83 template< class V, class C, class R, class B >
84 fpa::Base::Algorithm< V, C, R, B >::
87 m_ThrowEvents( false ),
88 m_StopAtOneFront( false )
92 // -------------------------------------------------------------------------
93 template< class V, class C, class R, class B >
94 fpa::Base::Algorithm< V, C, R, B >::
99 // -------------------------------------------------------------------------
100 template< class V, class C, class R, class B >
101 void fpa::Base::Algorithm< V, C, R, B >::
104 unsigned long N = this->m_Seeds.size( );
108 this->InvokeEvent( TStartEvent( ) );
109 this->_BeforeGenerateData( );
111 this->m_Collisions.clear( );
113 resize( N, _TCollisionsRow( N, _TCollision( TVertex( ), false ) ) );
114 this->_InitResults( );
118 this->_AfterGenerateData( );
119 this->InvokeEvent( TEndEvent( ) );
122 // -------------------------------------------------------------------------
123 template< class V, class C, class R, class B >
124 void fpa::Base::Algorithm< V, C, R, B >::
127 this->InvokeEvent( TStartLoopEvent( ) );
128 this->_BeforeLoop( );
129 while( !( this->_IsQueueEmpty( ) ) )
131 // Get next candidate
132 _TNode candidate = this->_QueuePop( );
133 if( this->_Node( candidate.Vertex ).Label == Self::AliveLabel )
136 // Mark it as "Alive" and update final result
137 candidate.Label = Self::AliveLabel;
138 this->_Mark( candidate );
139 this->_SetResult( candidate.Vertex, candidate.Result );
140 this->InvokeEvent( TAliveEvent( candidate.Vertex, candidate.FrontId ) );
142 // Check if a forced stop condition arises
143 if( !( this->_NeedToStop( ) ) )
145 // Compute neighborhood
146 _TVertices neighborhood;
147 this->_Neighborhood( neighborhood, candidate.Vertex );
149 // Iterate over neighbors
150 typename _TVertices::iterator nIt = neighborhood.begin( );
151 for( ; nIt != neighborhood.end( ); ++nIt )
153 _TNode neighbor = this->_Node( *nIt );
154 neighbor.Vertex = *nIt;
155 if( neighbor.Label == Self::AliveLabel )
158 if( this->_UpdateCollisions( candidate.Vertex, *nIt ) )
160 this->_QueueClear( );
161 nIt = neighborhood.end( );
167 // Add new candidate to queue
169 this->_ComputeNeighborResult(
170 neighbor.Result, *nIt, candidate.Vertex
174 neighbor.FrontId = candidate.FrontId;
175 neighbor.Parent = candidate.Vertex;
176 neighbor.Label = Self::FrontLabel;
177 this->_QueuePush( neighbor );
178 this->_Mark( neighbor );
179 this->InvokeEvent( TFrontEvent( *nIt, candidate.FrontId ) );
182 this->InvokeEvent( TFreezeEvent( *nIt, candidate.FrontId ) );
189 this->_QueueClear( );
193 this->InvokeEvent( TEndLoopEvent( ) );
196 // -------------------------------------------------------------------------
197 template< class V, class C, class R, class B >
198 void fpa::Base::Algorithm< V, C, R, B >::
199 _BeforeGenerateData( )
203 // -------------------------------------------------------------------------
204 template< class V, class C, class R, class B >
205 void fpa::Base::Algorithm< V, C, R, B >::
206 _AfterGenerateData( )
210 // -------------------------------------------------------------------------
211 template< class V, class C, class R, class B >
212 void fpa::Base::Algorithm< V, C, R, B >::
217 // -------------------------------------------------------------------------
218 template< class V, class C, class R, class B >
219 void fpa::Base::Algorithm< V, C, R, B >::
224 // -------------------------------------------------------------------------
225 template< class V, class C, class R, class B >
226 bool fpa::Base::Algorithm< V, C, R, B >::
227 _UpdateCollisions( const TVertex& a, const TVertex& b )
230 _TNode na = this->_Node( a );
231 _TNode nb = this->_Node( b );
232 long fa = na.FrontId;
233 long fb = na.FrontId;
237 // Mark collision, if it is new
238 bool exists = this->m_Collisions[ fa ][ fb ].second;
239 exists &= this->m_Collisions[ fb ][ fa ].second;
242 this->m_Collisions[ fa ][ fb ].first = na.Vertex;
243 this->m_Collisions[ fa ][ fb ].second = true;
244 this->m_Collisions[ fb ][ fa ].first = nb.Vertex;
245 this->m_Collisions[ fb ][ fa ].second = true;
247 // Stop if one front is desired
248 if( this->m_StopAtOneFront )
250 // Perform a depth-first iteration on front graph
251 unsigned long N = this->GetNumberOfSeeds( );
252 unsigned long count = 0;
253 std::vector< bool > m( N, false );
254 std::queue< unsigned long > q;
258 unsigned long f = q.front( );
266 for( unsigned int n = 0; n < N; ++n )
267 if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
271 ret = ( count == N );
281 // -------------------------------------------------------------------------
282 template< class V, class C, class R, class B >
283 bool fpa::Base::Algorithm< V, C, R, B >::
289 // -------------------------------------------------------------------------
290 template< class V, class C, class R, class B >
291 void fpa::Base::Algorithm< V, C, R, B >::
294 this->_QueueClear( );
296 typename _TNodes::const_iterator sIt = this->m_Seeds.begin( );
297 sIt != this->m_Seeds.end( );
301 this->_QueuePush( *sIt );
307 #endif // __FPA__BASE__ALGORITHM__HXX__