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 );
101 this->_AfterGenerateData( );
102 this->InvokeEvent( TEndEvent( ) );
105 // -------------------------------------------------------------------------
106 template < class _TFilter, class _TVertex, class _TOutput >
107 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
110 this->InvokeEvent( TStartLoopEvent( ) );
111 this->_BeforeLoop( );
112 while( this->_ValidLoop( ) )
114 _TQueueNode node = this->_QueuePop( );
115 this->InvokeEvent( TPopEvent( node.Vertex, node.FrontId ) );
117 // Process actual vertex
118 if( this->_IsMarked( node.Vertex ) )
121 this->_UpdateResult( node );
122 this->InvokeEvent( TMarkEvent( node.Vertex, node.FrontId ) );
124 // Add neighbors to queue
125 TNeighborhood neighs = this->m_NeighborhoodFunction->Evaluate( node.Vertex );
126 for( auto it = neighs.begin( ); it != neighs.end( ); ++it )
128 if( !( this->_IsMarked( *it ) ) )
130 _TQueueNode neigh( *it, node );
131 if( this->_UpdateValue( neigh, node ) )
133 this->_QueuePush( neigh );
134 this->InvokeEvent( TPushEvent( node.Vertex, node.FrontId ) );
139 this->_UpdateCollisions( node.Vertex, *it );
145 this->InvokeEvent( TEndLoopEvent( ) );
148 // -------------------------------------------------------------------------
149 template < class _TFilter, class _TVertex, class _TOutput >
150 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
151 _BeforeGenerateData( )
155 // -------------------------------------------------------------------------
156 template < class _TFilter, class _TVertex, class _TOutput >
157 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
158 _AfterGenerateData( )
162 // -------------------------------------------------------------------------
163 template < class _TFilter, class _TVertex, class _TOutput >
164 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
169 // -------------------------------------------------------------------------
170 template < class _TFilter, class _TVertex, class _TOutput >
171 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
176 // -------------------------------------------------------------------------
177 template < class _TFilter, class _TVertex, class _TOutput >
178 bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
181 bool r = ( this->_QueueSize( ) > 0 );
182 if( this->m_StopAtOneFront )
183 r &= ( this->m_NumberOfFronts > 0 );
187 // -------------------------------------------------------------------------
188 template < class _TFilter, class _TVertex, class _TOutput >
189 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
190 _UpdateCollisions( const TVertex& a, const TVertex& b )
192 auto ma = this->_GetMark( a );
193 auto mb = this->_GetMark( b );
194 if( ma == mb || ma == 0 || mb == 0 )
197 // Mark collision, if it is new
200 bool exists = this->m_Collisions[ ma ][ mb ].second;
201 exists &= this->m_Collisions[ mb ][ ma ].second;
204 this->m_Collisions[ ma ][ mb ].first = a;
205 this->m_Collisions[ ma ][ mb ].second = true;
206 this->m_Collisions[ mb ][ ma ].first = b;
207 this->m_Collisions[ mb ][ ma ].second = true;
209 // Update number of fronts
210 unsigned long N = this->m_Seeds.size( );
211 unsigned long count = 0;
212 std::vector< bool > m( N, false );
213 std::queue< unsigned long > q;
217 unsigned long f = q.front( );
225 for( unsigned int n = 0; n < N; ++n )
226 if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
230 this->m_NumberOfFronts = N - count;
235 #endif // __fpa__Base__Algorithm__hxx__