X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FDataStructures%2FMinimumSpanningTree.hxx;fp=lib%2Ffpa%2FDataStructures%2FMinimumSpanningTree.hxx;h=5eecf290918cb143354f003ad85b999f85408d4f;hb=2047276c8f1a02432fbcc7014722d460d6c1e60f;hp=0000000000000000000000000000000000000000;hpb=3c639e5da479c7216a0a302ffa156ac6762caeed;p=FrontAlgorithms.git

diff --git a/lib/fpa/DataStructures/MinimumSpanningTree.hxx b/lib/fpa/DataStructures/MinimumSpanningTree.hxx
new file mode 100644
index 0000000..5eecf29
--- /dev/null
+++ b/lib/fpa/DataStructures/MinimumSpanningTree.hxx
@@ -0,0 +1,235 @@
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
+#ifndef __fpa__DataStructures__MinimumSpanningTree__hxx__
+#define __fpa__DataStructures__MinimumSpanningTree__hxx__
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+const typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+TCollisions& fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+GetCollisions( ) const
+{
+  return( this->m_Collisions );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+void fpa::DataStructures::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 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 < N; ++i )
+  {
+    for( unsigned long j = 0; j < N; ++j )
+    {
+      if( this->m_Collisions[ i ][ j ].second )
+      {
+        dist[ i ][ j ] = 1;
+        dist[ j ][ i ] = 1;
+        this->m_FrontPaths[ i ][ j ] = j;
+        this->m_FrontPaths[ j ][ i ] = i;
+
+      } // fi
+
+    } // rof
+    dist[ i ][ i ] = 0;
+    this->m_FrontPaths[ i ][ i ] = i;
+
+  } // rof
+
+  // Use Floyd-Warshall to compute all possible paths between fronts
+  for( unsigned long k = 0; k < N; ++k )
+  {
+    for( unsigned long i = 0; i < N; ++i )
+    {
+      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 = _inf;
+        if( dik < _inf && dkj < _inf )
+          sum = dik + dkj;
+
+        // Ok, continue Floyd-Warshall
+        if( sum < dist[ i ][ j ] )
+        {
+          dist[ i ][ j ] = sum;
+          this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];
+
+        } // fi
+
+      } // rof
+
+    } // rof
+
+  } // rof
+  this->Modified( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+ClearSeeds( )
+{
+  this->m_Seeds.clear( );
+  this->Modified( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+void fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+AddSeed( const _TVertex& seed )
+{
+  this->m_Seeds.push_back( seed );
+  this->Modified( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+TVertices fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+GetPath( const _TVertex& a ) const
+{
+  TVertices 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 );
+  return( vertices );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+typename fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+TVertices fpa::DataStructures::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 )
+  {
+    // 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( ia );
+      while( ia != ib )
+      {
+        ia = this->m_FrontPaths[ ia ][ ib ];
+        fpath.push_back( ia );
+
+      } // elihw
+
+      // Continue only if both fronts are connected
+      unsigned int N = fpath.size( );
+      if( N > 0 )
+      {
+        // First path: from start vertex to first collision
+        vertices = this->GetPath(
+          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 - 1 ] ][ fpath[ i ] ].first,
+              this->m_Collisions[ fpath[ i + 1 ] ][ fpath[ i ] ].first
+              );
+          for( long id = 0; id < ipath.size( ); ++id )
+            vertices.push_back( ipath[ 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
+            );
+        for( long id = 0; id < lpath.size( ); ++id )
+          vertices.push_back( lpath[ id ] );
+
+      } // fi
+    }
+    else
+    {
+      // 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 )
+      {
+        cont = ( pa[ aIt ] == pb[ bIt ] );
+        aIt--;
+        bIt--;
+
+      } // elihw
+      aIt++;
+      bIt++;
+
+      // Glue both parts
+      for( long cIt = 0; cIt <= aIt; ++cIt )
+        vertices.push_back( pa[ cIt ] );
+      for( ; bIt >= 0; --bIt )
+        vertices.push_back( pb[ bIt ] );
+
+    } // fi
+
+  } // fi
+  return( vertices );
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+MinimumSpanningTree( )
+  : Superclass( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class _TVertex, class _Superclass >
+fpa::DataStructures::MinimumSpanningTree< _TVertex, _Superclass >::
+~MinimumSpanningTree( )
+{
+}
+
+#endif // __fpa__DataStructures__MinimumSpanningTree__hxx__
+// eof - $RCSfile$