1 // =========================================================================
2 // @author Leonardo Florez Valencia
3 // @email florez-l@javeriana.edu.co
4 // =========================================================================
5 #ifndef __fpa__DataStructures__MinimumSpanningTree__hxx__
6 #define __fpa__DataStructures__MinimumSpanningTree__hxx__
8 // -------------------------------------------------------------------------
9 template< class _TVertex, class _Superclass >
10 const typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
11 TCollisions& fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
12 GetCollisions( ) const
14 return( this->m_Collisions );
17 // -------------------------------------------------------------------------
18 template< class _TVertex, class _Superclass >
19 void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
20 SetCollisions( const TCollisions& collisions )
22 static const unsigned long _inf =
23 std::numeric_limits< unsigned long >::max( );
24 if( this->m_Collisions == collisions )
27 this->m_Collisions = collisions;
29 // Prepare a front graph
30 unsigned long N = this->m_Collisions.size( );
31 _TMatrix dist( N, _TRow( N, _inf ) );
32 this->m_FrontPaths = dist;
33 for( unsigned long i = 0; i < N; ++i )
35 for( unsigned long j = 0; j < N; ++j )
37 if( this->m_Collisions[ i ][ j ].second )
41 this->m_FrontPaths[ i ][ j ] = j;
42 this->m_FrontPaths[ j ][ i ] = i;
48 this->m_FrontPaths[ i ][ i ] = i;
52 // Use Floyd-Warshall to compute all possible paths between fronts
53 for( unsigned long k = 0; k < N; ++k )
55 for( unsigned long i = 0; i < N; ++i )
57 for( unsigned long j = 0; j < N; ++j )
59 // WARNING: you don't want a numeric overflow!!!
60 unsigned long dik = dist[ i ][ k ];
61 unsigned long dkj = dist[ k ][ j ];
62 unsigned long sum = _inf;
63 if( dik < _inf && dkj < _inf )
66 // Ok, continue Floyd-Warshall
67 if( sum < dist[ i ][ j ] )
70 this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
82 // -------------------------------------------------------------------------
83 template< class _TVertex, class _Superclass >
84 void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
87 this->m_Seeds.clear( );
91 // -------------------------------------------------------------------------
92 template< class _TVertex, class _Superclass >
93 void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
94 AddSeed( const _TVertex& seed )
96 this->m_Seeds.push_back( seed );
100 // -------------------------------------------------------------------------
101 template< class _TVertex, class _Superclass >
102 typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
103 TVertices fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
104 GetPath( const _TVertex& a ) const
108 _TVertex p = this->GetParent( it );
111 vertices.push_back( it );
113 p = this->GetParent( it );
116 vertices.push_back( it );
120 // -------------------------------------------------------------------------
121 template< class _TVertex, class _Superclass >
122 typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
123 TVertices fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
124 GetPath( const _TVertex& a, const _TVertex& b ) const
126 static const unsigned long _inf =
127 std::numeric_limits< unsigned long >::max( );
130 TVertices pa = this->GetPath( a );
131 TVertices pb = this->GetPath( b );
132 if( pa.size( ) > 0 && pb.size( ) > 0 )
134 // Find front identifiers
135 unsigned long ia = _inf, ib = _inf;
136 unsigned long N = this->m_Seeds.size( );
137 for( unsigned long i = 0; i < N; ++i )
139 if( this->m_Seeds[ i ] == pa[ pa.size( ) - 1 ] )
141 if( this->m_Seeds[ i ] == pb[ pb.size( ) - 1 ] )
146 // Check if there is a front-jump between given seeds
149 // Compute front path
150 std::vector< long > fpath;
151 fpath.push_back( ia );
154 ia = this->m_FrontPaths[ ia ][ ib ];
155 fpath.push_back( ia );
159 // Continue only if both fronts are connected
160 unsigned int N = fpath.size( );
163 // First path: from start vertex to first collision
164 vertices = this->GetPath(
165 a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
168 // Intermediary paths
169 for( unsigned int i = 1; i < N - 1; ++i )
173 this->m_Collisions[ fpath[ i - 1 ] ][ fpath[ i ] ].first,
174 this->m_Collisions[ fpath[ i + 1 ] ][ fpath[ i ] ].first
176 for( long id = 0; id < ipath.size( ); ++id )
177 vertices.push_back( ipath[ id ] );
181 // Final path: from last collision to end point
184 this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
186 for( long id = 0; id < lpath.size( ); ++id )
187 vertices.push_back( lpath[ id ] );
193 // Ignore common part: find common ancestor
194 long aIt = pa.size( ) - 1;
195 long bIt = pb.size( ) - 1;
197 while( aIt >= 0 && bIt >= 0 && cont )
199 cont = ( pa[ aIt ] == pb[ bIt ] );
208 for( long cIt = 0; cIt <= aIt; ++cIt )
209 vertices.push_back( pa[ cIt ] );
210 for( ; bIt >= 0; --bIt )
211 vertices.push_back( pb[ bIt ] );
219 // -------------------------------------------------------------------------
220 template< class _TVertex, class _Superclass >
221 fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
222 MinimumSpanningTree( )
227 // -------------------------------------------------------------------------
228 template< class _TVertex, class _Superclass >
229 fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
230 ~MinimumSpanningTree( )
234 #endif // __fpa__DataStructures__MinimumSpanningTree__hxx__