lib/fpa/Base/MinimumSpanningTree.hxx

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