1 #ifndef __fpa__Base__Algorithm__hxx__
2 #define __fpa__Base__Algorithm__hxx__
6 // -------------------------------------------------------------------------
7 template < class _TFilter, class _TVertex, class _TOutput >
8 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
11 this->Vertex.Fill( 0 );
12 this->Parent.Fill( 0 );
13 this->Result = _TOutput( 0 );
17 // -------------------------------------------------------------------------
18 template < class _TFilter, class _TVertex, class _TOutput >
19 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
20 _TQueueNode( const _TVertex& v )
24 this->Result = _TOutput( 0 );
28 // -------------------------------------------------------------------------
29 template < class _TFilter, class _TVertex, class _TOutput >
30 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
31 _TQueueNode( const _TVertex& v, const _TQueueNode& n )
34 this->Parent = n.Vertex;
35 this->Result = n.Result;
36 this->FrontId = n.FrontId;
39 // -------------------------------------------------------------------------
40 template < class _TFilter, class _TVertex, class _TOutput >
41 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
44 this->m_Seeds.clear( );
48 // -------------------------------------------------------------------------
49 template < class _TFilter, class _TVertex, class _TOutput >
50 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
51 AddSeed( const _TVertex& seed, const TOutput& value )
53 _TQueueNode node( seed );
54 node.FrontId = this->m_Seeds.size( ) + 1;
56 this->m_Seeds.push_back( node );
60 // -------------------------------------------------------------------------
61 template < class _TFilter, class _TVertex, class _TOutput >
62 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
65 m_InitResult( _TOutput( 0 ) ),
66 m_StopAtOneFront( false )
70 // -------------------------------------------------------------------------
71 template < class _TFilter, class _TVertex, class _TOutput >
72 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
77 // -------------------------------------------------------------------------
78 template < class _TFilter, class _TVertex, class _TOutput >
79 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
82 this->InvokeEvent( TStartEvent( ) );
83 this->_BeforeGenerateData( );
84 this->m_NumberOfFronts = this->m_Seeds.size( );
85 if( this->m_NumberOfFronts > 0 )
88 TCollision coll( TVertex( ), false );
89 TCollisionsRow row( this->m_NumberOfFronts, coll );
90 this->m_Collisions.clear( );
91 this->m_Collisions.resize( this->m_NumberOfFronts, row );
96 auto nIt = this->m_Seeds.begin( );
97 nIt != this->m_Seeds.end( );
100 this->_QueuePush( *nIt );
102 // Init marks and results
104 this->_InitResults( this->m_InitResult );
109 while( this->_ContinueGenerateData( ) );
112 this->_AfterGenerateData( );
113 this->InvokeEvent( TEndEvent( ) );
116 // -------------------------------------------------------------------------
117 template < class _TFilter, class _TVertex, class _TOutput >
118 bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
119 _ContinueGenerateData( )
124 // -------------------------------------------------------------------------
125 template < class _TFilter, class _TVertex, class _TOutput >
126 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
129 this->InvokeEvent( TStartLoopEvent( ) );
130 this->_BeforeLoop( );
131 while( this->_ValidLoop( ) )
133 _TQueueNode node = this->_QueuePop( );
134 this->InvokeEvent( TPopEvent( node.Vertex, node.FrontId ) );
136 // Process actual vertex
137 if( this->_IsMarked( node.Vertex ) )
140 this->_UpdateResult( node );
141 this->InvokeEvent( TMarkEvent( node.Vertex, node.FrontId ) );
143 // Add neighbors to queue
144 TNeighborhood neighs = this->m_NeighborhoodFunction->Evaluate( node.Vertex );
145 for( auto it = neighs.begin( ); it != neighs.end( ); ++it )
147 if( !( this->_IsMarked( *it ) ) )
149 _TQueueNode neigh( *it, node );
150 if( this->_UpdateValue( neigh, node ) )
152 this->_QueuePush( neigh );
153 this->InvokeEvent( TPushEvent( node.Vertex, node.FrontId ) );
158 this->_UpdateCollisions( node.Vertex, *it );
164 this->InvokeEvent( TEndLoopEvent( ) );
167 // -------------------------------------------------------------------------
168 template < class _TFilter, class _TVertex, class _TOutput >
169 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
170 _BeforeGenerateData( )
174 // -------------------------------------------------------------------------
175 template < class _TFilter, class _TVertex, class _TOutput >
176 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
177 _AfterGenerateData( )
181 // -------------------------------------------------------------------------
182 template < class _TFilter, class _TVertex, class _TOutput >
183 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
188 // -------------------------------------------------------------------------
189 template < class _TFilter, class _TVertex, class _TOutput >
190 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
195 // -------------------------------------------------------------------------
196 template < class _TFilter, class _TVertex, class _TOutput >
197 bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
200 bool r = ( this->_QueueSize( ) > 0 );
201 if( this->m_StopAtOneFront )
202 r &= ( this->m_NumberOfFronts > 0 );
206 // -------------------------------------------------------------------------
207 template < class _TFilter, class _TVertex, class _TOutput >
208 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
209 _UpdateCollisions( const TVertex& a, const TVertex& b )
211 auto ma = this->_GetMark( a );
212 auto mb = this->_GetMark( b );
213 if( ma == mb || ma == 0 || mb == 0 )
216 // Mark collision, if it is new
219 bool exists = this->m_Collisions[ ma ][ mb ].second;
220 exists &= this->m_Collisions[ mb ][ ma ].second;
223 this->m_Collisions[ ma ][ mb ].first = a;
224 this->m_Collisions[ ma ][ mb ].second = true;
225 this->m_Collisions[ mb ][ ma ].first = b;
226 this->m_Collisions[ mb ][ ma ].second = true;
228 // Update number of fronts
229 unsigned long N = this->m_Seeds.size( );
230 unsigned long count = 0;
231 std::vector< bool > m( N, false );
232 std::queue< unsigned long > q;
236 unsigned long f = q.front( );
244 for( unsigned int n = 0; n < N; ++n )
245 if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
249 this->m_NumberOfFronts = N - count;
254 // -------------------------------------------------------------------------
255 template < class _TFilter, class _TVertex, class _TOutput >
256 _TOutput fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
257 _GetInputValue( const _TQueueNode& v, const _TQueueNode& p )
259 _TOutput res = this->m_InitResult;
260 if( this->m_VertexFunction.IsNotNull( ) )
261 res = this->m_VertexFunction->Evaluate( v.Vertex, p.Vertex );
262 if( this->m_ConversionFunction.IsNotNull( ) )
263 res = this->m_ConversionFunction->Evaluate( res );
267 #endif // __fpa__Base__Algorithm__hxx__