lib/fpa/Base/TreeExtractor.hxx

   1 #ifndef __FPA__BASE__TREEEXTRACTOR__HXX__
   2 #define __FPA__BASE__TREEEXTRACTOR__HXX__
   3
   4 #include <limits>
   5
   6 // -------------------------------------------------------------------------
   7 template< class A >
   8 const unsigned long fpa::Base::TreeExtractor< A >::INF_VALUE =
   9   std::numeric_limits< unsigned long >::max( ) >> 1;
  10
  11 // -------------------------------------------------------------------------
  12 template< class A >
  13 unsigned int fpa::Base::TreeExtractor< A >::
  14 AddLeaf( const TVertex& leaf )
  15 {
  16   this->m_Leafs.push_back( leaf );
  17   this->Modified( );
  18   return( this->m_Leafs.size( ) - 1 );
  19 }
  20
  21 // -------------------------------------------------------------------------
  22 template< class A >
  23 unsigned int fpa::Base::TreeExtractor< A >::
  24 GetNumberOfLeafs( ) const
  25 {
  26   return( this->m_Leafs.size( ) );
  27 }
  28
  29 // -------------------------------------------------------------------------
  30 template< class A >
  31 const typename fpa::Base::TreeExtractor< A >::
  32 TVertex& fpa::Base::TreeExtractor< A >::
  33 GetLeaf( const unsigned int& id ) const
  34 {
  35   static const TVertex zero;
  36   if( id < this->m_Leafs.size( ) )
  37     return( this->m_Leafs[ id ] );
  38   else
  39     return( zero );
  40 }
  41
  42 // -------------------------------------------------------------------------
  43 template< class A >
  44 fpa::Base::TreeExtractor< A >::
  45 TreeExtractor( )
  46   : Superclass( )
  47 {
  48 }
  49
  50 // -------------------------------------------------------------------------
  51 template< class A >
  52 fpa::Base::TreeExtractor< A >::
  53 ~TreeExtractor( )
  54 {
  55 }
  56
  57 // -------------------------------------------------------------------------
  58 template< class A >
  59 void fpa::Base::TreeExtractor< A >::
  60 _BeforeMainLoop( )
  61 {
  62   this->Superclass::_BeforeMainLoop( );
  63   this->m_Tree.clear( );
  64 }
  65
  66 // -------------------------------------------------------------------------
  67 template< class A >
  68 void fpa::Base::TreeExtractor< A >::
  69 _AfterMainLoop( )
  70 {
  71   this->Superclass::_AfterMainLoop( );
  72
  73   // Prepare fronts graph using Floyd-Warshall
  74   unsigned long nSeeds = this->GetNumberOfSeeds( );
  75   _TMatrix dist( nSeeds, _TRow( nSeeds, Self::INF_VALUE ) );
  76   this->m_FrontPaths = dist;
  77
  78   for( unsigned long i = 0; i < nSeeds; ++i )
  79   {
  80     for( unsigned long j = 0; j < nSeeds; ++j )
  81     {
  82       if( this->m_CollisionSites[ i ][ j ].second )
  83       {
  84         dist[ i ][ j ] = 1;
  85         dist[ j ][ i ] = 1;
  86         this->m_FrontPaths[ i ][ j ] = j;
  87         this->m_FrontPaths[ j ][ i ] = i;
  88
  89       } // fi
  90
  91     } // rof
  92     dist[ i ][ i ] = 0;
  93     this->m_FrontPaths[ i ][ i ] = i;
  94
  95   } // rof
  96   for( unsigned long k = 0; k < nSeeds; ++k )
  97   {
  98     for( unsigned long i = 0; i < nSeeds; ++i )
  99     {
 100       for( unsigned long j = 0; j < nSeeds; ++j )
 101       {
 102         if( ( dist[ i ][ k ] + dist[ k ][ j ] ) < dist[ i ][ j ] )
 103         {
 104           dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ];
 105           this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
 106
 107         } // fi
 108
 109       } // rof
 110
 111     } // rof
 112
 113   } // rof
 114
 115   // Build tree
 116   this->m_Tree.clear( );
 117   typename TVertices::const_iterator vIt = this->m_Leafs.begin( );
 118   for( ; vIt != this->m_Leafs.end( ); ++vIt )
 119   {
 120     TVertices path = this->_Path( this->m_Root, *vIt );
 121     typename TVertices::const_iterator pIt = path.begin( );
 122     TVertex parent = *pIt;
 123     for( ; pIt != path.end( ); ++pIt )
 124     {
 125       this->m_Tree[ *pIt ] = parent;
 126       parent = *pIt;
 127
 128     } // rof
 129
 130   } // rof
 131 }
 132
 133 // -------------------------------------------------------------------------
 134 template< class A >
 135 typename fpa::Base::TreeExtractor< A >::
 136 TVertices fpa::Base::TreeExtractor< A >::
 137 _Path( const TVertex& s, const TVertex& e )
 138 {
 139   TVertices pS, pE;
 140
 141   // Check if both vertices belong to the same front or if collisions
 142   // should be analyzed.
 143   _TFrontId fs = this->_FrontId( s );
 144   _TFrontId fe = this->_FrontId( e );
 145   if( fs == fe )
 146   {
 147     // Path from start vertex until seed
 148     TVertex vIt = s;
 149     TVertex parent = this->_Parent( vIt );
 150     while( parent != vIt )
 151     {
 152       pS.push_back( vIt );
 153       vIt = parent;
 154       parent = this->_Parent( vIt );
 155
 156     } // elihw
 157     pS.push_back( vIt );
 158
 159     // Path from end vertex until seed
 160     vIt = e;
 161     parent = this->_Parent( vIt );
 162     while( parent != vIt )
 163     {
 164       pE.push_back( vIt );
 165       vIt = parent;
 166       parent = this->_Parent( vIt );
 167
 168     } // elihw
 169     pE.push_back( vIt );
 170
 171     // Erase duplicate vertices
 172     if( pS.size( ) > 0 && pE.size( ) > 0 )
 173     {
 174       bool cont = ( pS.back( ) == pE.back( ) );
 175       bool enter = false;
 176       TVertex lastVertex = pS.back( );
 177       while( cont )
 178       {
 179         enter = true;
 180
 181         lastVertex = pS.back( );
 182         pS.pop_back( );
 183         pE.pop_back( );
 184
 185         cont = ( pS.size( ) > 0 && pE.size( ) > 0 );
 186         if( cont )
 187           cont = ( pS.back( ) == pE.back( ) );
 188
 189       } // elihw
 190       if( enter )
 191         pS.push_back( lastVertex );
 192
 193     } // fi
 194
 195     // Contatenate both paths
 196     pS.insert( pS.end( ), pE.rbegin( ), pE.rend( ) );
 197   }
 198   else
 199   {
 200     // Use this->m_FrontPaths from Floyd-Warshall
 201     if( this->m_FrontPaths[ fs ][ fe ] != Self::INF_VALUE )
 202     {
 203       // Compute front path
 204       std::vector< unsigned long > fpath;
 205       fpath.push_back( fs );
 206       while( fs != fe )
 207       {
 208         fs = this->m_FrontPaths[ fs ][ fe ];
 209         fpath.push_back( fs );
 210
 211       } // elihw
 212
 213       // Continue only if both fronts are connected
 214       unsigned int N = fpath.size( );
 215       if( 0 < N )
 216       {
 217         // First path: from start vertex to first collision
 218         pS = this->_Path(
 219           s, this->m_CollisionSites[ fpath[ 0 ] ][ fpath[ 1 ] ].first
 220           );
 221
 222         // Intermediary paths
 223         for( unsigned int i = 1; i < N - 1; ++i )
 224         {
 225           pE = this->_Path(
 226             this->m_CollisionSites[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
 227             this->m_CollisionSites[ fpath[ i ] ][ fpath[ i + 1 ] ].first
 228             );
 229           pS.insert( pS.end( ), pE.begin( ), pE.end( ) );
 230
 231         } // rof
 232
 233         // Final path: from last collision to end point
 234         pE = this->_Path(
 235           this->m_CollisionSites[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first,
 236           e
 237           );
 238         pS.insert( pS.end( ), pE.begin( ), pE.end( ) );
 239
 240       } // fi
 241
 242     } // fi
 243
 244   } // fi
 245   return( pS );
 246 }
 247
 248 #endif // __FPA__BASE__TREEEXTRACTOR__HXX__
 249
 250 // eof - $RCSfile$