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   this->Modified( );
  60 }
  61
  62 // -------------------------------------------------------------------------
  63 template< class V, class C, class B >
  64 void fpa::Base::MinimumSpanningTree< V, C, B >::
  65 GetPath( std::vector< V >& path, const V& a, const V& b ) const
  66 {
  67   typename TDecorated::const_iterator aIt = this->Get( ).find( a );
  68   typename TDecorated::const_iterator bIt = this->Get( ).find( b );
  69
  70   if( aIt == this->Get( ).end( ) || bIt == this->Get( ).end( ) )
  71     return;
  72
  73   short fa = aIt->second.second;
  74   short fb = bIt->second.second;
  75
  76   if( fa == fb )
  77   {
  78     std::vector< V > ap, bp;
  79     this->_Path( ap, a );
  80     this->_Path( bp, b );
  81
  82     // Ignore common part
  83     typename std::vector< V >::const_reverse_iterator raIt, rbIt;
  84     raIt = ap.rbegin( );
  85     rbIt = bp.rbegin( );
  86     while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
  87     {
  88       ++raIt;
  89       ++rbIt;
  90
  91     } // elihw
  92     if( raIt != ap.rbegin( ) ) --raIt;
  93
  94     // Add part from a
  95     typename std::vector< V >::const_iterator iaIt = ap.begin( );
  96     for( ; iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
  97       path.push_back( *iaIt );
  98
  99     // Add part from b
 100     for( ; rbIt != bp.rend( ); ++rbIt )
 101       path.push_back( *rbIt );
 102   }
 103   else
 104   {
 105     // Use this->m_FrontPaths from Floyd-Warshall
 106     if( this->m_FrontPaths[ fa ][ fb ] != Self::INF_VALUE )
 107     {
 108       // Compute front path
 109       std::vector< long > fpath;
 110       fpath.push_back( fa );
 111       while( fa != fb )
 112       {
 113         fa = this->m_FrontPaths[ fa ][ fb ];
 114         fpath.push_back( fa );
 115
 116       } // elihw
 117
 118       // Continue only if both fronts are connected
 119       unsigned int N = fpath.size( );
 120       if( 0 < N )
 121       {
 122         // First path: from start vertex to first collision
 123         this->GetPath(
 124           path, a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
 125           );
 126
 127         // Intermediary paths
 128         for( unsigned int i = 1; i < N - 1; ++i )
 129         {
 130           this->GetPath(
 131             path,
 132             this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
 133             this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
 134             );
 135
 136         } // rof
 137
 138         // Final path: from last collision to end point
 139         this->GetPath(
 140           path,
 141           this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
 142           );
 143
 144       } // fi
 145
 146     } // fi
 147
 148   } // fi
 149 }
 150
 151 // -------------------------------------------------------------------------
 152 template< class V, class C, class B >
 153 fpa::Base::MinimumSpanningTree< V, C, B >::
 154 MinimumSpanningTree( )
 155   : Superclass( )
 156 {
 157 }
 158
 159 // -------------------------------------------------------------------------
 160 template< class V, class C, class B >
 161 fpa::Base::MinimumSpanningTree< V, C, B >::
 162 ~MinimumSpanningTree( )
 163 {
 164 }
 165
 166 // -------------------------------------------------------------------------
 167 template< class V, class C, class B >
 168 void fpa::Base::MinimumSpanningTree< V, C, B >::
 169 _Path( std::vector< V >& path, const V& a ) const
 170 {
 171   typename TDecorated::const_iterator dIt = this->Get( ).find( a );
 172   if( dIt != this->Get( ).end( ) )
 173   {
 174     do
 175     {
 176       path.push_back( dIt->first );
 177       dIt = this->Get( ).find( dIt->second.first );
 178
 179     } while( dIt->first != dIt->second.first && dIt != this->Get( ).end( ) );
 180
 181     if( dIt != this->Get( ).end( ) )
 182       path.push_back( dIt->first );
 183
 184   } // fi
 185 }
 186
 187 #endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
 188
 189 // eof - $RCSfile$