lib/fpa/Base/MinimumSpanningTree.hxx

   1 #ifndef __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
   2 #define __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
   3
   4 #include <limits>
   5
   6 // -------------------------------------------------------------------------
   7 template< class _TVertex, class _TScalar, class _TVertexCompare >
   8 const unsigned long fpa::Base::
   9 MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::INF_VALUE =
  10   std::numeric_limits< unsigned long >::max( );
  11
  12 // -------------------------------------------------------------------------
  13 template< class _TVertex, class _TScalar, class _TVertexCompare >
  14 void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
  15 SetCollisions( const TCollisions& collisions )
  16 {
  17   // Prepare a front graph
  18   this->m_Collisions = collisions;
  19   unsigned long nSeeds = this->m_Collisions.size( );
  20   _TMatrix dist( nSeeds, _TRow( nSeeds, Self::INF_VALUE ) );
  21   this->m_FrontPaths = dist;
  22   for( unsigned long i = 0; i < nSeeds; ++i )
  23   {
  24     for( unsigned long j = 0; j < nSeeds; ++j )
  25     {
  26       if( this->m_Collisions[ i ][ j ].second )
  27       {
  28         dist[ i ][ j ] = 1;
  29         dist[ j ][ i ] = 1;
  30         this->m_FrontPaths[ i ][ j ] = j;
  31         this->m_FrontPaths[ j ][ i ] = i;
  32
  33       } // fi
  34
  35     } // rof
  36     dist[ i ][ i ] = 0;
  37     this->m_FrontPaths[ i ][ i ] = i;
  38
  39   } // rof
  40
  41   // Use Floyd-Warshall to compute all possible paths between fronts
  42   for( unsigned long k = 0; k < nSeeds; ++k )
  43   {
  44     for( unsigned long i = 0; i < nSeeds; ++i )
  45     {
  46       for( unsigned long j = 0; j < nSeeds; ++j )
  47       {
  48         // WARNING: you don't want a numeric overflow!!!
  49         unsigned long dik = dist[ i ][ k ];
  50         unsigned long dkj = dist[ k ][ j ];
  51         unsigned long sum = Self::INF_VALUE;
  52         if( dik < Self::INF_VALUE && dkj < Self::INF_VALUE )
  53           sum = dik + dkj;
  54
  55         // Ok, continue Floyd-Warshall
  56         if( sum < dist[ i ][ j ] )
  57         {
  58           dist[ i ][ j ] = sum;
  59           this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
  60
  61         } // fi
  62
  63       } // rof
  64
  65     } // rof
  66
  67   } // rof
  68   this->Modified( );
  69 }
  70
  71 // -------------------------------------------------------------------------
  72 template< class _TVertex, class _TScalar, class _TVertexCompare >
  73 typename
  74 fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
  75 TVertices
  76 fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
  77 GetPath( const _TVertex& a ) const
  78 {
  79   TVertices path;
  80   if( this->_HasVertex( a ) )
  81     this->_Path( path, a );
  82   return( path );
  83 }
  84
  85 // -------------------------------------------------------------------------
  86 template< class _TVertex, class _TScalar, class _TVertexCompare >
  87 typename
  88 fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
  89 TVertices
  90 fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
  91 GetPath( const _TVertex& a, const _TVertex& b ) const
  92 {
  93   TVertices path;
  94
  95   // Check existence
  96   if( !this->_HasVertex( a ) || !this->_HasVertex( b ) )
  97     return( path );
  98
  99   // Get front ids
 100   long fa = this->_FrontId( a ) - 1;
 101   long fb = this->_FrontId( b ) - 1;
 102
 103   if( fa == fb )
 104   {
 105     // Get paths
 106     TVertices ap, bp;
 107     this->_Path( ap, a );
 108     this->_Path( bp, b );
 109
 110     // Ignore common part: find common ancestor
 111     auto raIt = ap.rbegin( );
 112     auto rbIt = bp.rbegin( );
 113     while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
 114     {
 115       ++raIt;
 116       ++rbIt;
 117
 118     } // elihw
 119     if( raIt != ap.rbegin( ) ) --raIt;
 120     if( rbIt != bp.rbegin( ) ) --rbIt;
 121
 122     // Add part from a
 123     for( auto iaIt = ap.begin( ); iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
 124       path.push_back( *iaIt );
 125
 126     // Add part from b
 127     for( ; rbIt != bp.rend( ); ++rbIt )
 128       path.push_back( *rbIt );
 129   }
 130   else
 131   {
 132     // Use this->m_FrontPaths from Floyd-Warshall
 133     if( this->m_FrontPaths[ fa ][ fb ] < Self::INF_VALUE )
 134     {
 135       // Compute front path
 136       std::vector< long > fpath;
 137       fpath.push_back( fa );
 138       while( fa != fb )
 139       {
 140         fa = this->m_FrontPaths[ fa ][ fb ];
 141         fpath.push_back( fa );
 142
 143       } // elihw
 144
 145       // Continue only if both fronts are connected
 146       unsigned int N = fpath.size( );
 147       if( N > 0 )
 148       {
 149         // First path: from start vertex to first collision
 150         path = this->GetPath(
 151           a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
 152           );
 153
 154         // Intermediary paths
 155         for( unsigned int i = 1; i < N - 1; ++i )
 156         {
 157           TVertices ipath =
 158             this->GetPath(
 159               this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
 160               this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
 161               );
 162           path.insert( path.end( ), ipath.begin( ), ipath.end( ) );
 163
 164         } // rof
 165
 166         // Final path: from last collision to end point
 167         TVertices lpath =
 168           this->GetPath(
 169             this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
 170             );
 171         path.insert( path.end( ), lpath.begin( ), lpath.end( ) );
 172
 173         // Remove repeated vertices
 174         auto p = path.begin( );
 175         auto q = p;
 176         q++;
 177         while( q != path.end( ) )
 178         {
 179           if( *q == *p )
 180           {
 181             p = path.erase( p );
 182             q = p;
 183           }
 184           else
 185             ++p;
 186           ++q;
 187
 188         } // elihw
 189
 190       } // fi
 191
 192     } // fi
 193
 194   } // fi
 195   return( path );
 196 }
 197
 198 // -------------------------------------------------------------------------
 199 template< class _TVertex, class _TScalar, class _TVertexCompare >
 200 void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
 201 SetNode(
 202   const _TVertex& vertex, const _TVertex& parent,
 203   const long& fid, const _TScalar& result
 204   )
 205 {
 206   this->Get( )[ vertex ] = TParent( parent, TData( result, fid ) );
 207   this->Modified( );
 208 }
 209
 210 // -------------------------------------------------------------------------
 211 template< class _TVertex, class _TScalar, class _TVertexCompare >
 212 void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
 213 Clear( )
 214 {
 215   this->Get( ).clear( );
 216   this->m_NodeQueue.clear( );
 217 }
 218
 219 // -------------------------------------------------------------------------
 220 template< class _TVertex, class _TScalar, class _TVertexCompare >
 221 fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
 222 MinimumSpanningTree( )
 223   : Superclass( ),
 224     m_FillNodeQueue( false )
 225 {
 226 }
 227
 228 // -------------------------------------------------------------------------
 229 template< class _TVertex, class _TScalar, class _TVertexCompare >
 230 fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
 231 ~MinimumSpanningTree( )
 232 {
 233 }
 234
 235 // -------------------------------------------------------------------------
 236 template< class _TVertex, class _TScalar, class _TVertexCompare >
 237 bool fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
 238 _HasVertex( const _TVertex& a ) const
 239 {
 240   return( this->Get( ).find( a ) != this->Get( ).end( ) );
 241 }
 242
 243 // -------------------------------------------------------------------------
 244 template< class _TVertex, class _TScalar, class _TVertexCompare >
 245 long fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
 246 _FrontId( const _TVertex& a ) const
 247 {
 248   static const long MAX_ID = std::numeric_limits< long >::max( );
 249   auto i = this->Get( ).find( a );
 250   if( i != this->Get( ).end( ) )
 251     return( i->second.second.second );
 252   else
 253     return( MAX_ID );
 254 }
 255
 256 // -------------------------------------------------------------------------
 257 template< class _TVertex, class _TScalar, class _TVertexCompare >
 258 void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
 259 _Path( TVertices& path, const _TVertex& a ) const
 260 {
 261   auto& m = this->Get( );
 262   auto it = m.find( a );
 263   if( it != m.end( ) )
 264   {
 265     do
 266     {
 267       path.push_back( it->first );
 268       it = m.find( it->second.first );
 269
 270     } while( it->first != it->second.first );
 271     path.push_back( it->first );
 272
 273   } // fi
 274 }
 275
 276 #endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
 277
 278 // eof - $RCSfile$