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