X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FMinimumSpanningTree.hxx;h=e8ed6a2c286e94b5701e022531a9e418a105cec1;hb=026b2fe203089e1917ab78ebafb3131f147223f5;hp=2f0a4b1a89a073f22d048be846b4b215783a2eaf;hpb=56b8bb48cc05a297a3faa264f8f2a88de21ef203;p=FrontAlgorithms.git

diff --git a/lib/fpa/Base/MinimumSpanningTree.hxx b/lib/fpa/Base/MinimumSpanningTree.hxx
index 2f0a4b1..e8ed6a2 100644
--- a/lib/fpa/Base/MinimumSpanningTree.hxx
+++ b/lib/fpa/Base/MinimumSpanningTree.hxx
@@ -1,27 +1,38 @@
-#ifndef __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
-#define __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
+#ifndef __fpa__Base__MinimumSpanningTree__hxx__
+#define __fpa__Base__MinimumSpanningTree__hxx__
 
 #include <limits>
 
 // -------------------------------------------------------------------------
-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 _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 _TScalar, class _TVertexCompare >
-void fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
 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 )
       {
@@ -39,17 +50,17 @@ SetCollisions( const TCollisions& collisions )
   } // 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
@@ -69,76 +80,85 @@ SetCollisions( const TCollisions& collisions )
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TVertexCompare >
-typename
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
-TVertices
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
-GetPath( const _TVertex& a ) const
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+ClearSeeds( )
 {
-  TVertices path;
-  if( this->_HasVertex( a ) )
-    this->_Path( path, a );
-  return( path );
+  this->m_Seeds.clear( );
+  this->Modified( );
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TVertexCompare >
-typename
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
-TVertices
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
-GetPath( const _TVertex& a, const _TVertex& b ) const
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+AddSeed( const _TVertex& seed )
 {
-  TVertices path;
+  this->m_Seeds.push_back( seed );
+  this->Modified( );
+}
 
-  // 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;
+// -------------------------------------------------------------------------
+template< class _TVertex, class _TPath, class _TSuperclass >
+void fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
+GetPath( typename _TPath::Pointer& path, const _TVertex& a ) const
+{
+  std::vector< _TVertex > 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 );
+
+  if( path.IsNull( ) )
+    path = _TPath::New( );
+  for( auto v = vertices.begin( ); v != vertices.end( ); ++v )
+    path->AddVertex( *v );
+}
 
-  if( fa == fb )
+// -------------------------------------------------------------------------
+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( );
+
+  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 )
   {
-    // 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->GetVertex( pa->GetSize( ) - 1 ) )
+        ia = i;
+      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 )
     {
       // 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
 
@@ -147,132 +167,78 @@ GetPath( const _TVertex& a, const _TVertex& b ) const
       if( N > 0 )
       {
         // First path: from start vertex to first collision
-        path = this->GetPath(
-          a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
+        this->GetPath(
+          path, a,
+          this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
           );
 
         // 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( ) );
+          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 ) );
 
         } // 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( ) );
-
-        // 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
+        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
+      long aIt = pa->GetSize( ) - 1;
+      long bIt = pb->GetSize( ) - 1;
+      bool cont = true;
+      while( aIt >= 0 && bIt >= 0 && cont )
+      {
+        cont = ( pa->GetVertex( aIt ) == pb->GetVertex( bIt ) );
+        aIt--;
+        bIt--;
 
-    } // fi
+      } // elihw
+      aIt++;
+      bIt++;
 
-  } // fi
-  return( path );
-}
+      // Glue both parts
+      for( long cIt = 0; cIt <= aIt; ++cIt )
+        path->AddVertex( pa->GetVertex( cIt ) );
+      for( ; bIt >= 0; --bIt )
+        path->AddVertex( pb->GetVertex( 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
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TVertexCompare >
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
 MinimumSpanningTree( )
-  : Superclass( ),
-    m_FillNodeQueue( false )
+  : Superclass( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TVertexCompare >
-fpa::Base::MinimumSpanningTree< _TVertex, _TScalar, _TVertexCompare >::
+template< class _TVertex, class _TPath, class _TSuperclass >
+fpa::Base::MinimumSpanningTree< _TVertex, _TPath, _TSuperclass >::
 ~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$