-#ifndef __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
-#define __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
-#include <limits>
+#ifndef __fpa__Base__MinimumSpanningTree__hxx__
+#define __fpa__Base__MinimumSpanningTree__hxx__
// -------------------------------------------------------------------------
-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 _TVertex, class _Superclass >
+const typename fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+TCollisions& fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+GetCollisions( ) const
+{
+ return( this->m_Collisions );
+}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TVertexCompare >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+template< class _TVertex, class _Superclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
SetCollisions( const TCollisions& collisions )
{
- // Prepare a front graph
+ static const unsigned long _inf =
+ std::numeric_limits< unsigned long >::max( );
+ if( this->m_Collisions == collisions )
+ return;
+
this->m_Collisions = collisions;
- unsigned long nSeeds = this->m_Collisions.size( );
- _TMatrix dist( nSeeds, _TRow( nSeeds, Self::INF_VALUE ) );
+
+ // 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 < nSeeds; ++i )
+ for( unsigned long i = 0; i < N; ++i )
{
- for( unsigned long j = 0; j < nSeeds; ++j )
+ for( unsigned long j = 0; j < N; ++j )
{
if( this->m_Collisions[ i ][ j ].second )
{
} // rof
// Use Floyd-Warshall to compute all possible paths between fronts
- for( unsigned long k = 0; k < nSeeds; ++k )
+ for( unsigned long k = 0; k < N; ++k )
{
- for( unsigned long i = 0; i < nSeeds; ++i )
+ for( unsigned long i = 0; i < N; ++i )
{
- for( unsigned long j = 0; j < nSeeds; ++j )
+ 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 = Self::INF_VALUE;
- if( dik < Self::INF_VALUE && dkj < Self::INF_VALUE )
+ unsigned long sum = _inf;
+ if( dik < _inf && dkj < _inf )
sum = dik + dkj;
// Ok, continue Floyd-Warshall
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TVertexCompare >
-typename
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
-TVertices
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+template< class _TVertex, class _Superclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+ClearSeeds( )
+{
+ this->m_Seeds.clear( );
+ this->Modified( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+AddSeed( const _TVertex& seed )
+{
+ this->m_Seeds.push_back( seed );
+ this->Modified( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+typename fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+TVertices fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
GetPath( const _TVertex& a ) const
{
- TVertices path;
- if( this->_HasVertex( a ) )
- this->_Path( path, a );
- return( path );
+ 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 _TScalar, class _TVertexCompare >
-typename
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
-TVertices
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+template< class _TVertex, class _Superclass >
+typename fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+TVertices fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
GetPath( const _TVertex& a, const _TVertex& b ) const
{
- TVertices path;
+ static const unsigned long _inf =
+ std::numeric_limits< unsigned long >::max( );
- // Check existence
- if( !this->_HasVertex( a ) || !this->_HasVertex( b ) )
- return( path );
-
- // Get front ids
- long fa = this->_FrontId( a ) - 1;
- long fb = this->_FrontId( b ) - 1;
-
- if( fa == fb )
+ TVertices vertices;
+ TVertices pa = this->GetPath( a );
+ TVertices pb = this->GetPath( b );
+ if( pa.size( ) > 0 && pb.size( ) > 0 )
{
- // Get paths
- TVertices ap, bp;
- this->_Path( ap, a );
- this->_Path( bp, b );
-
- // Ignore common part: find common ancestor
- auto raIt = ap.rbegin( );
- auto rbIt = bp.rbegin( );
- while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
+ // Find front identifiers
+ unsigned long ia = _inf, ib = _inf;
+ unsigned long N = this->m_Seeds.size( );
+ for( unsigned long i = 0; i < N; ++i )
{
- ++raIt;
- ++rbIt;
-
- } // elihw
- if( raIt != ap.rbegin( ) ) --raIt;
- if( rbIt != bp.rbegin( ) ) --rbIt;
-
- // Add part from a
- for( auto iaIt = ap.begin( ); iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
- path.push_back( *iaIt );
-
- // Add part from b
- for( ; rbIt != bp.rend( ); ++rbIt )
- path.push_back( *rbIt );
- }
- else
- {
- // Use this->m_FrontPaths from Floyd-Warshall
- if( this->m_FrontPaths[ fa ][ fb ] < Self::INF_VALUE )
+ 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( fa );
- while( fa != fb )
+ fpath.push_back( ia );
+ while( ia != ib )
{
- fa = this->m_FrontPaths[ fa ][ fb ];
- fpath.push_back( fa );
+ ia = this->m_FrontPaths[ ia ][ ib ];
+ fpath.push_back( ia );
} // elihw
if( N > 0 )
{
// First path: from start vertex to first collision
- path = this->GetPath(
- a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
+ vertices = this->GetPath(
+ a, this->m_Collisions[ fpath[ 1 ] ][ fpath[ 0 ] ].first
);
// Intermediary paths
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( ) );
+ 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->GetPath(
- this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
+ this->m_Collisions[ fpath[ N - 2 ] ][ fpath[ N - 1 ] ].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
+ 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--;
- } // fi
+ } // elihw
+ aIt++;
+ bIt++;
- } // fi
- return( path );
-}
+ // Glue both parts
+ for( long cIt = 0; cIt <= aIt; ++cIt )
+ vertices.push_back( pa[ cIt ] );
+ for( ; bIt >= 0; --bIt )
+ vertices.push_back( pb[ bIt ] );
-// -------------------------------------------------------------------------
-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( );
-}
+ } // fi
-// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TVertexCompare >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
-Clear( )
-{
- this->Get( ).clear( );
- this->m_NodeQueue.clear( );
+ } // fi
+ return( vertices );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TVertexCompare >
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+template< class _TVertex, class _Superclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
MinimumSpanningTree( )
- : Superclass( ),
- m_FillNodeQueue( false )
+ : Superclass( )
{
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TVertexCompare >
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+template< class _TVertex, class _Superclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
~MinimumSpanningTree( )
{
}
-// -------------------------------------------------------------------------
-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
-{
- auto& m = this->Get( );
- auto it = m.find( a );
- if( it != m.end( ) )
- {
- do
- {
- path.push_back( it->first );
- it = m.find( it->second.first );
-
- } while( it->first != it->second.first );
- path.push_back( it->first );
-
- } // fi
-}
-
-#endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
+#endif // __fpa__Base__MinimumSpanningTree__hxx__
// eof - $RCSfile$