lib/fpa/Base/MinimumSpanningTree.hxx

   1 #ifndef __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
   2 #define __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
   3
   4 #include <limits>
   5
   6 // -------------------------------------------------------------------------
   7 template< class V, class C, class B >
   8 const unsigned long fpa::Base::MinimumSpanningTree< V, C, B >::INF_VALUE =
   9   std::numeric_limits< unsigned long >::max( ) >> 1;
  10
  11 // -------------------------------------------------------------------------
  12 template< class V, class C, class B >
  13 void fpa::Base::MinimumSpanningTree< V, C, B >::
  14 SetCollisions( const TCollisions& collisions )
  15 {
  16   this->m_Collisions = collisions;
  17
  18   // Prepare fronts graph using Floyd-Warshall
  19   unsigned long nSeeds = this->m_Collisions.size( );
  20   _TMatrix dist( nSeeds, _TRow( nSeeds, Self::INF_VALUE ) );
  21   this->m_FrontPaths = dist;
  22
  23   for( unsigned long i = 0; i < nSeeds; ++i )
  24   {
  25     for( unsigned long j = 0; j < nSeeds; ++j )
  26     {
  27       if( this->m_Collisions[ i ][ j ].second )
  28       {
  29         dist[ i ][ j ] = 1;
  30         dist[ j ][ i ] = 1;
  31         this->m_FrontPaths[ i ][ j ] = j;
  32         this->m_FrontPaths[ j ][ i ] = i;
  33
  34       } // fi
  35
  36     } // rof
  37     dist[ i ][ i ] = 0;
  38     this->m_FrontPaths[ i ][ i ] = i;
  39
  40   } // rof
  41   for( unsigned long k = 0; k < nSeeds; ++k )
  42   {
  43     for( unsigned long i = 0; i < nSeeds; ++i )
  44     {
  45       for( unsigned long j = 0; j < nSeeds; ++j )
  46       {
  47         if( ( dist[ i ][ k ] + dist[ k ][ j ] ) < dist[ i ][ j ] )
  48         {
  49           dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ];
  50           this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
  51
  52         } // fi
  53
  54       } // rof
  55
  56     } // rof
  57
  58   } // rof
  59
  60   this->Modified( );
  61 }
  62
  63 // -------------------------------------------------------------------------
  64 template< class V, class C, class B >
  65 void fpa::Base::MinimumSpanningTree< V, C, B >::
  66 GetPath( std::vector< V >& path, const V& a, const V& b ) const
  67 {
  68   long fa = this->_FrontId( a );
  69   long fb = this->_FrontId( b );
  70
  71   if( fa == fb )
  72   {
  73     std::vector< V > ap, bp;
  74     this->_Path( ap, a );
  75     this->_Path( bp, b );
  76
  77     // Ignore common part
  78     typename std::vector< V >::const_reverse_iterator raIt, rbIt;
  79     raIt = ap.rbegin( );
  80     rbIt = bp.rbegin( );
  81     while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
  82     {
  83       ++raIt;
  84       ++rbIt;
  85
  86     } // elihw
  87     if( raIt != ap.rbegin( ) ) --raIt;
  88     if( rbIt != bp.rbegin( ) ) --rbIt;
  89
  90     // Add part from a
  91     typename std::vector< V >::const_iterator iaIt = ap.begin( );
  92     for( ; iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
  93       path.push_back( *iaIt );
  94
  95     // Add part from b
  96     for( ; rbIt != bp.rend( ); ++rbIt )
  97       path.push_back( *rbIt );
  98   }
  99   else
 100   {
 101     // Use this->m_FrontPaths from Floyd-Warshall
 102     if( this->m_FrontPaths[ fa ][ fb ] != Self::INF_VALUE )
 103     {
 104       // Compute front path
 105       std::vector< long > fpath;
 106       fpath.push_back( fa );
 107       while( fa != fb )
 108       {
 109         fa = this->m_FrontPaths[ fa ][ fb ];
 110         fpath.push_back( fa );
 111
 112       } // elihw
 113
 114       // Continue only if both fronts are connected
 115       unsigned int N = fpath.size( );
 116       if( 0 < N )
 117       {
 118         // First path: from start vertex to first collision
 119         this->GetPath(
 120           path, a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
 121           );
 122
 123         // Intermediary paths
 124         for( unsigned int i = 1; i < N - 1; ++i )
 125         {
 126           this->GetPath(
 127             path,
 128             this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
 129             this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
 130             );
 131
 132         } // rof
 133
 134         // Final path: from last collision to end point
 135         this->GetPath(
 136           path,
 137           this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
 138           );
 139
 140       } // fi
 141
 142     } // fi
 143
 144   } // fi
 145 }
 146
 147 // -------------------------------------------------------------------------
 148 template< class V, class C, class B >
 149 fpa::Base::MinimumSpanningTree< V, C, B >::
 150 MinimumSpanningTree( )
 151   : Superclass( )
 152 {
 153 }
 154
 155 // -------------------------------------------------------------------------
 156 template< class V, class C, class B >
 157 fpa::Base::MinimumSpanningTree< V, C, B >::
 158 ~MinimumSpanningTree( )
 159 {
 160 }
 161
 162 // -------------------------------------------------------------------------
 163 template< class V, class C, class B >
 164 void fpa::Base::MinimumSpanningTree< V, C, B >::
 165 _Path( std::vector< V >& path, const V& a ) const
 166 {
 167   V it = a;
 168   do
 169   {
 170     path.push_back( it );
 171     it = this->_Parent( it );
 172
 173   } while( it != this->_Parent( it ) );
 174   path.push_back( it );
 175 }
 176
 177 #endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
 178
 179 // eof - $RCSfile$