lib/fpa/DataStructures/MinimumSpanningTree.hxx

   1 // =========================================================================
   2 // @author Leonardo Florez Valencia
   3 // @email florez-l@javeriana.edu.co
   4 // =========================================================================
   5 #ifndef __fpa__DataStructures__MinimumSpanningTree__hxx__
   6 #define __fpa__DataStructures__MinimumSpanningTree__hxx__
   7
   8 // -------------------------------------------------------------------------
   9 template< class _TVertex, class _Superclass >
  10 const typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
  11 TCollisions& fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
  12 GetCollisions( ) const
  13 {
  14   return( this->m_Collisions );
  15 }
  16
  17 // -------------------------------------------------------------------------
  18 template< class _TVertex, class _Superclass >
  19 void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
  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->m_Seeds.resize( N );
  80   this->Modified( );
  81 }
  82
  83 // -------------------------------------------------------------------------
  84 template< class _TVertex, class _Superclass >
  85 void fpa::DataStructures::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::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
  95 AddSeed( const _TVertex& seed, unsigned long fId )
  96 {
  97   this->m_Seeds[ fId - 1 ] = seed;
  98   this->Modified( );
  99 }
 100
 101 // -------------------------------------------------------------------------
 102 template< class _TVertex, class _Superclass >
 103 typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 104 TVertices fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 105 GetAxis( 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::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 124 TVertices fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 125 GetAxis( 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->GetAxis( a );
 132   TVertices pb = this->GetAxis( 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->GetAxis(
 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->GetAxis(
 174               this->m_Collisions[ fpath[ i - 1 ] ][ fpath[ i ] ].first,
 175               this->m_Collisions[ fpath[ i + 1 ] ][ fpath[ i ] ].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->GetAxis(
 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::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 223 MinimumSpanningTree( )
 224   : Superclass( )
 225 {
 226 }
 227
 228 // -------------------------------------------------------------------------
 229 template< class _TVertex, class _Superclass >
 230 fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 231 ~MinimumSpanningTree( )
 232 {
 233 }
 234
 235 #endif // __fpa__DataStructures__MinimumSpanningTree__hxx__
 236 // eof - $RCSfile$