X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;ds=inline;f=lib%2Ffpa%2FBase%2FMinimumSpanningTree.hxx;h=e8ed6a2c286e94b5701e022531a9e418a105cec1;hb=86a6d5df2aa1aa5292a5fa851d98bfc13939bdf3;hp=8746005f8a776b11f8021a65a55d86341b65eea1;hpb=ea46079b5aef76c1782648ed23e70ea944649635;p=FrontAlgorithms.git

diff --git a/lib/fpa/Base/MinimumSpanningTree.hxx b/lib/fpa/Base/MinimumSpanningTree.hxx
index 8746005..e8ed6a2 100644
--- a/lib/fpa/Base/MinimumSpanningTree.hxx
+++ b/lib/fpa/Base/MinimumSpanningTree.hxx
@@ -4,17 +4,19 @@
 #include <limits>
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-const typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
-TCollisions& fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+const typename
+fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+TCollisions&
+fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
 GetCollisions( ) const
 {
   return( this->m_Collisions );
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
 SetCollisions( const TCollisions& collisions )
 {
   static const unsigned long _inf =
@@ -78,8 +80,8 @@ SetCollisions( const TCollisions& collisions )
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
 ClearSeeds( )
 {
   this->m_Seeds.clear( );
@@ -87,8 +89,8 @@ ClearSeeds( )
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
 AddSeed( const _TVertex& seed )
 {
   this->m_Seeds.push_back( seed );
@@ -96,133 +98,143 @@ AddSeed( const _TVertex& seed )
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
-TVertices fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
-GetPath( const _TVertex& a ) const
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+GetPath( typename _TPath::Pointer& path, const _TVertex& a ) const
 {
-  TVertices path;
+  std::vector< _TVertex > vertices;
   _TVertex it = a;
   _TVertex p = this->GetParent( it );
   while( it != p )
   {
-    path.push_front( it );
+    vertices.push_back( it );
     it = p;
     p = this->GetParent( it );
 
   } // elihw
-  path.push_front( it );
-  return( path );
+  vertices.push_back( it );
+
+  if( path.IsNull( ) )
+    path = _TPath::New( );
+  for( auto v = vertices.begin( ); v != vertices.end( ); ++v )
+    path->AddVertex( *v );
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
-TVertices fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
-GetPath( const _TVertex& a, const _TVertex& b ) const
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+GetPath(
+  typename _TPath::Pointer& path, const _TVertex& a, const _TVertex& b
+  ) const
 {
   static const unsigned long _inf =
     std::numeric_limits< unsigned long >::max( );
 
-  TVertices path;
-  TVertices pa = this->GetPath( a );
-  TVertices pb = this->GetPath( b );
-  if( pa.size( ) > 0 && pb.size( ) > 0 )
+  if( path.IsNull( ) )
+    path = _TPath::New( );
+  typename _TPath::Pointer pa, pb;
+  this->GetPath( pa, a );
+  this->GetPath( pb, b );
+  if( pa->GetSize( ) > 0 && pb->GetSize( ) > 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.front( ) )
+      if( this->m_Seeds[ i ] == pa->GetVertex( pa->GetSize( ) - 1 ) )
         ia = i;
-      if( this->m_Seeds[ i ] == pb.front( ) )
+      if( this->m_Seeds[ i ] == pb->GetVertex( pb->GetSize( ) - 1 ) )
         ib = i;
 
     } // rof
 
+    // Check if there is a front-jump between given seeds
     if( ia != ib )
     {
-      // Use this->m_FrontPaths from Floyd-Warshall
-      if( this->m_FrontPaths[ ia ][ ib ] < _inf )
+      // Compute front path
+      std::vector< long > fpath;
+      fpath.push_back( ia );
+      while( ia != ib )
       {
-        // Compute front path
-        std::vector< long > fpath;
+        ia = this->m_FrontPaths[ ia ][ ib ];
         fpath.push_back( ia );
-        while( ia != ib )
-        {
-          ia = this->m_FrontPaths[ ia ][ ib ];
-          fpath.push_back( ia );
 
-        } // elihw
+      } // elihw
 
-        // Continue only if both fronts are connected
-        unsigned int N = fpath.size( );
-        if( N > 0 )
+      // Continue only if both fronts are connected
+      unsigned int N = fpath.size( );
+      if( N > 0 )
+      {
+        // First path: from start vertex to first collision
+        this->GetPath(
+          path, a,
+          this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
+          );
+
+        // Intermediary paths
+        for( unsigned int i = 1; i < N - 1; ++i )
         {
-          // First path: from start vertex to first collision
-          path = this->GetPath(
-            a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
+          typename _TPath::Pointer ipath;
+          this->GetPath(
+            ipath,
+            this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
+            this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
             );
+          for( long id = 0; id < ipath->GetSize( ); ++id )
+            path->AddVertex( ipath->GetVertex( id ) );
 
-          // Intermediary paths
-          for( unsigned int i = 1; i < N - 1; ++i )
-          {
-            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
-          TVertices lpath =
-            this->GetPath(
-              this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
-              );
-          path.insert( path.end( ), lpath.begin( ), lpath.end( ) );
+        } // rof
 
-        } // fi
+        // Final path: from last collision to end point
+        typename _TPath::Pointer lpath;
+        this->GetPath(
+          lpath,
+          this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
+          );
+        for( long id = 0; id < lpath->GetSize( ); ++id )
+          path->AddVertex( lpath->GetVertex( id ) );
 
       } // fi
     }
     else
     {
       // Ignore common part: find common ancestor
-      auto aIt = pa.begin( );
-      auto bIt = pb.begin( );
-      while( *aIt == *bIt && aIt != pa.end( ) && bIt != pb.end( ) )
+      long aIt = pa->GetSize( ) - 1;
+      long bIt = pb->GetSize( ) - 1;
+      bool cont = true;
+      while( aIt >= 0 && bIt >= 0 && cont )
       {
-        ++aIt;
-        ++bIt;
+        cont = ( pa->GetVertex( aIt ) == pb->GetVertex( bIt ) );
+        aIt--;
+        bIt--;
 
       } // elihw
+      aIt++;
+      bIt++;
 
       // Glue both parts
-      for( --aIt; aIt != pa.end( ); ++aIt )
-        path.push_front( *aIt );
-      for( ; bIt != pb.end( ); ++bIt )
-        path.push_back( *bIt );
+      for( long cIt = 0; cIt <= aIt; ++cIt )
+        path->AddVertex( pa->GetVertex( cIt ) );
+      for( ; bIt >= 0; --bIt )
+        path->AddVertex( pb->GetVertex( bIt ) );
 
     } // fi
 
   } // fi
-  return( path );
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
 MinimumSpanningTree( )
   : Superclass( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TSuperclass >
-fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
 ~MinimumSpanningTree( )
 {
 }