X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FAlgorithm.hxx;h=dbcdc608614faeb297e0a8403cf02c97dc1d015c;hb=8cf92baeeefc45bc80a2d0eb2850e04b6089111f;hp=f4ccfdb5c95ae0bdce26cac35df7869783fa7ef8;hpb=9f7b6541d030299dff60fb93caa4371f8f9825de;p=FrontAlgorithms.git

diff --git a/lib/fpa/Base/Algorithm.hxx b/lib/fpa/Base/Algorithm.hxx
index f4ccfdb..dbcdc60 100644
--- a/lib/fpa/Base/Algorithm.hxx
+++ b/lib/fpa/Base/Algorithm.hxx
@@ -1,13 +1,65 @@
 #ifndef __FPA__BASE__ALGORITHM__HXX__
 #define __FPA__BASE__ALGORITHM__HXX__
 
-#include <algorithm>
-#include <limits>
 #include <queue>
+#include <itkProcessObject.h>
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+fpa::Base::Algorithm< V, C, R, VC, B >::_TNode::
+_TNode( )
+  : Result( TResult( 0 ) ),
+    FrontId( -1 ),
+    Label( Self::FarLabel )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+fpa::Base::Algorithm< V, C, R, VC, B >::_TNode::
+~_TNode( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+typename fpa::Base::Algorithm< V, C, R, VC, B >::
+TMinimumSpanningTree* fpa::Base::Algorithm< V, C, R, VC, B >::
+GetMinimumSpanningTree( )
+{
+  return(
+    dynamic_cast< TMinimumSpanningTree* >(
+      this->itk::ProcessObject::GetOutput( 1 )
+      )
+    );
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+const typename fpa::Base::Algorithm< V, C, R, VC, B >::
+TMinimumSpanningTree* fpa::Base::Algorithm< V, C, R, VC, B >::
+GetMinimumSpanningTree( ) const
+{
+  return(
+    dynamic_cast< const TMinimumSpanningTree* >(
+      this->itk::ProcessObject::GetOutput( 1 )
+      )
+    );
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+GraftMinimumSpanningTree( itk::DataObject* obj )
+{
+  TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
+  if( mst != NULL )
+    this->GraftNthOutput( 1, mst );
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
 InvokeEvent( const itk::EventObject& e )
 {
   if( this->m_ThrowEvents )
@@ -15,8 +67,8 @@ InvokeEvent( const itk::EventObject& e )
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
 InvokeEvent( const itk::EventObject& e ) const
 {
   if( this->m_ThrowEvents )
@@ -24,197 +76,223 @@ InvokeEvent( const itk::EventObject& e ) const
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-AddSeed( const TVertex& s, const TResult& v )
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+AddSeed( const TVertex& s, const TResult& r )
 {
-  this->m_Seeds.push_back( _TNode( s, v, this->m_Seeds.size( ) ) );
+  _TNode ns;
+  ns.Parent = s;
+  ns.Result = r;
+  ns.FrontId = this->m_SeedVertices.size( );
+  ns.Label = Self::FrontLabel;
+  this->m_Seeds[ s ] = ns;
+  this->m_SeedVertices.push_back( s );
   this->Modified( );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-const typename fpa::Base::Algorithm< T, B >::
-TVertex& fpa::Base::Algorithm< T, B >::
-GetSeed( const unsigned long& i ) const
+template< class V, class C, class R, class VC, class B >
+const typename fpa::Base::Algorithm< V, C, R, VC, B >::
+TVertex& fpa::Base::Algorithm< V, C, R, VC, B >::
+GetSeed( const unsigned int& id ) const
 {
-  return( this->m_Seeds[ i ].Vertex );
+  return( this->m_SeedVertices[ id ] );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
 ClearSeeds( )
 {
   this->m_Seeds.clear( );
+  this->m_SeedVertices.clear( );
   this->Modified( );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-unsigned long fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+unsigned long fpa::Base::Algorithm< V, C, R, VC, B >::
 GetNumberOfSeeds( ) const
 {
   return( this->m_Seeds.size( ) );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+fpa::Base::Algorithm< V, C, R, VC, B >::
 Algorithm( )
   : Superclass( ),
-    m_StopAtOneFront( false ),
-    m_ThrowEvents( false )
+    m_ThrowEvents( false ),
+    m_StopAtOneFront( false )
 {
+  this->m_MinimumSpanningTreeIndex = this->GetNumberOfRequiredOutputs( );
+  this->SetNumberOfRequiredOutputs( this->m_MinimumSpanningTreeIndex + 1 );
+  this->itk::ProcessObject::SetNthOutput(
+    this->m_MinimumSpanningTreeIndex, TMinimumSpanningTree::New( )
+    );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+fpa::Base::Algorithm< V, C, R, VC, B >::
 ~Algorithm( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
 GenerateData( )
 {
-  this->AllocateOutputs( );
-
   unsigned long N = this->m_Seeds.size( );
   if( N == 0 )
     return;
-  this->m_CollisionSites.clear( );
-  this->m_CollisionSites.
-    resize( N, _TCollisionSitesRow( N, _TCollision( TVertex( ), false ) ) );
-
-  this->_BeforeMainLoop( );
-  this->_InitializeMarks( );
-  this->_InitializeResults( );
-  this->_InitializeQueue( );
-  this->_Loop( );
-  this->_AfterMainLoop( );
-}
 
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_BeforeMainLoop( )
-{
-}
+  this->InvokeEvent( TStartEvent( ) );
+  this->_BeforeGenerateData( );
 
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_AfterMainLoop( )
-{
-}
-
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_BeforeLoop( )
-{
-}
-
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_AfterLoop( )
-{
+  this->m_Collisions.clear( );
+  this->m_Collisions.
+    resize( N, _TCollisionsRow( N, _TCollision( TVertex( ), false ) ) );
+  this->_InitResults( );
+  this->_InitMarks( );
+  this->_InitQueue( );
+  this->_Loop( );
+  this->_AfterGenerateData( );
+  this->InvokeEvent( TEndEvent( ) );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
 _Loop( )
 {
+  this->InvokeEvent( TStartLoopEvent( ) );
   this->_BeforeLoop( );
   while( !( this->_IsQueueEmpty( ) ) )
   {
-    _TNode n = this->_QueuePop( );
-    if( this->_IsMarked( n.Vertex ) )
+    // Get next candidate
+    TVertex vertex;
+    _TNode node;
+    this->_QueuePop( vertex, node );
+    if( this->_Node( vertex ).Label == Self::AliveLabel )
       continue;
 
-    this->_Mark( n );
-    this->InvokeEvent( TMarkEvent( n ) );
-    if( this->_UpdateResult( n ) )
+    // Mark it as "Alive" and update final result
+    node.Label = Self::AliveLabel;
+    this->_Mark( vertex, node );
+    this->_SetResult( vertex, node );
+    this->InvokeEvent( TAliveEvent( vertex, node.FrontId ) );
+
+    // Check if a forced stop condition arises
+    if( !( this->_NeedToStop( ) ) )
     {
-      if( !( this->_CheckStopCondition( ) ) )
+      // Compute neighborhood
+      _TVertices neighborhood;
+      this->_Neighborhood( neighborhood, vertex );
+
+      // Iterate over neighbors
+      typename _TVertices::iterator nIt = neighborhood.begin( );
+      while( nIt != neighborhood.end( ) )
       {
-        _TNodes N;
-        this->_Neighs( n, N );
-        typename _TNodes::iterator nnIt = N.begin( );
-        while( nnIt != N.end( ) )
+        _TNode neighbor = this->_Node( *nIt );
+        if( neighbor.Label == Self::AliveLabel )
         {
-          if( this->_IsMarked( nnIt->Vertex ) )
+          // Update collisions
+          if( this->_UpdateCollisions( vertex, *nIt ) )
           {
-            // Update real front identifier
-            nnIt->FrontId = this->_FrontId( nnIt->Vertex );
-
-            // Update collisions
-            if( this->_CheckCollisions( n, *nnIt ) )
-            {
-              if( this->m_StopAtOneFront )
-              {
-                this->_QueueClear( );
-                nnIt = N.end( );
-
-              } // fi
+            this->_QueueClear( );
+            nIt = neighborhood.end( );
+            continue;
 
-            } // fi
+          } // fi
+        }
+        else
+        {
+          // Add new candidate to queue
+          if( this->_ComputeNeighborResult( neighbor.Result, *nIt, vertex ) )
+          {
+            neighbor.FrontId = node.FrontId;
+            neighbor.Parent = vertex;
+            neighbor.Label = Self::FrontLabel;
+            this->_QueuePush( *nIt, neighbor );
+            this->_Mark( *nIt, neighbor );
+            this->InvokeEvent( TFrontEvent( *nIt, node.FrontId ) );
           }
           else
-          {
-            if( this->_UpdateNeigh( *nnIt, n ) )
-            {
-              nnIt->Parent = n.Vertex;
-              this->_QueuePush( *nnIt );
-              this->InvokeEvent( TFrontEvent( *nnIt ) );
+            this->InvokeEvent( TFreezeEvent( *nIt, node.FrontId ) );
 
-            } // fi
+        } // fi
+        ++nIt;
 
-          } // fi
-          if( nnIt != N.end( ) )
-            nnIt++;
-
-        } // elihw
-      }
-      else
-        this->_QueueClear( );
-
-    } // fi
+      } // elihw
+    }
+    else
+      this->_QueueClear( );
 
   } // elihw
-  this->InvokeEvent( TEndEvent( ) );
   this->_AfterLoop( );
+  this->InvokeEvent( TEndLoopEvent( ) );
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_BeforeGenerateData( )
+{
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-bool fpa::Base::Algorithm< T, B >::
-_CheckCollisions( const _TNode& a, const _TNode& b )
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_AfterGenerateData( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_BeforeLoop( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_AfterLoop( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+bool fpa::Base::Algorithm< V, C, R, VC, B >::
+_UpdateCollisions( const TVertex& a, const TVertex& b )
 {
   bool ret = false;
-  if( a.FrontId != b.FrontId )
+  _TNode na = this->_Node( a );
+  _TNode nb = this->_Node( b );
+  long fa = na.FrontId;
+  long fb = nb.FrontId;
+
+  if( fa != fb )
   {
     // Mark collision, if it is new
-    bool exists = this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second;
-    exists     &= this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second;
+    bool exists = this->m_Collisions[ fa ][ fb ].second;
+    exists     &= this->m_Collisions[ fb ][ fa ].second;
+        
     if( !exists )
     {
-      this->m_CollisionSites[ a.FrontId ][ b.FrontId ].first = a.Vertex;
-      this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second = true;
-      this->m_CollisionSites[ b.FrontId ][ a.FrontId ].first = b.Vertex;
-      this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second = true;
+      this->m_Collisions[ fa ][ fb ].first = a;
+      this->m_Collisions[ fa ][ fb ].second = true;
+      this->m_Collisions[ fb ][ fa ].first = b;
+      this->m_Collisions[ fb ][ fa ].second = true;
 
       // Stop if one front is desired
       if( this->m_StopAtOneFront )
       {
         // Perform a depth-first iteration on front graph
         unsigned long N = this->GetNumberOfSeeds( );
-        unsigned long C = 0;
+        unsigned long count = 0;
         std::vector< bool > m( N, false );
         std::queue< unsigned long > q;
         q.push( 0 );
@@ -226,14 +304,14 @@ _CheckCollisions( const _TNode& a, const _TNode& b )
           if( m[ f ] )
             continue;
           m[ f ] = true;
-          C++;
+          count++;
 
           for( unsigned int n = 0; n < N; ++n )
-            if( this->m_CollisionSites[ f ][ n ].second && !m[ n ] )
+            if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
               q.push( n );
 
         } // elihw
-        ret = ( C == N );
+        ret = ( count == N );
 
       } // fi
 
@@ -244,69 +322,76 @@ _CheckCollisions( const _TNode& a, const _TNode& b )
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-bool fpa::Base::Algorithm< T, B >::
-_CheckStopCondition( )
+template< class V, class C, class R, class VC, class B >
+bool fpa::Base::Algorithm< V, C, R, VC, B >::
+_NeedToStop( ) const
 {
   return( false );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-bool fpa::Base::Algorithm< T, B >::
-_UpdateResult( _TNode& n )
+template< class V, class C, class R, class VC, class B >
+typename fpa::Base::Algorithm< V, C, R, VC, B >::
+_TNode& fpa::Base::Algorithm< V, C, R, VC, B >::
+_Node( const TVertex& v )
 {
-  return( true );
-}
+  typename _TNodes::iterator vIt = this->m_Marks.find( v );
+  if( vIt == this->m_Marks.end( ) )
+  {
+    _TNode new_node;
+    new_node.Parent = v;
+    new_node.Result = TResult( 0 );
+    new_node.FrontId = -1;
+    new_node.Label = Self::FarLabel;
+    this->m_Marks[ v ] = new_node;
+    vIt = this->m_Marks.find( v );
 
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_InitializeMarks( )
-{
-  this->m_Marks.clear( );
+  } // fi
+  return( vIt->second );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-bool  fpa::Base::Algorithm< T, B >::
-_IsMarked( const TVertex& v ) const
+template< class V, class C, class R, class VC, class B >
+const typename fpa::Base::Algorithm< V, C, R, VC, B >::
+_TNode& fpa::Base::Algorithm< V, C, R, VC, B >::
+_Node( const TVertex& v ) const
 {
-  return( this->m_Marks.find( v ) != this->m_Marks.end( ) );
+  typename _TNodes::const_iterator vIt = this->m_Marks.find( v );
+  return( vIt->second );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-typename fpa::Base::Algorithm< T, B >::
-_TFrontId fpa::Base::Algorithm< T, B >::
-_FrontId( const TVertex& v ) const
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_InitMarks( )
 {
-  typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
-  if( mIt != this->m_Marks.end( ) )
-    return( mIt->second.FrontId );
-  else
-    return( std::numeric_limits< _TFrontId >::max( ) );
+  this->m_Marks.clear( );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-typename fpa::Base::Algorithm< T, B >::
-TVertex fpa::Base::Algorithm< T, B >::
-_Parent( const TVertex& v ) const
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_Mark( const TVertex& v, const _TNode& node )
 {
-  typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
-  if( mIt == this->m_Marks.end( ) )
-    return( TVertex( ) );
-  else
-    return( mIt->second.Parent );
+  this->m_Marks[ v ] = node;
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void  fpa::Base::Algorithm< T, B >::
-_Mark( const _TNode& n )
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_InitQueue( )
 {
-  this->m_Marks[ n.Vertex ] = n;
+  this->_QueueClear( );
+  for(
+    typename _TNodes::const_iterator sIt = this->m_Seeds.begin( );
+    sIt != this->m_Seeds.end( );
+    sIt++
+    )
+  {
+    this->_QueuePush( sIt->first, sIt->second );
+    this->_Mark( sIt->first, sIt->second );
+
+  } // rof
 }
 
 #endif // __FPA__BASE__ALGORITHM__HXX__