1 #ifndef __FPA__BASE__TREEEXTRACTOR__HXX__
2 #define __FPA__BASE__TREEEXTRACTOR__HXX__
6 // -------------------------------------------------------------------------
8 const unsigned long fpa::Base::TreeExtractor< A >::INF_VALUE =
9 std::numeric_limits< unsigned long >::max( ) >> 1;
11 // -------------------------------------------------------------------------
13 unsigned int fpa::Base::TreeExtractor< A >::
14 AddLeaf( const TVertex& leaf )
16 this->m_Leafs.push_back( leaf );
18 return( this->m_Leafs.size( ) - 1 );
21 // -------------------------------------------------------------------------
23 unsigned int fpa::Base::TreeExtractor< A >::
24 GetNumberOfLeafs( ) const
26 return( this->m_Leafs.size( ) );
29 // -------------------------------------------------------------------------
31 const typename fpa::Base::TreeExtractor< A >::
32 TVertex& fpa::Base::TreeExtractor< A >::
33 GetLeaf( const unsigned int& id ) const
35 static const TVertex zero;
36 if( id < this->m_Leafs.size( ) )
37 return( this->m_Leafs[ id ] );
42 // -------------------------------------------------------------------------
44 fpa::Base::TreeExtractor< A >::
50 // -------------------------------------------------------------------------
52 fpa::Base::TreeExtractor< A >::
57 // -------------------------------------------------------------------------
59 void fpa::Base::TreeExtractor< A >::
62 this->Superclass::_BeforeLoop( );
63 this->m_Tree.clear( );
66 // -------------------------------------------------------------------------
68 void fpa::Base::TreeExtractor< A >::
71 this->Superclass::_AfterLoop( );
73 // Prepare fronts graph using Floyd-Warshall
74 unsigned long nSeeds = this->GetNumberOfSeeds( );
75 _TMatrix dist( nSeeds, _TRow( nSeeds, Self::INF_VALUE ) );
76 this->m_FrontPaths = dist;
78 for( unsigned long i = 0; i < nSeeds; ++i )
80 for( unsigned long j = 0; j < nSeeds; ++j )
82 if( this->m_CollisionSites[ i ][ j ].second )
86 this->m_FrontPaths[ i ][ j ] = j;
87 this->m_FrontPaths[ j ][ i ] = i;
93 this->m_FrontPaths[ i ][ i ] = i;
96 for( unsigned long k = 0; k < nSeeds; ++k )
98 for( unsigned long i = 0; i < nSeeds; ++i )
100 for( unsigned long j = 0; j < nSeeds; ++j )
102 if( ( dist[ i ][ k ] + dist[ k ][ j ] ) < dist[ i ][ j ] )
104 dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ];
105 this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
116 this->m_Tree.clear( );
117 typename TVertices::const_iterator vIt = this->m_Leafs.begin( );
118 for( ; vIt != this->m_Leafs.end( ); ++vIt )
120 TVertices path = this->_Path( this->m_Root, *vIt );
121 typename TVertices::const_iterator pIt = path.begin( );
122 TVertex parent = *pIt;
123 for( ; pIt != path.end( ); ++pIt )
125 this->m_Tree[ *pIt ] = parent;
133 // -------------------------------------------------------------------------
135 typename fpa::Base::TreeExtractor< A >::
136 TVertices fpa::Base::TreeExtractor< A >::
137 _Path( const TVertex& s, const TVertex& e )
141 // Check if both vertices belong to the same front or if collisions
142 // should be analyzed.
143 _TFrontId fs = this->_FrontId( s );
144 _TFrontId fe = this->_FrontId( e );
147 // Path from start vertex until seed
149 TVertex parent = this->_Parent( vIt );
150 while( parent != vIt )
154 parent = this->_Parent( vIt );
159 // Path from end vertex until seed
161 parent = this->_Parent( vIt );
162 while( parent != vIt )
166 parent = this->_Parent( vIt );
171 // Erase duplicate vertices
172 if( pS.size( ) > 0 && pE.size( ) > 0 )
174 bool cont = ( pS.back( ) == pE.back( ) );
176 TVertex lastVertex = pS.back( );
181 lastVertex = pS.back( );
185 cont = ( pS.size( ) > 0 && pE.size( ) > 0 );
187 cont = ( pS.back( ) == pE.back( ) );
191 pS.push_back( lastVertex );
195 // Contatenate both paths
196 pS.insert( pS.end( ), pE.rbegin( ), pE.rend( ) );
200 // Use this->m_FrontPaths from Floyd-Warshall
201 if( this->m_FrontPaths[ fs ][ fe ] != Self::INF_VALUE )
203 // Compute front path
204 std::vector< unsigned long > fpath;
205 fpath.push_back( fs );
208 fs = this->m_FrontPaths[ fs ][ fe ];
209 fpath.push_back( fs );
213 // Continue only if both fronts are connected
214 unsigned int N = fpath.size( );
217 // First path: from start vertex to first collision
219 s, this->m_CollisionSites[ fpath[ 0 ] ][ fpath[ 1 ] ].first
222 // Intermediary paths
223 for( unsigned int i = 1; i < N - 1; ++i )
226 this->m_CollisionSites[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
227 this->m_CollisionSites[ fpath[ i ] ][ fpath[ i + 1 ] ].first
229 pS.insert( pS.end( ), pE.begin( ), pE.end( ) );
233 // Final path: from last collision to end point
235 this->m_CollisionSites[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first,
238 pS.insert( pS.end( ), pE.begin( ), pE.end( ) );
248 #endif // __FPA__BASE__TREEEXTRACTOR__HXX__