1 // =========================================================================
2 // @author Leonardo Florez Valencia
3 // @email florez-l@javeriana.edu.co
4 // =========================================================================
6 #ifndef __fpa__Base__MinimumSpanningTree__hxx__
7 #define __fpa__Base__MinimumSpanningTree__hxx__
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
15 return( this->m_Collisions );
18 // -------------------------------------------------------------------------
19 template< class _TVertex, class _Superclass >
20 void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
21 SetCollisions( const TCollisions& collisions )
23 static const unsigned long _inf =
24 std::numeric_limits< unsigned long >::max( );
25 if( this->m_Collisions == collisions )
28 this->m_Collisions = collisions;
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 )
36 for( unsigned long j = 0; j < N; ++j )
38 if( this->m_Collisions[ i ][ j ].second )
42 this->m_FrontPaths[ i ][ j ] = j;
43 this->m_FrontPaths[ j ][ i ] = i;
49 this->m_FrontPaths[ i ][ i ] = i;
53 // Use Floyd-Warshall to compute all possible paths between fronts
54 for( unsigned long k = 0; k < N; ++k )
56 for( unsigned long i = 0; i < N; ++i )
58 for( unsigned long j = 0; j < N; ++j )
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 )
67 // Ok, continue Floyd-Warshall
68 if( sum < dist[ i ][ j ] )
71 this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
83 // -------------------------------------------------------------------------
84 template< class _TVertex, class _Superclass >
85 void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
88 this->m_Seeds.clear( );
89 if( this->m_DataObject != NULL )
90 this->m_DataObject->Modified( );
93 // -------------------------------------------------------------------------
94 template< class _TVertex, class _Superclass >
95 void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
96 AddSeed( const _TVertex& seed )
98 this->m_Seeds.push_back( seed );
99 if( this->m_DataObject != NULL )
100 this->m_DataObject->Modified( );
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
111 _TVertex p = this->GetParent( it );
114 vertices.push_back( it );
116 p = this->GetParent( it );
119 vertices.push_back( it );
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
129 static const unsigned long _inf =
130 std::numeric_limits< unsigned long >::max( );
133 TVertices pa = this->GetPath( a );
134 TVertices pb = this->GetPath( b );
135 if( pa.size( ) > 0 && pb.size( ) > 0 )
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 )
142 if( this->m_Seeds[ i ] == pa[ pa.size( ) - 1 ] )
144 if( this->m_Seeds[ i ] == pb[ pb.size( ) - 1 ] )
149 // Check if there is a front-jump between given seeds
152 // Compute front path
153 std::vector< long > fpath;
154 fpath.push_back( ia );
157 ia = this->m_FrontPaths[ ia ][ ib ];
158 fpath.push_back( ia );
162 // Continue only if both fronts are connected
163 unsigned int N = fpath.size( );
166 // First path: from start vertex to first collision
167 vertices = this->GetPath(
168 a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
171 // Intermediary paths
172 for( unsigned int i = 1; i < N - 1; ++i )
176 this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
177 this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
179 for( long id = 0; id < ipath.size( ); ++id )
180 vertices.push_back( ipath[ id ] );
184 // Final path: from last collision to end point
187 this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
189 for( long id = 0; id < lpath.size( ); ++id )
190 vertices.push_back( lpath[ id ] );
196 // Ignore common part: find common ancestor
197 long aIt = pa.size( ) - 1;
198 long bIt = pb.size( ) - 1;
200 while( aIt >= 0 && bIt >= 0 && cont )
202 cont = ( pa[ aIt ] == pb[ bIt ] );
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 ] );
222 // -------------------------------------------------------------------------
223 template< class _TVertex, class _Superclass >
224 fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
225 MinimumSpanningTree( )
230 // -------------------------------------------------------------------------
231 template< class _TVertex, class _Superclass >
232 fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
233 ~MinimumSpanningTree( )
237 #endif // __fpa__Base__MinimumSpanningTree__hxx__