libs/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 ClearSeeds( )
  43 {
  44   this->m_Seeds.clear( );
  45   this->Modified( );
  46 }
  47
  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 )
  52 {
  53   _TQueueNode node( seed );
  54   node.FrontId = this->m_Seeds.size( ) + 1;
  55   node.Result = value;
  56   this->m_Seeds.push_back( node );
  57   this->Modified( );
  58 }
  59
  60 // -------------------------------------------------------------------------
  61 template < class _TFilter, class _TVertex, class _TOutput >
  62 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
  63 Algorithm( )
  64   : Superclass( ),
  65     m_InitResult( _TOutput( 0 ) ),
  66     m_StopAtOneFront( false )
  67 {
  68 }
  69
  70 // -------------------------------------------------------------------------
  71 template < class _TFilter, class _TVertex, class _TOutput >
  72 fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
  73 ~Algorithm( )
  74 {
  75 }
  76
  77 // -------------------------------------------------------------------------
  78 template < class _TFilter, class _TVertex, class _TOutput >
  79 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
  80 GenerateData( )
  81 {
  82   this->InvokeEvent( TStartEvent( ) );
  83   this->_BeforeGenerateData( );
  84   this->m_NumberOfFronts = this->m_Seeds.size( );
  85   if( this->m_NumberOfFronts > 0 )
  86   {
  87     // Prepare collisions
  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 );
  92
  93     // Put seeds on queue
  94     this->_QueueClear( );
  95     for(
  96       auto nIt = this->m_Seeds.begin( );
  97       nIt != this->m_Seeds.end( );
  98       ++nIt
  99       )
 100       this->_QueuePush( *nIt );
 101
 102     // Init marks and results
 103     this->_InitMarks( );
 104     this->_InitResults( this->m_InitResult );
 105
 106     // Main loop
 107     do
 108       this->_Loop( );
 109     while( this->_ContinueGenerateData( ) );
 110
 111   } // fi
 112   this->_AfterGenerateData( );
 113   this->InvokeEvent( TEndEvent( ) );
 114 }
 115
 116 // -------------------------------------------------------------------------
 117 template < class _TFilter, class _TVertex, class _TOutput >
 118 bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 119 _ContinueGenerateData( )
 120 {
 121   return( false );
 122 }
 123
 124 // -------------------------------------------------------------------------
 125 template < class _TFilter, class _TVertex, class _TOutput >
 126 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 127 _Loop( )
 128 {
 129   this->InvokeEvent( TStartLoopEvent( ) );
 130   this->_BeforeLoop( );
 131   while( this->_ValidLoop( ) )
 132   {
 133     _TQueueNode node = this->_QueuePop( );
 134     this->InvokeEvent( TPopEvent( node.Vertex, node.FrontId ) );
 135
 136     // Process actual vertex
 137     if( this->_IsMarked( node.Vertex ) )
 138       continue;
 139     this->_Mark( node );
 140     this->InvokeEvent( TMarkEvent( node.Vertex, node.FrontId ) );
 141     if( !( this->_UpdateResult( node ) ) )
 142       continue;
 143
 144     // Add neighbors to queue
 145     TNeighborhood neighs = this->m_NeighborhoodFunction->Evaluate( node.Vertex );
 146     for( auto it = neighs.begin( ); it != neighs.end( ); ++it )
 147     {
 148       if( !( this->_IsMarked( *it ) ) )
 149       {
 150         _TQueueNode neigh( *it, node );
 151         if( this->_UpdateValue( neigh, node ) )
 152         {
 153           this->_QueuePush( neigh );
 154           this->InvokeEvent( TPushEvent( node.Vertex, node.FrontId ) );
 155
 156         } // fi
 157       }
 158       else
 159         this->_UpdateCollisions( node.Vertex, *it );
 160
 161     } // rof
 162
 163   } // elihw
 164   this->_AfterLoop( );
 165   this->InvokeEvent( TEndLoopEvent( ) );
 166 }
 167
 168 // -------------------------------------------------------------------------
 169 template < class _TFilter, class _TVertex, class _TOutput >
 170 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 171 _BeforeGenerateData( )
 172 {
 173 }
 174
 175 // -------------------------------------------------------------------------
 176 template < class _TFilter, class _TVertex, class _TOutput >
 177 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 178 _AfterGenerateData( )
 179 {
 180 }
 181
 182 // -------------------------------------------------------------------------
 183 template < class _TFilter, class _TVertex, class _TOutput >
 184 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 185 _BeforeLoop( )
 186 {
 187 }
 188
 189 // -------------------------------------------------------------------------
 190 template < class _TFilter, class _TVertex, class _TOutput >
 191 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 192 _AfterLoop( )
 193 {
 194 }
 195
 196 // -------------------------------------------------------------------------
 197 template < class _TFilter, class _TVertex, class _TOutput >
 198 bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 199 _ValidLoop( ) const
 200 {
 201   bool r = ( this->_QueueSize( ) > 0 );
 202   if( this->m_StopAtOneFront )
 203     r &= ( this->m_NumberOfFronts > 0 );
 204   return( r );
 205 }
 206
 207 // -------------------------------------------------------------------------
 208 template < class _TFilter, class _TVertex, class _TOutput >
 209 void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 210 _UpdateCollisions( const TVertex& a, const TVertex& b )
 211 {
 212   auto ma = this->_GetMark( a );
 213   auto mb = this->_GetMark( b );
 214   if( ma == mb || ma == 0 || mb == 0 )
 215     return;
 216
 217   // Mark collision, if it is new
 218   ma--; mb--;
 219   bool ret = false;
 220   bool exists = this->m_Collisions[ ma ][ mb ].second;
 221   exists     &= this->m_Collisions[ mb ][ ma ].second;
 222   if( !exists )
 223   {
 224     this->m_Collisions[ ma ][ mb ].first = a;
 225     this->m_Collisions[ ma ][ mb ].second = true;
 226     this->m_Collisions[ mb ][ ma ].first = b;
 227     this->m_Collisions[ mb ][ ma ].second = true;
 228
 229     // Update number of fronts
 230     unsigned long N = this->m_Seeds.size( );
 231     unsigned long count = 0;
 232     std::vector< bool > m( N, false );
 233     std::queue< unsigned long > q;
 234     q.push( 0 );
 235     while( !q.empty( ) )
 236     {
 237       unsigned long f = q.front( );
 238       q.pop( );
 239
 240       if( m[ f ] )
 241         continue;
 242       m[ f ] = true;
 243       count++;
 244
 245       for( unsigned int n = 0; n < N; ++n )
 246         if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
 247           q.push( n );
 248
 249     } // elihw
 250     this->m_NumberOfFronts = N - count;
 251
 252   } // fi
 253 }
 254
 255 // -------------------------------------------------------------------------
 256 template < class _TFilter, class _TVertex, class _TOutput >
 257 _TOutput fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 258 _GetInputValue( const TVertex& v, const TVertex& p )
 259 {
 260   _TOutput res = this->m_InitResult;
 261   if( this->m_VertexFunction.IsNotNull( ) )
 262     res = this->m_VertexFunction->Evaluate( v, p );
 263   if( this->m_ConversionFunction.IsNotNull( ) )
 264     res = this->m_ConversionFunction->Evaluate( res );
 265   return( res );
 266 }
 267
 268 // -------------------------------------------------------------------------
 269 template < class _TFilter, class _TVertex, class _TOutput >
 270 bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
 271 _UpdateResult( _TQueueNode& n )
 272 {
 273   return( true );
 274 }
 275
 276 #endif // __fpa__Base__Algorithm__hxx__
 277
 278 // eof - $RCSfile$