#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 _TVertex, class _TScalar, class _TVertexCompare >
+const unsigned long fpa::Base::
+MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::INF_VALUE =
+ std::numeric_limits< unsigned long >::max( );
// -------------------------------------------------------------------------
-template< class V, class C, class B >
-void fpa::Base::MinimumSpanningTree< V, C, B >::
+template< class _TVertex, class _TScalar, class _TVertexCompare >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
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 between fronts
for( unsigned long k = 0; k < nSeeds; ++k )
{
for( unsigned long i = 0; i < nSeeds; ++i )
{
for( unsigned long j = 0; j < nSeeds; ++j )
{
- if( ( dist[ i ][ k ] + dist[ k ][ j ] ) < dist[ i ][ j ] )
+ // WARNING: you don't want a numeric overflow!!!
+ unsigned long dik = dist[ i ][ k ];
+ unsigned long dkj = dist[ k ][ j ];
+ unsigned long sum = Self::INF_VALUE;
+ if( dik < Self::INF_VALUE && dkj < Self::INF_VALUE )
+ sum = dik + dkj;
+
+ // Ok, continue Floyd-Warshall
+ if( sum < dist[ i ][ j ] )
{
- dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ];
+ dist[ i ][ j ] = sum;
this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
} // fi
}
// -------------------------------------------------------------------------
-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 _TVertex, class _TScalar, class _TVertexCompare >
+typename
+fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+TVertices
+fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+GetPath( const _TVertex& a ) const
{
- typename TDecorated::const_iterator aIt = this->Get( ).find( a );
- typename TDecorated::const_iterator bIt = this->Get( ).find( b );
+ TVertices path;
+ if( this->_HasVertex( a ) )
+ this->_Path( path, a );
+ return( path );
+}
- if( aIt == this->Get( ).end( ) || bIt == this->Get( ).end( ) )
- return;
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TScalar, class _TVertexCompare >
+typename
+fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+TVertices
+fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+GetPath( const _TVertex& a, const _TVertex& b ) const
+{
+ TVertices path;
+
+ // Check existence
+ if( !this->_HasVertex( a ) || !this->_HasVertex( b ) )
+ return( path );
- short fa = aIt->second.second;
- short fb = bIt->second.second;
+ // Get front ids
+ long fa = this->_FrontId( a ) - 1;
+ long fb = this->_FrontId( b ) - 1;
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;
} // elihw
if( raIt != ap.rbegin( ) ) --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( ) );
+
+ // Remove repeated vertices
+ auto p = path.begin( );
+ auto q = p;
+ q++;
+ while( q != path.end( ) )
+ {
+ if( *q == *p )
+ {
+ p = path.erase( p );
+ q = p;
+ }
+ else
+ ++p;
+ ++q;
+
+ } // elihw
} // fi
} // fi
} // fi
+ return( path );
}
// -------------------------------------------------------------------------
-template< class V, class C, class B >
-fpa::Base::MinimumSpanningTree< V, C, B >::
+template< class _TVertex, class _TScalar, class _TVertexCompare >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+SetNode(
+ const _TVertex& vertex, const _TVertex& parent,
+ const long& fid, const _TScalar& result
+ )
+{
+ this->Get( )[ vertex ] = TParent( parent, TData( result, fid ) );
+ this->Modified( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TScalar, class _TVertexCompare >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+Clear( )
+{
+ this->Get( ).clear( );
+ this->m_NodeQueue.clear( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TScalar, class _TVertexCompare >
+fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
MinimumSpanningTree( )
- : Superclass( )
+ : Superclass( ),
+ m_FillNodeQueue( false )
{
}
// -------------------------------------------------------------------------
-template< class V, class C, class B >
-fpa::Base::MinimumSpanningTree< V, C, B >::
+template< class _TVertex, class _TScalar, class _TVertexCompare >
+fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
~MinimumSpanningTree( )
{
}
// -------------------------------------------------------------------------
-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 _TVertex, class _TScalar, class _TVertexCompare >
+bool fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+_HasVertex( const _TVertex& a ) const
+{
+ return( this->Get( ).find( a ) != this->Get( ).end( ) );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TScalar, class _TVertexCompare >
+long fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+_FrontId( const _TVertex& a ) const
+{
+ static const long MAX_ID = std::numeric_limits< long >::max( );
+ auto i = this->Get( ).find( a );
+ if( i != this->Get( ).end( ) )
+ return( i->second.second.second );
+ else
+ return( MAX_ID );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TScalar, class _TVertexCompare >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+_Path( TVertices& path, const _TVertex& a ) const
{
- typename TDecorated::const_iterator dIt = this->Get( ).find( a );
- if( dIt != this->Get( ).end( ) )
+ auto& m = this->Get( );
+ auto it = m.find( a );
+ if( it != m.end( ) )
{
do
{
- path.push_back( dIt->first );
- dIt = this->Get( ).find( dIt->second.first );
-
- } while( dIt->first != dIt->second.first && dIt != this->Get( ).end( ) );
+ path.push_back( it->first );
+ it = m.find( it->second.first );
- if( dIt != this->Get( ).end( ) )
- path.push_back( dIt->first );
+ } while( it->first != it->second.first );
+ path.push_back( it->first );
} // fi
}
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff