X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FMinimumSpanningTree.hxx;h=6004aaa183efea0514cc2839fea585a009fadfa6;hb=ed2108383e59a45c6fa2e9259a27256a93d8aa6a;hp=9d0939ddf74b2e469c4416c103f1f6445ee96214;hpb=855f9954a822d2739efac96c38356d0aa788c982;p=FrontAlgorithms.git

diff --git a/lib/fpa/Base/MinimumSpanningTree.hxx b/lib/fpa/Base/MinimumSpanningTree.hxx
index 9d0939d..6004aaa 100644
--- a/lib/fpa/Base/MinimumSpanningTree.hxx
+++ b/lib/fpa/Base/MinimumSpanningTree.hxx
@@ -1,28 +1,39 @@
-#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 V, class B >
-const unsigned long fpa::Base::MinimumSpanningTree< V, B >::INF_VALUE =
-  std::numeric_limits< unsigned long >::max( ) >> 1;
+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 V, class B >
-void fpa::Base::MinimumSpanningTree< V, B >::
+template< class _TVertex, class _Superclass >
+void fpa::Base::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 fronts graph using Floyd-Warshall
-  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 )
       {
@@ -38,15 +49,25 @@ SetCollisions( const TCollisions& collisions )
     this->m_FrontPaths[ i ][ i ] = i;
 
   } // rof
-  for( unsigned long k = 0; k < nSeeds; ++k )
+
+  // Use Floyd-Warshall to compute all possible paths between fronts
+  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 )
       {
-        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 = _inf;
+        if( dik < _inf && dkj < _inf )
+          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
@@ -60,190 +81,157 @@ SetCollisions( const TCollisions& collisions )
 }
 
 // -------------------------------------------------------------------------
-template< class V, class B >
-std::vector< V > fpa::Base::MinimumSpanningTree< V, B >::
-GetPath( const V& a, const V& b ) const
+template< class _TVertex, class _Superclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+ClearSeeds( )
 {
-  std::vector< V > path;
-  typename TDecorated::const_iterator aIt = this->Get( ).find( a );
-  typename TDecorated::const_iterator bIt = this->Get( ).find( b );
+  this->m_Seeds.clear( );
+  this->Modified( );
+}
 
-  if( aIt == this->Get( ).end( ) || bIt == this->Get( ).end( ) )
-    return( path );
-  
-  short fa = aIt->second.second;
-  short fb = bIt->second.second;
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+AddSeed( const _TVertex& seed )
+{
+  this->m_Seeds.push_back( seed );
+  this->Modified( );
+}
 
-  if( fa == fb )
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+typename fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+TVertices fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+GetPath( const _TVertex& a ) const
+{
+  TVertices vertices;
+  _TVertex it = a;
+  _TVertex p = this->GetParent( it );
+  while( it != p )
   {
-    std::vector< V > 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( );
-    while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
-    {
-      ++raIt;
-      ++rbIt;
-
-    } // 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 )
-      path.push_back( *iaIt );
-
-    // Add part from b
-    for( ; rbIt != bp.rend( ); ++rbIt )
-      path.push_back( *rbIt );
-  }
-  else
+    vertices.push_back( it );
+    it = p;
+    p = this->GetParent( it );
+
+  } // elihw
+  vertices.push_back( it );
+  return( vertices );
+}
+
+// -------------------------------------------------------------------------
+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
+{
+  static const unsigned long _inf =
+    std::numeric_limits< unsigned long >::max( );
+
+  TVertices vertices;
+  TVertices pa = this->GetPath( a );
+  TVertices pb = this->GetPath( b );
+  if( pa.size( ) > 0 && pb.size( ) > 0 )
   {
-    // Use this->m_FrontPaths from Floyd-Warshall
-    if( this->m_FrontPaths[ fa ][ fb ] != Self::INF_VALUE )
+    // 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( 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
 
       // 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
-        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
         for( unsigned int i = 1; i < N - 1; ++i )
         {
-          std::vector< V > ipath =
+          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( ) );
+          for( long id = 0; id < ipath.size( ); ++id )
+            vertices.push_back( ipath[ id ] );
 
         } // rof
 
         // Final path: from last collision to end point
-        std::vector< V > lpath =
+        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( ) );
+        for( long id = 0; id < lpath.size( ); ++id )
+          vertices.push_back( lpath[ id ] );
 
       } // fi
-
-    } // fi
-
-  } // fi
-  return( path );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class B >
-template< class I >
-std::vector< typename I::PointType > fpa::Base::MinimumSpanningTree< V, B >::
-GetPathFromImage(
-  const V& a, const V& b,
-  const I* image, unsigned int kernel
-  ) const
-{
-  typedef typename I::PointType _P;
-
-  std::vector< _P > path;
-  std::vector< V > vertices = this->GetPath( a, b );
-  for( unsigned int i = 0; i < vertices.size( ); ++i )
-  {
-    _P p;
-    image->TransformIndexToPhysicalPoint( vertices[ i ], p );
-    path.push_back( p );
-
-  } // rof
-
-  // Lowpass filter
-  if( kernel > 0 )
-  {
-    int k = int( kernel ) >> 1;
-    std::vector< _P > lowpass_path;
-    for( unsigned int i = 0; i < path.size( ); ++i )
+    }
+    else
     {
-      _P p;
-      p.Fill( ( typename _P::ValueType )( 0 ) );
-      unsigned int c = 0;
-      for( int j = -k; j <= k; ++j )
+      // 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 )
       {
-        int l = int( i ) + j;
-        if( l >= 0 && l < path.size( ) )
-        {
-          p += path[ l ].GetVectorFromOrigin( );
-          c++;
+        cont = ( pa[ aIt ] == pb[ bIt ] );
+        aIt--;
+        bIt--;
 
-        } // fi
-
-      } // rof
-      if( c > 0 )
-        for( unsigned int d = 0; d < _P::PointDimension; ++d )
-          p[ d ] /= ( typename _P::ValueType )( c );
-      lowpass_path.push_back( p );
+      } // elihw
+      aIt++;
+      bIt++;
 
-    } // rof
+      // Glue both parts
+      for( long cIt = 0; cIt <= aIt; ++cIt )
+        vertices.push_back( pa[ cIt ] );
+      for( ; bIt >= 0; --bIt )
+        vertices.push_back( pb[ bIt ] );
 
-    path = lowpass_path;
+    } // fi
 
   } // fi
-  return( path );
+  return( vertices );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class B >
-fpa::Base::MinimumSpanningTree< V, B >::
+template< class _TVertex, class _Superclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
 MinimumSpanningTree( )
   : Superclass( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class V, class B >
-fpa::Base::MinimumSpanningTree< V, B >::
+template< class _TVertex, class _Superclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
 ~MinimumSpanningTree( )
 {
 }
 
-// -------------------------------------------------------------------------
-template< class V, class B >
-void fpa::Base::MinimumSpanningTree< V, B >::
-_Path( std::vector< V >& path, const V& a ) 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 );
-
-    } while( dIt->first != dIt->second.first && dIt != this->Get( ).end( ) );
-
-    if( dIt != this->Get( ).end( ) )
-      path.push_back( dIt->first );
-
-  } // fi
-}
-
-#endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
+#endif // __fpa__Base__MinimumSpanningTree__hxx__
 
 // eof - $RCSfile$