--- /dev/null
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
+#ifndef __fpa__DataStructures__MinimumSpanningTree__hxx__
+#define __fpa__DataStructures__MinimumSpanningTree__hxx__
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+const typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+TCollisions& fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+GetCollisions( ) const
+{
+ return( this->m_Collisions );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+SetCollisions( const TCollisions& collisions )
+{
+ static const unsigned long _inf =
+ std::numeric_limits< unsigned long >::max( );
+ if( this->m_Collisions == collisions )
+ return;
+
+ this->m_Collisions = collisions;
+
+ // Prepare a front graph
+ unsigned long N = this->m_Collisions.size( );
+ _TMatrix dist( N, _TRow( N, _inf ) );
+ this->m_FrontPaths = dist;
+ for( unsigned long i = 0; i < N; ++i )
+ {
+ for( unsigned long j = 0; j < N; ++j )
+ {
+ if( this->m_Collisions[ i ][ j ].second )
+ {
+ dist[ i ][ j ] = 1;
+ dist[ j ][ i ] = 1;
+ this->m_FrontPaths[ i ][ j ] = j;
+ this->m_FrontPaths[ j ][ i ] = i;
+
+ } // fi
+
+ } // rof
+ dist[ i ][ i ] = 0;
+ this->m_FrontPaths[ i ][ i ] = i;
+
+ } // rof
+
+ // Use Floyd-Warshall to compute all possible paths between fronts
+ for( unsigned long k = 0; k < N; ++k )
+ {
+ for( unsigned long i = 0; i < N; ++i )
+ {
+ for( unsigned long j = 0; j < N; ++j )
+ {
+ // WARNING: you don't want a numeric overflow!!!
+ unsigned long dik = dist[ i ][ k ];
+ unsigned long dkj = dist[ k ][ j ];
+ unsigned long sum = _inf;
+ if( dik < _inf && dkj < _inf )
+ sum = dik + dkj;
+
+ // Ok, continue Floyd-Warshall
+ if( sum < dist[ i ][ j ] )
+ {
+ dist[ i ][ j ] = sum;
+ this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
+
+ } // fi
+
+ } // rof
+
+ } // rof
+
+ } // rof
+ this->Modified( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+ClearSeeds( )
+{
+ this->m_Seeds.clear( );
+ this->Modified( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+AddSeed( const _TVertex& seed )
+{
+ this->m_Seeds.push_back( seed );
+ this->Modified( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+TVertices fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+GetAxis( const _TVertex& a ) const
+{
+ TVertices vertices;
+ _TVertex it = a;
+ _TVertex p = this->GetParent( it );
+ while( it != p )
+ {
+ vertices.push_back( it );
+ it = p;
+ p = this->GetParent( it );
+
+ } // elihw
+ vertices.push_back( it );
+ return( vertices );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+TVertices fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+GetAxis( const _TVertex& a, const _TVertex& b ) const
+{
+ static const unsigned long _inf =
+ std::numeric_limits< unsigned long >::max( );
+
+ TVertices vertices;
+ TVertices pa = this->GetAxis( a );
+ TVertices pb = this->GetAxis( b );
+ if( pa.size( ) > 0 && pb.size( ) > 0 )
+ {
+ // Find front identifiers
+ unsigned long ia = _inf, ib = _inf;
+ unsigned long N = this->m_Seeds.size( );
+ for( unsigned long i = 0; i < N; ++i )
+ {
+ if( this->m_Seeds[ i ] == pa[ pa.size( ) - 1 ] )
+ ia = i;
+ if( this->m_Seeds[ i ] == pb[ pb.size( ) - 1 ] )
+ ib = i;
+
+ } // rof
+
+ // Check if there is a front-jump between given seeds
+ if( ia != ib )
+ {
+ // Compute front path
+ std::vector< long > fpath;
+ fpath.push_back( ia );
+ while( ia != ib )
+ {
+ ia = this->m_FrontPaths[ ia ][ ib ];
+ fpath.push_back( ia );
+
+ } // elihw
+
+ // Continue only if both fronts are connected
+ unsigned int N = fpath.size( );
+ if( N > 0 )
+ {
+ // First path: from start vertex to first collision
+ vertices = this->GetAxis(
+ a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
+ );
+
+ // Intermediary paths
+ for( unsigned int i = 1; i < N - 1; ++i )
+ {
+ TVertices ipath =
+ this->GetAxis(
+ this->m_Collisions[ fpath[ i - 1 ] ][ fpath[ i ] ].first,
+ this->m_Collisions[ fpath[ i + 1 ] ][ fpath[ i ] ].first
+ );
+ for( long id = 0; id < ipath.size( ); ++id )
+ vertices.push_back( ipath[ id ] );
+
+ } // rof
+
+ // Final path: from last collision to end point
+ TVertices lpath =
+ this->GetAxis(
+ this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
+ );
+ for( long id = 0; id < lpath.size( ); ++id )
+ vertices.push_back( lpath[ id ] );
+
+ } // fi
+ }
+ else
+ {
+ // Ignore common part: find common ancestor
+ long aIt = pa.size( ) - 1;
+ long bIt = pb.size( ) - 1;
+ bool cont = true;
+ while( aIt >= 0 && bIt >= 0 && cont )
+ {
+ cont = ( pa[ aIt ] == pb[ bIt ] );
+ aIt--;
+ bIt--;
+
+ } // elihw
+ aIt++;
+ bIt++;
+
+ // Glue both parts
+ for( long cIt = 0; cIt <= aIt; ++cIt )
+ vertices.push_back( pa[ cIt ] );
+ for( ; bIt >= 0; --bIt )
+ vertices.push_back( pb[ bIt ] );
+
+ } // fi
+
+ } // fi
+ return( vertices );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+MinimumSpanningTree( )
+ : Superclass( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+~MinimumSpanningTree( )
+{
+}
+
+#endif // __fpa__DataStructures__MinimumSpanningTree__hxx__
+// eof - $RCSfile$
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff