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->Modified( );
  80 }
  81
  82 // -------------------------------------------------------------------------
  83 template< class _TVertex, class _Superclass >
  84 void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
  85 ClearSeeds( )
  86 {
  87   this->m_Seeds.clear( );
  88   this->Modified( );
  89 }
  90
  91 // -------------------------------------------------------------------------
  92 template< class _TVertex, class _Superclass >
  93 void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
  94 AddSeed( const _TVertex& seed )
  95 {
  96   this->m_Seeds.push_back( seed );
  97   this->Modified( );
  98 }
  99
 100 // -------------------------------------------------------------------------
 101 template< class _TVertex, class _Superclass >
 102 typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 103 TVertices fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 104 GetPath( const _TVertex& a ) const
 105 {
 106   TVertices vertices;
 107   _TVertex it = a;
 108   _TVertex p = this->GetParent( it );
 109   while( it != p )
 110   {
 111     vertices.push_back( it );
 112     it = p;
 113     p = this->GetParent( it );
 114
 115   } // elihw
 116   vertices.push_back( it );
 117   return( vertices );
 118 }
 119
 120 // -------------------------------------------------------------------------
 121 template< class _TVertex, class _Superclass >
 122 typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 123 TVertices fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 124 GetPath( const _TVertex& a, const _TVertex& b ) const
 125 {
 126   static const unsigned long _inf =
 127     std::numeric_limits< unsigned long >::max( );
 128
 129   TVertices vertices;
 130   TVertices pa = this->GetPath( a );
 131   TVertices pb = this->GetPath( b );
 132   if( pa.size( ) > 0 && pb.size( ) > 0 )
 133   {
 134     // Find front identifiers
 135     unsigned long ia = _inf, ib = _inf;
 136     unsigned long N = this->m_Seeds.size( );
 137     for( unsigned long i = 0; i < N; ++i )
 138     {
 139       if( this->m_Seeds[ i ] == pa[ pa.size( ) - 1 ] )
 140         ia = i;
 141       if( this->m_Seeds[ i ] == pb[ pb.size( ) - 1 ] )
 142         ib = i;
 143
 144     } // rof
 145
 146     // Check if there is a front-jump between given seeds
 147     if( ia != ib )
 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         vertices = 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 - 1 ] ][ fpath[ i ] ].first,
 174               this->m_Collisions[ fpath[ i + 1 ] ][ fpath[ i ] ].first
 175               );
 176           for( long id = 0; id < ipath.size( ); ++id )
 177             vertices.push_back( ipath[ id ] );
 178
 179         } // rof
 180
 181         // Final path: from last collision to end point
 182         TVertices lpath =
 183           this->GetPath(
 184             this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
 185             );
 186         for( long id = 0; id < lpath.size( ); ++id )
 187           vertices.push_back( lpath[ id ] );
 188
 189       } // fi
 190     }
 191     else
 192     {
 193       // Ignore common part: find common ancestor
 194       long aIt = pa.size( ) - 1;
 195       long bIt = pb.size( ) - 1;
 196       bool cont = true;
 197       while( aIt >= 0 && bIt >= 0 && cont )
 198       {
 199         cont = ( pa[ aIt ] == pb[ bIt ] );
 200         aIt--;
 201         bIt--;
 202
 203       } // elihw
 204       aIt++;
 205       bIt++;
 206
 207       // Glue both parts
 208       for( long cIt = 0; cIt <= aIt; ++cIt )
 209         vertices.push_back( pa[ cIt ] );
 210       for( ; bIt >= 0; --bIt )
 211         vertices.push_back( pb[ bIt ] );
 212
 213     } // fi
 214
 215   } // fi
 216   return( vertices );
 217 }
 218
 219 // -------------------------------------------------------------------------
 220 template< class _TVertex, class _Superclass >
 221 fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 222 MinimumSpanningTree( )
 223   : Superclass( )
 224 {
 225 }
 226
 227 // -------------------------------------------------------------------------
 228 template< class _TVertex, class _Superclass >
 229 fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
 230 ~MinimumSpanningTree( )
 231 {
 232 }
 233
 234 #endif // __fpa__DataStructures__MinimumSpanningTree__hxx__
 235 // eof - $RCSfile$