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 _TVertex, class _TSuperclass >
   8 const typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
   9 TCollisions& fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
  10 GetCollisions( ) const
  11 {
  12   return( this->m_Collisions );
  13 }
  14
  15 // -------------------------------------------------------------------------
  16 template< class _TVertex, class _TSuperclass >
  17 void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
  18 SetCollisions( const TCollisions& collisions )
  19 {
  20   static const unsigned long _inf =
  21     std::numeric_limits< unsigned long >::max( );
  22   if( this->m_Collisions == collisions )
  23     return;
  24
  25   this->m_Collisions = collisions;
  26
  27   // Prepare a front graph
  28   unsigned long N = this->m_Collisions.size( );
  29   _TMatrix dist( N, _TRow( N, _inf ) );
  30   this->m_FrontPaths = dist;
  31   for( unsigned long i = 0; i < N; ++i )
  32   {
  33     for( unsigned long j = 0; j < N; ++j )
  34     {
  35       if( this->m_Collisions[ i ][ j ].second )
  36       {
  37         dist[ i ][ j ] = 1;
  38         dist[ j ][ i ] = 1;
  39         this->m_FrontPaths[ i ][ j ] = j;
  40         this->m_FrontPaths[ j ][ i ] = i;
  41
  42       } // fi
  43
  44     } // rof
  45     dist[ i ][ i ] = 0;
  46     this->m_FrontPaths[ i ][ i ] = i;
  47
  48   } // rof
  49
  50   // Use Floyd-Warshall to compute all possible paths between fronts
  51   for( unsigned long k = 0; k < N; ++k )
  52   {
  53     for( unsigned long i = 0; i < N; ++i )
  54     {
  55       for( unsigned long j = 0; j < N; ++j )
  56       {
  57         // WARNING: you don't want a numeric overflow!!!
  58         unsigned long dik = dist[ i ][ k ];
  59         unsigned long dkj = dist[ k ][ j ];
  60         unsigned long sum = _inf;
  61         if( dik < _inf && dkj < _inf )
  62           sum = dik + dkj;
  63
  64         // Ok, continue Floyd-Warshall
  65         if( sum < dist[ i ][ j ] )
  66         {
  67           dist[ i ][ j ] = sum;
  68           this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
  69
  70         } // fi
  71
  72       } // rof
  73
  74     } // rof
  75
  76   } // rof
  77   this->Modified( );
  78 }
  79
  80 // -------------------------------------------------------------------------
  81 template< class _TVertex, class _TSuperclass >
  82 void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
  83 ClearSeeds( )
  84 {
  85   this->m_Seeds.clear( );
  86   this->Modified( );
  87 }
  88
  89 // -------------------------------------------------------------------------
  90 template< class _TVertex, class _TSuperclass >
  91 void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
  92 AddSeed( const _TVertex& seed )
  93 {
  94   this->m_Seeds.push_back( seed );
  95   this->Modified( );
  96 }
  97
  98 // -------------------------------------------------------------------------
  99 template< class _TVertex, class _TSuperclass >
 100 typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
 101 TVertices fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
 102 GetPath( const _TVertex& a ) const
 103 {
 104   TVertices path;
 105   _TVertex it = a;
 106   _TVertex p = this->GetParent( it );
 107   while( it != p )
 108   {
 109     path.push_front( it );
 110     it = p;
 111     p = this->GetParent( it );
 112
 113   } // elihw
 114   path.push_front( it );
 115   return( path );
 116 }
 117
 118 // -------------------------------------------------------------------------
 119 template< class _TVertex, class _TSuperclass >
 120 typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
 121 TVertices fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
 122 GetPath( const _TVertex& a, const _TVertex& b ) const
 123 {
 124   static const unsigned long _inf =
 125     std::numeric_limits< unsigned long >::max( );
 126
 127   TVertices path;
 128   TVertices pa = this->GetPath( a );
 129   TVertices pb = this->GetPath( b );
 130   if( pa.size( ) > 0 && pb.size( ) > 0 )
 131   {
 132     // Find front identifiers
 133     unsigned long ia = _inf, ib = _inf;
 134     unsigned long N = this->m_Seeds.size( );
 135     for( unsigned long i = 0; i < N; ++i )
 136     {
 137       if( this->m_Seeds[ i ] == pa.front( ) )
 138         ia = i;
 139       if( this->m_Seeds[ i ] == pb.front( ) )
 140         ib = i;
 141
 142     } // rof
 143
 144     if( ia != ib )
 145     {
 146       // Use this->m_FrontPaths from Floyd-Warshall
 147       if( this->m_FrontPaths[ ia ][ ib ] < _inf )
 148       {
 149         // Compute front path
 150         std::vector< long > fpath;
 151         fpath.push_back( ia );
 152         while( ia != ib )
 153         {
 154           ia = this->m_FrontPaths[ ia ][ ib ];
 155           fpath.push_back( ia );
 156
 157         } // elihw
 158
 159         // Continue only if both fronts are connected
 160         unsigned int N = fpath.size( );
 161         if( N > 0 )
 162         {
 163           // First path: from start vertex to first collision
 164           path = this->GetPath(
 165             a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
 166             );
 167
 168           // Intermediary paths
 169           for( unsigned int i = 1; i < N - 1; ++i )
 170           {
 171             TVertices ipath =
 172               this->GetPath(
 173                 this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
 174                 this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
 175                 );
 176             path.insert( path.end( ), ipath.begin( ), ipath.end( ) );
 177
 178           } // rof
 179
 180           // Final path: from last collision to end point
 181           TVertices lpath =
 182             this->GetPath(
 183               this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
 184               );
 185           path.insert( path.end( ), lpath.begin( ), lpath.end( ) );
 186
 187         } // fi
 188
 189       } // fi
 190     }
 191     else
 192     {
 193       // Ignore common part: find common ancestor
 194       auto aIt = pa.begin( );
 195       auto bIt = pb.begin( );
 196       while( *aIt == *bIt && aIt != pa.end( ) && bIt != pb.end( ) )
 197       {
 198         ++aIt;
 199         ++bIt;
 200
 201       } // elihw
 202
 203       // Glue both parts
 204       for( --aIt; aIt != pa.end( ); ++aIt )
 205         path.push_front( *aIt );
 206       for( ; bIt != pb.end( ); ++bIt )
 207         path.push_back( *bIt );
 208
 209     } // fi
 210
 211   } // fi
 212   return( path );
 213 }
 214
 215 // -------------------------------------------------------------------------
 216 template< class _TVertex, class _TSuperclass >
 217 fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
 218 MinimumSpanningTree( )
 219   : Superclass( )
 220 {
 221 }
 222
 223 // -------------------------------------------------------------------------
 224 template< class _TVertex, class _TSuperclass >
 225 fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
 226 ~MinimumSpanningTree( )
 227 {
 228 }
 229
 230 #endif // __fpa__Base__MinimumSpanningTree__hxx__
 231
 232 // eof - $RCSfile$