X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FMinimumSpanningTree.hxx;h=c53a071dd2dba934907f5826c88a0afef23ce94e;hb=826a318db2e9b41fbd865e41ebb5906efdefbb02;hp=1140e4022f717616c2aadee581d2898a1488962d;hpb=db33ebb226fd58f493b7db245fc8b807f895ee6e;p=FrontAlgorithms.git

diff --git a/lib/fpa/Base/MinimumSpanningTree.hxx b/lib/fpa/Base/MinimumSpanningTree.hxx
index 1140e40..c53a071 100644
--- a/lib/fpa/Base/MinimumSpanningTree.hxx
+++ b/lib/fpa/Base/MinimumSpanningTree.hxx
@@ -4,22 +4,21 @@
 #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 _TSuperclass, class _TVertex >
+const unsigned long fpa::Base::
+MinimumSpanningTree< _TSuperclass, _TVertex >::INF_VALUE =
+  std::numeric_limits< unsigned long >::max( );
+  
 // -------------------------------------------------------------------------
-template< class V, class C, class B >
-void fpa::Base::MinimumSpanningTree< V, C, B >::
+template< class _TSuperclass, class _TVertex >
+void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
 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 )
@@ -38,6 +37,8 @@ SetCollisions( const TCollisions& collisions )
     this->m_FrontPaths[ i ][ i ] = i;
 
   } // rof
+
+  // Use Floyd-Warshall to compute all possible paths
   for( unsigned long k = 0; k < nSeeds; ++k )
   {
     for( unsigned long i = 0; i < nSeeds; ++i )
@@ -56,28 +57,47 @@ SetCollisions( const TCollisions& collisions )
     } // rof
 
   } // rof
-
   this->Modified( );
 }
 
 // -------------------------------------------------------------------------
-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 _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TVertices fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetPath( const TVertex& a ) const
+{
+  TVertices path;
+  if( this->_HasVertex( a ) )
+    this->_Path( path, a );
+  return( path );
+}
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TVertices fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetPath( const TVertex& a, const TVertex& b ) const
 {
-  long fa = this->_FrontId( a );
-  long fb = this->_FrontId( b );
+  TVertices path;
+
+  // Check existence
+  if( !this->_HasVertex( a ) || !this->_HasVertex( b ) )
+    return( path );
+  
+  // Get front ids
+  short fa = this->_FrontId( a );
+  short fb = this->_FrontId( b );
 
   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;
@@ -88,8 +108,7 @@ GetPath( std::vector< V >& path, const V& a, const V& b ) const
     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
@@ -99,7 +118,7 @@ GetPath( std::vector< V >& path, const V& a, const V& b ) const
   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;
@@ -113,65 +132,103 @@ GetPath( std::vector< V >& path, const V& a, const V& b ) const
 
       // 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( ) );
 
       } // fi
 
     } // fi
 
   } // fi
+  return( path );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class B >
-fpa::Base::MinimumSpanningTree< V, C, B >::
-MinimumSpanningTree( )
-  : Superclass( )
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TPoints fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetEuclideanPath( const TVertex& a ) const
 {
+  TPoints points;
+  return( points );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class B >
-fpa::Base::MinimumSpanningTree< V, C, B >::
-~MinimumSpanningTree( )
+template< class _TSuperclass, class _TVertex >
+typename fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+TPoints fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+GetEuclideanPath( const TVertex& a, const TVertex& b ) const
 {
+  TPoints points;
+  return( points );
 }
 
 // -------------------------------------------------------------------------
-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 _TSuperclass, class _TVertex >
+bool fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+IsDefinedInEuclideanSpace( ) const
 {
-  V it = a;
-  do
-  {
-    path.push_back( it );
-    it = this->_Parent( it );
+  return( false );
+}
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+SetNode(
+  const TVertex& v, const TVertex& p,
+  const short& fid, const double& cost
+  )
+{
+  typedef typename TNodeQueue::value_type _TNodeQueueValue;
+  if( this->m_FillNodeQueue )
+    this->m_NodeQueue.insert( _TNodeQueueValue( cost, v ) );
+}
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+void fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+Clear( )
+{
+  this->m_NodeQueue.clear( );
+}
 
-  } while( it != this->_Parent( it ) );
-  path.push_back( it );
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+MinimumSpanningTree( )
+  : Superclass( ),
+    m_FillNodeQueue( false )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass, class _TVertex >
+fpa::Base::MinimumSpanningTree< _TSuperclass, _TVertex >::
+~MinimumSpanningTree( )
+{
 }
 
 #endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__