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