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 _TSuperclass, class _TVertex >
   8 const unsigned long fpa::Base::
   9 MinimumSpanningTree< _TSuperclass, _TVertex >::INF_VALUE =
  10   std::numeric_limits< unsigned long >::max( );
  11
  12 // -------------------------------------------------------------------------
  13 template< class _TSuperclass, class _TVertex >
  14 void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
  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
  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         if( ( dist[ i ][ k ] + dist[ k ][ j ] ) < dist[ i ][ j ] )
  49         {
  50           dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ];
  51           this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
  52
  53         } // fi
  54
  55       } // rof
  56
  57     } // rof
  58
  59   } // rof
  60   this->Modified( );
  61 }
  62
  63 // -------------------------------------------------------------------------
  64 template< class _TSuperclass, class _TVertex >
  65 typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
  66 TVertices fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
  67 GetPath( const TVertex& a ) const
  68 {
  69   TVertices path;
  70   if( this->_HasVertex( a ) )
  71     this->_Path( path, a );
  72   return( path );
  73 }
  74
  75 // -------------------------------------------------------------------------
  76 template< class _TSuperclass, class _TVertex >
  77 typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
  78 TVertices fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
  79 GetPath( const TVertex& a, const TVertex& b ) const
  80 {
  81   TVertices path;
  82
  83   // Check existence
  84   if( !this->_HasVertex( a ) || !this->_HasVertex( b ) )
  85     return( path );
  86
  87   // Get front ids
  88   short fa = this->_FrontId( a );
  89   short fb = this->_FrontId( b );
  90
  91   if( fa == fb )
  92   {
  93     // Get paths
  94     TVertices ap, bp;
  95     this->_Path( ap, a );
  96     this->_Path( bp, b );
  97
  98     // Ignore common part: find common ancestor
  99     auto raIt = ap.rbegin( );
 100     auto rbIt = bp.rbegin( );
 101     while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
 102     {
 103       ++raIt;
 104       ++rbIt;
 105
 106     } // elihw
 107     if( raIt != ap.rbegin( ) ) --raIt;
 108     if( rbIt != bp.rbegin( ) ) --rbIt;
 109
 110     // Add part from a
 111     for( auto iaIt = ap.begin( ); iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
 112       path.push_back( *iaIt );
 113
 114     // Add part from b
 115     for( ; rbIt != bp.rend( ); ++rbIt )
 116       path.push_back( *rbIt );
 117   }
 118   else
 119   {
 120     // Use this->m_FrontPaths from Floyd-Warshall
 121     if( this->m_FrontPaths[ fa ][ fb ] < Self::INF_VALUE )
 122     {
 123       // Compute front path
 124       std::vector< long > fpath;
 125       fpath.push_back( fa );
 126       while( fa != fb )
 127       {
 128         fa = this->m_FrontPaths[ fa ][ fb ];
 129         fpath.push_back( fa );
 130
 131       } // elihw
 132
 133       // Continue only if both fronts are connected
 134       unsigned int N = fpath.size( );
 135       if( N > 0 )
 136       {
 137         // First path: from start vertex to first collision
 138         path = this->GetPath(
 139           a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
 140           );
 141
 142         // Intermediary paths
 143         for( unsigned int i = 1; i < N - 1; ++i )
 144         {
 145           TVertices ipath =
 146             this->GetPath(
 147               this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
 148               this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
 149               );
 150           path.insert( path.end( ), ipath.begin( ), ipath.end( ) );
 151
 152         } // rof
 153
 154         // Final path: from last collision to end point
 155         TVertices lpath =
 156           this->GetPath(
 157             this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
 158             );
 159         path.insert( path.end( ), lpath.begin( ), lpath.end( ) );
 160
 161       } // fi
 162
 163     } // fi
 164
 165   } // fi
 166   return( path );
 167 }
 168
 169 // -------------------------------------------------------------------------
 170 template< class _TSuperclass, class _TVertex >
 171 typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
 172 TPoints fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
 173 GetEuclideanPath( const TVertex& a ) const
 174 {
 175   TPoints points;
 176   return( points );
 177 }
 178
 179 // -------------------------------------------------------------------------
 180 template< class _TSuperclass, class _TVertex >
 181 typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
 182 TPoints fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
 183 GetEuclideanPath( const TVertex& a, const TVertex& b ) const
 184 {
 185   TPoints points;
 186   return( points );
 187 }
 188
 189 // -------------------------------------------------------------------------
 190 template< class _TSuperclass, class _TVertex >
 191 bool fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
 192 IsDefinedInEuclideanSpace( ) const
 193 {
 194   return( false );
 195 }
 196
 197 // -------------------------------------------------------------------------
 198 template< class _TSuperclass, class _TVertex >
 199 void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
 200 SetNode(
 201   const TVertex& v, const TVertex& p,
 202   const short& fid, const double& cost
 203   )
 204 {
 205   typedef typename TNodeQueue::value_type _TNodeQueueValue;
 206   if( this->m_FillNodeQueue )
 207     this->m_NodeQueue.insert( _TNodeQueueValue( cost, v ) );
 208 }
 209
 210 // -------------------------------------------------------------------------
 211 template< class _TSuperclass, class _TVertex >
 212 void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
 213 Clear( )
 214 {
 215   this->m_NodeQueue.clear( );
 216 }
 217
 218 // -------------------------------------------------------------------------
 219 template< class _TSuperclass, class _TVertex >
 220 fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
 221 MinimumSpanningTree( )
 222   : Superclass( ),
 223     m_FillNodeQueue( false )
 224 {
 225 }
 226
 227 // -------------------------------------------------------------------------
 228 template< class _TSuperclass, class _TVertex >
 229 fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
 230 ~MinimumSpanningTree( )
 231 {
 232 }
 233
 234 #endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
 235
 236 // eof - $RCSfile$