#include <limits>
// -------------------------------------------------------------------------
-template< class V, class C, class B >
-const unsigned long fpa::Base::MinimumSpanningTree< V, C, B >::INF_VALUE =
- std::numeric_limits< unsigned long >::max( ) >> 1;
-
+template< class _TSuperclass, class _TVertex >
+const unsigned long fpa::Base::
+MinimumSpanningTree< _TSuperclass, _TVertex >::INF_VALUE =
+ std::numeric_limits< unsigned long >::max( );
+
// -------------------------------------------------------------------------
-template< class V, class C, class B >
-void fpa::Base::MinimumSpanningTree< V, C, B >::
+template< class _TSuperclass, class _TVertex >
+void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
SetCollisions( const TCollisions& collisions )
{
+ // Prepare a front graph
this->m_Collisions = collisions;
-
- // Prepare fronts graph using Floyd-Warshall
unsigned long nSeeds = this->m_Collisions.size( );
_TMatrix dist( nSeeds, _TRow( nSeeds, Self::INF_VALUE ) );
this->m_FrontPaths = dist;
-
for( unsigned long i = 0; i < nSeeds; ++i )
{
for( unsigned long j = 0; j < nSeeds; ++j )
this->m_FrontPaths[ i ][ i ] = i;
} // rof
+
+ // Use Floyd-Warshall to compute all possible paths
for( unsigned long k = 0; k < nSeeds; ++k )
{
for( unsigned long i = 0; i < nSeeds; ++i )
}
// -------------------------------------------------------------------------
-template< class V, class C, class B >
-void fpa::Base::MinimumSpanningTree< V, C, B >::
-GetPath( std::vector< V >& path, const V& a, const V& b ) const
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TVertices fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetPath( const TVertex& a ) const
+{
+ TVertices path;
+ if( this->_HasVertex( a ) )
+ this->_Path( path, a );
+ return( path );
+}
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TVertices fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetPath( const TVertex& a, const TVertex& b ) const
{
- typename TDecorated::const_iterator aIt = this->Get( ).find( a );
- typename TDecorated::const_iterator bIt = this->Get( ).find( b );
+ TVertices path;
- if( aIt == this->Get( ).end( ) || bIt == this->Get( ).end( ) )
- return;
+ // Check existence
+ if( !this->_HasVertex( a ) || !this->_HasVertex( b ) )
+ return( path );
- short fa = aIt->second.second;
- short fb = bIt->second.second;
+ // Get front ids
+ short fa = this->_FrontId( a );
+ short fb = this->_FrontId( b );
if( fa == fb )
{
- std::vector< V > ap, bp;
+ // Get paths
+ TVertices ap, bp;
this->_Path( ap, a );
this->_Path( bp, b );
- // Ignore common part
- typename std::vector< V >::const_reverse_iterator raIt, rbIt;
- raIt = ap.rbegin( );
- rbIt = bp.rbegin( );
+ // Ignore common part: find common ancestor
+ auto raIt = ap.rbegin( );
+ auto rbIt = bp.rbegin( );
while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
{
++raIt;
if( rbIt != bp.rbegin( ) ) --rbIt;
// Add part from a
- typename std::vector< V >::const_iterator iaIt = ap.begin( );
- for( ; iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
+ for( auto iaIt = ap.begin( ); iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
path.push_back( *iaIt );
// Add part from b
else
{
// Use this->m_FrontPaths from Floyd-Warshall
- if( this->m_FrontPaths[ fa ][ fb ] != Self::INF_VALUE )
+ if( this->m_FrontPaths[ fa ][ fb ] < Self::INF_VALUE )
{
// Compute front path
std::vector< long > fpath;
// Continue only if both fronts are connected
unsigned int N = fpath.size( );
- if( 0 < N )
+ if( N > 0 )
{
// First path: from start vertex to first collision
- this->GetPath(
- path, a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
+ path = this->GetPath(
+ a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
);
// Intermediary paths
for( unsigned int i = 1; i < N - 1; ++i )
{
- this->GetPath(
- path,
- this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
- this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
- );
+ TVertices ipath =
+ this->GetPath(
+ this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
+ this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
+ );
+ path.insert( path.end( ), ipath.begin( ), ipath.end( ) );
} // rof
// Final path: from last collision to end point
- this->GetPath(
- path,
- this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
- );
+ TVertices lpath =
+ this->GetPath(
+ this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
+ );
+ path.insert( path.end( ), lpath.begin( ), lpath.end( ) );
} // fi
} // fi
} // fi
+ return( path );
}
// -------------------------------------------------------------------------
-template< class V, class C, class B >
-fpa::Base::MinimumSpanningTree< V, C, B >::
-MinimumSpanningTree( )
- : Superclass( )
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TPoints fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetEuclideanPath( const TVertex& a ) const
{
+ TPoints points;
+ return( points );
}
// -------------------------------------------------------------------------
-template< class V, class C, class B >
-fpa::Base::MinimumSpanningTree< V, C, B >::
-~MinimumSpanningTree( )
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TPoints fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetEuclideanPath( const TVertex& a, const TVertex& b ) const
{
+ TPoints points;
+ return( points );
}
// -------------------------------------------------------------------------
-template< class V, class C, class B >
-void fpa::Base::MinimumSpanningTree< V, C, B >::
-_Path( std::vector< V >& path, const V& a ) const
+template< class _TSuperclass, class _TVertex >
+bool fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+IsDefinedInEuclideanSpace( ) const
{
- typename TDecorated::const_iterator dIt = this->Get( ).find( a );
- if( dIt != this->Get( ).end( ) )
- {
- do
- {
- path.push_back( dIt->first );
- dIt = this->Get( ).find( dIt->second.first );
+ return( false );
+}
- } while( dIt->first != dIt->second.first && dIt != this->Get( ).end( ) );
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+SetNode(
+ const TVertex& v, const TVertex& p,
+ const short& fid, const double& cost
+ )
+{
+ typedef typename TNodeQueue::value_type _TNodeQueueValue;
+ if( this->m_FillNodeQueue )
+ this->m_NodeQueue.insert( _TNodeQueueValue( cost, v ) );
+}
- if( dIt != this->Get( ).end( ) )
- path.push_back( dIt->first );
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+Clear( )
+{
+ this->m_NodeQueue.clear( );
+}
- } // fi
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+MinimumSpanningTree( )
+ : Superclass( ),
+ m_FillNodeQueue( false )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+~MinimumSpanningTree( )
+{
}
#endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff