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 VC, class B >
9 fpa::Base::Algorithm< V, C, R, VC, B >::_TNode::
11 : Result( TResult( 0 ) ),
13 Label( Self::FarLabel )
17 // -------------------------------------------------------------------------
18 template< class V, class C, class R, class VC, class B >
19 fpa::Base::Algorithm< V, C, R, VC, B >::_TNode::
24 // -------------------------------------------------------------------------
25 template< class V, class C, class R, class VC, class B >
26 typename fpa::Base::Algorithm< V, C, R, VC, B >::
27 TMinimumSpanningTree* fpa::Base::Algorithm< V, C, R, VC, B >::
28 GetMinimumSpanningTree( )
31 dynamic_cast< TMinimumSpanningTree* >(
32 this->itk::ProcessObject::GetOutput( 1 )
37 // -------------------------------------------------------------------------
38 template< class V, class C, class R, class VC, class B >
39 const typename fpa::Base::Algorithm< V, C, R, VC, B >::
40 TMinimumSpanningTree* fpa::Base::Algorithm< V, C, R, VC, B >::
41 GetMinimumSpanningTree( ) const
44 dynamic_cast< const TMinimumSpanningTree* >(
45 this->itk::ProcessObject::GetOutput( 1 )
50 // -------------------------------------------------------------------------
51 template< class V, class C, class R, class VC, class B >
52 void fpa::Base::Algorithm< V, C, R, VC, B >::
53 GraftMinimumSpanningTree( itk::DataObject* obj )
55 TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
57 this->GraftNthOutput( 1, mst );
60 // -------------------------------------------------------------------------
61 template< class V, class C, class R, class VC, class B >
62 void fpa::Base::Algorithm< V, C, R, VC, B >::
63 InvokeEvent( const itk::EventObject& e )
65 if( this->m_ThrowEvents )
66 this->Superclass::InvokeEvent( e );
69 // -------------------------------------------------------------------------
70 template< class V, class C, class R, class VC, class B >
71 void fpa::Base::Algorithm< V, C, R, VC, B >::
72 InvokeEvent( const itk::EventObject& e ) const
74 if( this->m_ThrowEvents )
75 this->Superclass::InvokeEvent( e );
78 // -------------------------------------------------------------------------
79 template< class V, class C, class R, class VC, class B >
80 void fpa::Base::Algorithm< V, C, R, VC, B >::
81 AddSeed( const TVertex& s, const TResult& 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 );
93 // -------------------------------------------------------------------------
94 template< class V, class C, class R, class VC, class B >
95 const typename fpa::Base::Algorithm< V, C, R, VC, B >::
96 TVertex& fpa::Base::Algorithm< V, C, R, VC, B >::
97 GetSeed( const unsigned int& id ) const
99 return( this->m_SeedVertices[ id ] );
102 // -------------------------------------------------------------------------
103 template< class V, class C, class R, class VC, class B >
104 void fpa::Base::Algorithm< V, C, R, VC, B >::
107 this->m_Seeds.clear( );
108 this->m_SeedVertices.clear( );
112 // -------------------------------------------------------------------------
113 template< class V, class C, class R, class VC, class B >
114 unsigned long fpa::Base::Algorithm< V, C, R, VC, B >::
115 GetNumberOfSeeds( ) const
117 return( this->m_Seeds.size( ) );
120 // -------------------------------------------------------------------------
121 template< class V, class C, class R, class VC, class B >
122 fpa::Base::Algorithm< V, C, R, VC, B >::
125 m_ThrowEvents( false ),
126 m_StopAtOneFront( false )
128 this->m_MinimumSpanningTreeIndex = this->GetNumberOfRequiredOutputs( );
129 this->SetNumberOfRequiredOutputs( this->m_MinimumSpanningTreeIndex + 1 );
130 this->itk::ProcessObject::SetNthOutput(
131 this->m_MinimumSpanningTreeIndex, TMinimumSpanningTree::New( )
135 // -------------------------------------------------------------------------
136 template< class V, class C, class R, class VC, class B >
137 fpa::Base::Algorithm< V, C, R, VC, B >::
142 // -------------------------------------------------------------------------
143 template< class V, class C, class R, class VC, class B >
144 void fpa::Base::Algorithm< V, C, R, VC, B >::
147 unsigned long N = this->m_Seeds.size( );
151 this->InvokeEvent( TStartEvent( ) );
152 this->_BeforeGenerateData( );
154 this->m_Collisions.clear( );
156 resize( N, _TCollisionsRow( N, _TCollision( TVertex( ), false ) ) );
157 this->_InitResults( );
161 this->_AfterGenerateData( );
162 this->InvokeEvent( TEndEvent( ) );
165 // -------------------------------------------------------------------------
166 template< class V, class C, class R, class VC, class B >
167 void fpa::Base::Algorithm< V, C, R, VC, B >::
170 this->InvokeEvent( TStartLoopEvent( ) );
171 this->_BeforeLoop( );
172 while( !( this->_IsQueueEmpty( ) ) )
174 // Get next candidate
177 this->_QueuePop( vertex, node );
178 if( this->_Node( vertex ).Label == Self::AliveLabel )
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 ) );
187 // Check if a forced stop condition arises
188 if( !( this->_NeedToStop( ) ) )
190 // Compute neighborhood
191 _TVertices neighborhood;
192 this->_Neighborhood( neighborhood, vertex );
194 // Iterate over neighbors
195 typename _TVertices::iterator nIt = neighborhood.begin( );
196 while( nIt != neighborhood.end( ) )
198 _TNode neighbor = this->_Node( *nIt );
199 if( neighbor.Label == Self::AliveLabel )
202 if( this->_UpdateCollisions( vertex, *nIt ) )
204 this->_QueueClear( );
205 nIt = neighborhood.end( );
212 // Add new candidate to queue
213 if( this->_ComputeNeighborResult( neighbor.Result, *nIt, vertex ) )
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 ) );
223 this->InvokeEvent( TFreezeEvent( *nIt, node.FrontId ) );
231 this->_QueueClear( );
235 this->InvokeEvent( TEndLoopEvent( ) );
238 // -------------------------------------------------------------------------
239 template< class V, class C, class R, class VC, class B >
240 void fpa::Base::Algorithm< V, C, R, VC, B >::
241 _BeforeGenerateData( )
245 // -------------------------------------------------------------------------
246 template< class V, class C, class R, class VC, class B >
247 void fpa::Base::Algorithm< V, C, R, VC, B >::
248 _AfterGenerateData( )
252 // -------------------------------------------------------------------------
253 template< class V, class C, class R, class VC, class B >
254 void fpa::Base::Algorithm< V, C, R, VC, B >::
259 // -------------------------------------------------------------------------
260 template< class V, class C, class R, class VC, class B >
261 void fpa::Base::Algorithm< V, C, R, VC, B >::
266 // -------------------------------------------------------------------------
267 template< class V, class C, class R, class VC, class B >
268 bool fpa::Base::Algorithm< V, C, R, VC, B >::
269 _UpdateCollisions( const TVertex& a, const TVertex& b )
272 _TNode na = this->_Node( a );
273 _TNode nb = this->_Node( b );
274 long fa = na.FrontId;
275 long fb = nb.FrontId;
279 // Mark collision, if it is new
280 bool exists = this->m_Collisions[ fa ][ fb ].second;
281 exists &= this->m_Collisions[ fb ][ fa ].second;
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;
290 // Stop if one front is desired
291 if( this->m_StopAtOneFront )
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;
301 unsigned long f = q.front( );
309 for( unsigned int n = 0; n < N; ++n )
310 if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
314 ret = ( count == N );
324 // -------------------------------------------------------------------------
325 template< class V, class C, class R, class VC, class B >
326 bool fpa::Base::Algorithm< V, C, R, VC, B >::
332 // -------------------------------------------------------------------------
333 template< class V, class C, class R, class VC, class B >
334 typename fpa::Base::Algorithm< V, C, R, VC, B >::
335 _TNode& fpa::Base::Algorithm< V, C, R, VC, B >::
336 _Node( const TVertex& v )
338 typename _TNodes::iterator vIt = this->m_Marks.find( v );
339 if( vIt == this->m_Marks.end( ) )
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 );
350 return( vIt->second );
353 // -------------------------------------------------------------------------
354 template< class V, class C, class R, class VC, class B >
355 const typename fpa::Base::Algorithm< V, C, R, VC, B >::
356 _TNode& fpa::Base::Algorithm< V, C, R, VC, B >::
357 _Node( const TVertex& v ) const
359 typename _TNodes::const_iterator vIt = this->m_Marks.find( v );
360 return( vIt->second );
363 // -------------------------------------------------------------------------
364 template< class V, class C, class R, class VC, class B >
365 void fpa::Base::Algorithm< V, C, R, VC, B >::
368 this->m_Marks.clear( );
371 // -------------------------------------------------------------------------
372 template< class V, class C, class R, class VC, class B >
373 void fpa::Base::Algorithm< V, C, R, VC, B >::
374 _Mark( const TVertex& v, const _TNode& node )
376 this->m_Marks[ v ] = node;
379 // -------------------------------------------------------------------------
380 template< class V, class C, class R, class VC, class B >
381 void fpa::Base::Algorithm< V, C, R, VC, B >::
384 this->_QueueClear( );
386 typename _TNodes::const_iterator sIt = this->m_Seeds.begin( );
387 sIt != this->m_Seeds.end( );
391 this->_QueuePush( sIt->first, sIt->second );
392 this->_Mark( sIt->first, sIt->second );
397 #endif // __FPA__BASE__ALGORITHM__HXX__