1 #ifndef __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
2 #define __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
6 // -------------------------------------------------------------------------
7 template< class V, class C, class B >
8 const unsigned long fpa::Base::MinimumSpanningTree< V, C, B >::INF_VALUE =
9 std::numeric_limits< unsigned long >::max( ) >> 1;
11 // -------------------------------------------------------------------------
12 template< class V, class C, class B >
13 void fpa::Base::MinimumSpanningTree< V, C, B >::
14 SetCollisions( const TCollisions& collisions )
16 this->m_Collisions = collisions;
18 // Prepare fronts graph using Floyd-Warshall
19 unsigned long nSeeds = this->m_Collisions.size( );
20 _TMatrix dist( nSeeds, _TRow( nSeeds, Self::INF_VALUE ) );
21 this->m_FrontPaths = dist;
23 for( unsigned long i = 0; i < nSeeds; ++i )
25 for( unsigned long j = 0; j < nSeeds; ++j )
27 if( this->m_Collisions[ i ][ j ].second )
31 this->m_FrontPaths[ i ][ j ] = j;
32 this->m_FrontPaths[ j ][ i ] = i;
38 this->m_FrontPaths[ i ][ i ] = i;
41 for( unsigned long k = 0; k < nSeeds; ++k )
43 for( unsigned long i = 0; i < nSeeds; ++i )
45 for( unsigned long j = 0; j < nSeeds; ++j )
47 if( ( dist[ i ][ k ] + dist[ k ][ j ] ) < dist[ i ][ j ] )
49 dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ];
50 this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
62 // -------------------------------------------------------------------------
63 template< class V, class C, class B >
64 void fpa::Base::MinimumSpanningTree< V, C, B >::
65 GetPath( std::vector< V >& path, const V& a, const V& b ) const
67 typename TDecorated::const_iterator aIt = this->Get( ).find( a );
68 typename TDecorated::const_iterator bIt = this->Get( ).find( b );
70 if( aIt == this->Get( ).end( ) || bIt == this->Get( ).end( ) )
73 short fa = aIt->second.second;
74 short fb = bIt->second.second;
78 std::vector< V > ap, bp;
83 typename std::vector< V >::const_reverse_iterator raIt, rbIt;
86 while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
92 if( raIt != ap.rbegin( ) ) --raIt;
95 typename std::vector< V >::const_iterator iaIt = ap.begin( );
96 for( ; iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
97 path.push_back( *iaIt );
100 for( ; rbIt != bp.rend( ); ++rbIt )
101 path.push_back( *rbIt );
105 // Use this->m_FrontPaths from Floyd-Warshall
106 if( this->m_FrontPaths[ fa ][ fb ] != Self::INF_VALUE )
108 // Compute front path
109 std::vector< long > fpath;
110 fpath.push_back( fa );
113 fa = this->m_FrontPaths[ fa ][ fb ];
114 fpath.push_back( fa );
118 // Continue only if both fronts are connected
119 unsigned int N = fpath.size( );
122 // First path: from start vertex to first collision
124 path, a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
127 // Intermediary paths
128 for( unsigned int i = 1; i < N - 1; ++i )
132 this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
133 this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
138 // Final path: from last collision to end point
141 this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
151 // -------------------------------------------------------------------------
152 template< class V, class C, class B >
153 fpa::Base::MinimumSpanningTree< V, C, B >::
154 MinimumSpanningTree( )
159 // -------------------------------------------------------------------------
160 template< class V, class C, class B >
161 fpa::Base::MinimumSpanningTree< V, C, B >::
162 ~MinimumSpanningTree( )
166 // -------------------------------------------------------------------------
167 template< class V, class C, class B >
168 void fpa::Base::MinimumSpanningTree< V, C, B >::
169 _Path( std::vector< V >& path, const V& a ) const
171 typename TDecorated::const_iterator dIt = this->Get( ).find( a );
172 if( dIt != this->Get( ).end( ) )
176 path.push_back( dIt->first );
177 dIt = this->Get( ).find( dIt->second.first );
179 } while( dIt->first != dIt->second.first && dIt != this->Get( ).end( ) );
181 if( dIt != this->Get( ).end( ) )
182 path.push_back( dIt->first );
187 #endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__