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 >::
42 AddSeed( const _TVertex& seed, const TOutput& value )
44 _TQueueNode node( seed );
45 node.FrontId = this->m_Seeds.size( ) + 1;
47 this->m_Seeds.push_back( node );
51 // -------------------------------------------------------------------------
52 template < class _TFilter, class _TVertex, class _TOutput >
53 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
56 m_InitResult( _TOutput( 0 ) ),
57 m_StopAtOneFront( false )
61 // -------------------------------------------------------------------------
62 template < class _TFilter, class _TVertex, class _TOutput >
63 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
68 // -------------------------------------------------------------------------
69 template < class _TFilter, class _TVertex, class _TOutput >
70 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
73 this->InvokeEvent( TStartEvent( ) );
74 this->_BeforeGenerateData( );
75 this->m_NumberOfFronts = this->m_Seeds.size( );
76 if( this->m_NumberOfFronts > 0 )
79 TCollision coll( TVertex( ), false );
80 TCollisionsRow row( this->m_NumberOfFronts, coll );
81 this->m_Collisions.clear( );
82 this->m_Collisions.resize( this->m_NumberOfFronts, row );
87 auto nIt = this->m_Seeds.begin( );
88 nIt != this->m_Seeds.end( );
91 this->_QueuePush( *nIt );
93 // Init marks and results
95 this->_InitResults( this->m_InitResult );
100 while( this->_ContinueGenerateData( ) );
103 this->_AfterGenerateData( );
104 this->InvokeEvent( TEndEvent( ) );
107 // -------------------------------------------------------------------------
108 template < class _TFilter, class _TVertex, class _TOutput >
109 bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
110 _ContinueGenerateData( )
115 // -------------------------------------------------------------------------
116 template < class _TFilter, class _TVertex, class _TOutput >
117 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
120 this->InvokeEvent( TStartLoopEvent( ) );
121 this->_BeforeLoop( );
122 while( this->_ValidLoop( ) )
124 _TQueueNode node = this->_QueuePop( );
125 this->InvokeEvent( TPopEvent( node.Vertex, node.FrontId ) );
127 // Process actual vertex
128 if( this->_IsMarked( node.Vertex ) )
131 this->_UpdateResult( node );
132 this->InvokeEvent( TMarkEvent( node.Vertex, node.FrontId ) );
134 // Add neighbors to queue
135 TNeighborhood neighs = this->m_NeighborhoodFunction->Evaluate( node.Vertex );
136 for( auto it = neighs.begin( ); it != neighs.end( ); ++it )
138 if( !( this->_IsMarked( *it ) ) )
140 _TQueueNode neigh( *it, node );
141 if( this->_UpdateValue( neigh, node ) )
143 this->_QueuePush( neigh );
144 this->InvokeEvent( TPushEvent( node.Vertex, node.FrontId ) );
149 this->_UpdateCollisions( node.Vertex, *it );
155 this->InvokeEvent( TEndLoopEvent( ) );
158 // -------------------------------------------------------------------------
159 template < class _TFilter, class _TVertex, class _TOutput >
160 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
161 _BeforeGenerateData( )
165 // -------------------------------------------------------------------------
166 template < class _TFilter, class _TVertex, class _TOutput >
167 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
168 _AfterGenerateData( )
172 // -------------------------------------------------------------------------
173 template < class _TFilter, class _TVertex, class _TOutput >
174 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
179 // -------------------------------------------------------------------------
180 template < class _TFilter, class _TVertex, class _TOutput >
181 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
186 // -------------------------------------------------------------------------
187 template < class _TFilter, class _TVertex, class _TOutput >
188 bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
191 bool r = ( this->_QueueSize( ) > 0 );
192 if( this->m_StopAtOneFront )
193 r &= ( this->m_NumberOfFronts > 0 );
197 // -------------------------------------------------------------------------
198 template < class _TFilter, class _TVertex, class _TOutput >
199 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
200 _UpdateCollisions( const TVertex& a, const TVertex& b )
202 auto ma = this->_GetMark( a );
203 auto mb = this->_GetMark( b );
204 if( ma == mb || ma == 0 || mb == 0 )
207 // Mark collision, if it is new
210 bool exists = this->m_Collisions[ ma ][ mb ].second;
211 exists &= this->m_Collisions[ mb ][ ma ].second;
214 this->m_Collisions[ ma ][ mb ].first = a;
215 this->m_Collisions[ ma ][ mb ].second = true;
216 this->m_Collisions[ mb ][ ma ].first = b;
217 this->m_Collisions[ mb ][ ma ].second = true;
219 // Update number of fronts
220 unsigned long N = this->m_Seeds.size( );
221 unsigned long count = 0;
222 std::vector< bool > m( N, false );
223 std::queue< unsigned long > q;
227 unsigned long f = q.front( );
235 for( unsigned int n = 0; n < N; ++n )
236 if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
240 this->m_NumberOfFronts = N - count;
245 #endif // __fpa__Base__Algorithm__hxx__