lib/fpa/Base/Algorithm.hxx

   1 #ifndef __fpa__Base__Algorithm__hxx__
   2 #define __fpa__Base__Algorithm__hxx__
   3
   4 #include <queue>
   5
   6 // -------------------------------------------------------------------------
   7 template < class _TFilter, class _TVertex, class _TOutput >
   8 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
   9 _TQueueNode( )
  10 {
  11   this->Vertex.Fill( 0 );
  12   this->Parent.Fill( 0 );
  13   this->Result = _TOutput( 0 );
  14   this->FrontId = 0;
  15 }
  16
  17 // -------------------------------------------------------------------------
  18 template < class _TFilter, class _TVertex, class _TOutput >
  19 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
  20 _TQueueNode( const _TVertex& v )
  21 {
  22   this->Vertex = v;
  23   this->Parent = v;
  24   this->Result = _TOutput( 0 );
  25   this->FrontId = 0;
  26 }
  27
  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 )
  32 {
  33   this->Vertex = v;
  34   this->Parent = n.Vertex;
  35   this->Result = n.Result;
  36   this->FrontId = n.FrontId;
  37 }
  38
  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 )
  43 {
  44   _TQueueNode node( seed );
  45   node.FrontId = this->m_Seeds.size( ) + 1;
  46   node.Result = value;
  47   this->m_Seeds.push_back( node );
  48   this->Modified( );
  49 }
  50
  51 // -------------------------------------------------------------------------
  52 template < class _TFilter, class _TVertex, class _TOutput >
  53 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
  54 Algorithm( )
  55   : Superclass( ),
  56     m_InitResult( _TOutput( 0 ) ),
  57     m_StopAtOneFront( false )
  58 {
  59 }
  60
  61 // -------------------------------------------------------------------------
  62 template < class _TFilter, class _TVertex, class _TOutput >
  63 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
  64 ~Algorithm( )
  65 {
  66 }
  67
  68 // -------------------------------------------------------------------------
  69 template < class _TFilter, class _TVertex, class _TOutput >
  70 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
  71 GenerateData( )
  72 {
  73   this->InvokeEvent( TStartEvent( ) );
  74   this->_BeforeGenerateData( );
  75   this->m_NumberOfFronts = this->m_Seeds.size( );
  76   if( this->m_NumberOfFronts > 0 )
  77   {
  78     // Prepare collisions
  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 );
  83
  84     // Put seeds on queue
  85     this->_QueueClear( );
  86     for(
  87       auto nIt = this->m_Seeds.begin( );
  88       nIt != this->m_Seeds.end( );
  89       ++nIt
  90       )
  91       this->_QueuePush( *nIt );
  92
  93     // Init marks and results
  94     this->_InitMarks( );
  95     this->_InitResults( this->m_InitResult );
  96
  97     // Main loop
  98     do
  99       this->_Loop( );
 100     while( this->_ContinueGenerateData( ) );
 101
 102   } // fi
 103   this->_AfterGenerateData( );
 104   this->InvokeEvent( TEndEvent( ) );
 105 }
 106
 107 // -------------------------------------------------------------------------
 108 template < class _TFilter, class _TVertex, class _TOutput >
 109 bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 110 _ContinueGenerateData( )
 111 {
 112   return( false );
 113 }
 114
 115 // -------------------------------------------------------------------------
 116 template < class _TFilter, class _TVertex, class _TOutput >
 117 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 118 _Loop( )
 119 {
 120   this->InvokeEvent( TStartLoopEvent( ) );
 121   this->_BeforeLoop( );
 122   while( this->_ValidLoop( ) )
 123   {
 124     _TQueueNode node = this->_QueuePop( );
 125     this->InvokeEvent( TPopEvent( node.Vertex, node.FrontId ) );
 126
 127     // Process actual vertex
 128     if( this->_IsMarked( node.Vertex ) )
 129       continue;
 130     this->_Mark( node );
 131     this->_UpdateResult( node );
 132     this->InvokeEvent( TMarkEvent( node.Vertex, node.FrontId ) );
 133
 134     // Add neighbors to queue
 135     TNeighborhood neighs = this->m_NeighborhoodFunction->Evaluate( node.Vertex );
 136     for( auto it = neighs.begin( ); it != neighs.end( ); ++it )
 137     {
 138       if( !( this->_IsMarked( *it ) ) )
 139       {
 140         _TQueueNode neigh( *it, node );
 141         if( this->_UpdateValue( neigh, node ) )
 142         {
 143           this->_QueuePush( neigh );
 144           this->InvokeEvent( TPushEvent( node.Vertex, node.FrontId ) );
 145
 146         } // fi
 147       }
 148       else
 149         this->_UpdateCollisions( node.Vertex, *it );
 150
 151     } // rof
 152
 153   } // elihw
 154   this->_AfterLoop( );
 155   this->InvokeEvent( TEndLoopEvent( ) );
 156 }
 157
 158 // -------------------------------------------------------------------------
 159 template < class _TFilter, class _TVertex, class _TOutput >
 160 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 161 _BeforeGenerateData( )
 162 {
 163 }
 164
 165 // -------------------------------------------------------------------------
 166 template < class _TFilter, class _TVertex, class _TOutput >
 167 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 168 _AfterGenerateData( )
 169 {
 170 }
 171
 172 // -------------------------------------------------------------------------
 173 template < class _TFilter, class _TVertex, class _TOutput >
 174 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 175 _BeforeLoop( )
 176 {
 177 }
 178
 179 // -------------------------------------------------------------------------
 180 template < class _TFilter, class _TVertex, class _TOutput >
 181 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 182 _AfterLoop( )
 183 {
 184 }
 185
 186 // -------------------------------------------------------------------------
 187 template < class _TFilter, class _TVertex, class _TOutput >
 188 bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 189 _ValidLoop( ) const
 190 {
 191   bool r = ( this->_QueueSize( ) > 0 );
 192   if( this->m_StopAtOneFront )
 193     r &= ( this->m_NumberOfFronts > 0 );
 194   return( r );
 195 }
 196
 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 )
 201 {
 202   auto ma = this->_GetMark( a );
 203   auto mb = this->_GetMark( b );
 204   if( ma == mb || ma == 0 || mb == 0 )
 205     return;
 206
 207   // Mark collision, if it is new
 208   ma--; mb--;
 209   bool ret = false;
 210   bool exists = this->m_Collisions[ ma ][ mb ].second;
 211   exists     &= this->m_Collisions[ mb ][ ma ].second;
 212   if( !exists )
 213   {
 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;
 218
 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;
 224     q.push( 0 );
 225     while( !q.empty( ) )
 226     {
 227       unsigned long f = q.front( );
 228       q.pop( );
 229
 230       if( m[ f ] )
 231         continue;
 232       m[ f ] = true;
 233       count++;
 234
 235       for( unsigned int n = 0; n < N; ++n )
 236         if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
 237           q.push( n );
 238
 239     } // elihw
 240     this->m_NumberOfFronts = N - count;
 241
 242   } // fi
 243 }
 244
 245 #endif // __fpa__Base__Algorithm__hxx__
 246
 247 // eof - $RCSfile$