...

[FrontAlgorithms.git] / libs / fpa / Base / MinimumSpanningTree.hxx

diff --git a/libs/fpa/Base/MinimumSpanningTree.hxx b/libs/fpa/Base/MinimumSpanningTree.hxx
index e8ed6a2c286e94b5701e022531a9e418a105cec1..c5838f319be7784e4d949796aee058ac1d442a75 100644 (file)
--- a/libs/fpa/Base/MinimumSpanningTree.hxx
+++ b/libs/fpa/Base/MinimumSpanningTree.hxx
@@ -1,22 +1,23 @@
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
+
 #ifndef __fpa__Base__MinimumSpanningTree__hxx__
 #define __fpa__Base__MinimumSpanningTree__hxx__
 
-#include <limits>
-
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TPath, class _TSuperclass >
-const typename
-fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
-TCollisions&
-fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+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 _TPath, class _TSuperclass >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+template< class _TVertex, class _Superclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
 SetCollisions( const TCollisions& collisions )
 {
   static const unsigned long _inf =
@@ -80,8 +81,8 @@ SetCollisions( const TCollisions& collisions )
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TPath, class _TSuperclass >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+template< class _TVertex, class _Superclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
 ClearSeeds( )
 {
   this->m_Seeds.clear( );
@@ -89,8 +90,8 @@ ClearSeeds( )
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TPath, class _TSuperclass >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+template< class _TVertex, class _Superclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
 AddSeed( const _TVertex& seed )
 {
   this->m_Seeds.push_back( seed );
@@ -98,11 +99,12 @@ AddSeed( const _TVertex& seed )
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TPath, class _TSuperclass >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
-GetPath( typename _TPath::Pointer& path, const _TVertex& a ) const
+template< class _TVertex, class _Superclass >
+typename fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+TVertices fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
+GetPath( const _TVertex& a ) const
 {
-  std::vector< _TVertex > vertices;
+  TVertices vertices;
   _TVertex it = a;
   _TVertex p = this->GetParent( it );
   while( it != p )
@@ -113,38 +115,31 @@ GetPath( typename _TPath::Pointer& path, const _TVertex& a ) const
 
   } // elihw
   vertices.push_back( it );
-
-  if( path.IsNull( ) )
-    path = _TPath::New( );
-  for( auto v = vertices.begin( ); v != vertices.end( ); ++v )
-    path->AddVertex( *v );
+  return( vertices );
 }
 
 // -------------------------------------------------------------------------
-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
+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( );
 
-  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 )
+  TVertices vertices;
+  TVertices pa = this->GetPath( a );
+  TVertices pb = this->GetPath( b );
+  if( pa.size( ) > 0 && pb.size( ) > 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->GetVertex( pa->GetSize( ) - 1 ) )
+      if( this->m_Seeds[ i ] == pa[ pa.size( ) - 1 ] )
         ia = i;
-      if( this->m_Seeds[ i ] == pb->GetVertex( pb->GetSize( ) - 1 ) )
+      if( this->m_Seeds[ i ] == pb[ pb.size( ) - 1 ] )
         ib = i;
 
     } // rof
@@ -167,45 +162,42 @@ GetPath(
       if( N > 0 )
       {
         // First path: from start vertex to first collision
-        this->GetPath(
-          path, a,
-          this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
+        vertices = this->GetPath(
+          a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
           );
 
         // Intermediary paths
         for( unsigned int i = 1; i < N - 1; ++i )
         {
-          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 ) );
+          TVertices ipath =
+            this->GetPath(
+              this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
+              this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
+              );
+          for( long id = 0; id < ipath.size( ); ++id )
+            vertices.push_back( ipath[ id ] );
 
         } // rof
 
         // 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 ) );
+        TVertices lpath =
+          this->GetPath(
+            this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
+            );
+        for( long id = 0; id < lpath.size( ); ++id )
+          vertices.push_back( lpath[ id ] );
 
       } // fi
     }
     else
     {
       // Ignore common part: find common ancestor
-      long aIt = pa->GetSize( ) - 1;
-      long bIt = pb->GetSize( ) - 1;
+      long aIt = pa.size( ) - 1;
+      long bIt = pb.size( ) - 1;
       bool cont = true;
       while( aIt >= 0 && bIt >= 0 && cont )
       {
-        cont = ( pa->GetVertex( aIt ) == pb->GetVertex( bIt ) );
+        cont = ( pa[ aIt ] == pb[ bIt ] );
         aIt--;
         bIt--;
 
@@ -215,26 +207,27 @@ GetPath(
 
       // Glue both parts
       for( long cIt = 0; cIt <= aIt; ++cIt )
-        path->AddVertex( pa->GetVertex( cIt ) );
+        vertices.push_back( pa[ cIt ] );
       for( ; bIt >= 0; --bIt )
-        path->AddVertex( pb->GetVertex( bIt ) );
+        vertices.push_back( pb[ bIt ] );
 
     } // fi
 
   } // fi
+  return( vertices );
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TPath, class _TSuperclass >
-fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+template< class _TVertex, class _Superclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
 MinimumSpanningTree( )
   : Superclass( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TPath, class _TSuperclass >
-fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+template< class _TVertex, class _Superclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _Superclass >::
 ~MinimumSpanningTree( )
 {
 }