libs/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   static const unsigned long _inf =
 128     std::numeric_limits< unsigned long >::max( );
 129
 130   TVertices vertices;
 131   TVertices pa = this->GetPath( a );
 132   TVertices pb = this->GetPath( b );
 133   if( pa.size( ) > 0 && pb.size( ) > 0 )
 134   {
 135     // Find front identifiers
 136     unsigned long ia = _inf, ib = _inf;
 137     unsigned long N = this->m_Seeds.size( );
 138     for( unsigned long i = 0; i < N; ++i )
 139     {
 140       if( this->m_Seeds[ i ] == pa[ pa.size( ) - 1 ] )
 141         ia = i;
 142       if( this->m_Seeds[ i ] == pb[ pb.size( ) - 1 ] )
 143         ib = i;
 144
 145     } // rof
 146
 147     // Check if there is a front-jump between given seeds
 148     if( ia != ib )
 149     {
 150       // Compute front path
 151       std::vector< long > fpath;
 152       fpath.push_back( ia );
 153       while( ia != ib )
 154       {
 155         ia = this->m_FrontPaths[ ia ][ ib ];
 156         fpath.push_back( ia );
 157
 158       } // elihw
 159
 160       // Continue only if both fronts are connected
 161       unsigned int N = fpath.size( );
 162       if( N > 0 )
 163       {
 164         // First path: from start vertex to first collision
 165         vertices = this->GetPath(
 166           a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
 167           );
 168
 169         // Intermediary paths
 170         for( unsigned int i = 1; i < N - 1; ++i )
 171         {
 172           TVertices ipath =
 173             this->GetPath(
 174               this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
 175               this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
 176               );
 177           for( long id = 0; id < ipath.size( ); ++id )
 178             vertices.push_back( ipath[ id ] );
 179
 180         } // rof
 181
 182         // Final path: from last collision to end point
 183         TVertices lpath =
 184           this->GetPath(
 185             this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
 186             );
 187         for( long id = 0; id < lpath.size( ); ++id )
 188           vertices.push_back( lpath[ id ] );
 189
 190       } // fi
 191     }
 192     else
 193     {
 194       // Ignore common part: find common ancestor
 195       long aIt = pa.size( ) - 1;
 196       long bIt = pb.size( ) - 1;
 197       bool cont = true;
 198       while( aIt >= 0 && bIt >= 0 && cont )
 199       {
 200         cont = ( pa[ aIt ] == pb[ bIt ] );
 201         aIt--;
 202         bIt--;
 203
 204       } // elihw
 205       aIt++;
 206       bIt++;
 207
 208       // Glue both parts
 209       for( long cIt = 0; cIt <= aIt; ++cIt )
 210         vertices.push_back( pa[ cIt ] );
 211       for( ; bIt >= 0; --bIt )
 212         vertices.push_back( pb[ bIt ] );
 213
 214     } // fi
 215
 216   } // fi
 217   return( vertices );
 218 }
 219
 220 // -------------------------------------------------------------------------
 221 template< class _TVertex, class _Superclass >
 222 fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
 223 MinimumSpanningTree( )
 224   : Superclass( )
 225 {
 226 }
 227
 228 // -------------------------------------------------------------------------
 229 template< class _TVertex, class _Superclass >
 230 fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
 231 ~MinimumSpanningTree( )
 232 {
 233 }
 234
 235 #endif // __fpa__Base__MinimumSpanningTree__hxx__
 236
 237 // eof - $RCSfile$