X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FDijkstra.hxx;h=b7c10f478a2d6eee59fa04fbc08b0501ca23b4e6;hb=c370699e769d8db284c58534c7a45f11dc9fb8b3;hp=bad348b1156ac276f388bfbfb367dec486f0b91a;hpb=8fafb83c41ab35dfc25eb637170882a612924433;p=FrontAlgorithms.git

diff --git a/lib/fpa/Base/Dijkstra.hxx b/lib/fpa/Base/Dijkstra.hxx
index bad348b..b7c10f4 100644
--- a/lib/fpa/Base/Dijkstra.hxx
+++ b/lib/fpa/Base/Dijkstra.hxx
@@ -1,145 +1,195 @@
-#ifndef __FPA__BASE__DIJKSTRA__HXX__
-#define __FPA__BASE__DIJKSTRA__HXX__
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
 
-#include <algorithm>
+#ifndef __fpa__Base__Dijkstra__hxx__
+#define __fpa__Base__Dijkstra__hxx__
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-typename fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-TMinimumSpanningTree* fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+typename
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+TMST* fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
 GetMinimumSpanningTree( )
 {
   return(
-    dynamic_cast< TMinimumSpanningTree* >(
-      this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
+    dynamic_cast< TMST* >(
+      this->itk::ProcessObject::GetOutput( this->m_MSTIndex )
       )
     );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-const typename fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-TMinimumSpanningTree* fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+const typename
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+TMST* fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
 GetMinimumSpanningTree( ) const
 {
   return(
-    dynamic_cast< const TMinimumSpanningTree* >(
-      this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
+    dynamic_cast< const TMST* >(
+      this->itk::ProcessObject::GetOutput( this->m_MSTIndex )
       )
     );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-GraftMinimumSpanningTree( itk::DataObject* obj )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+const typename
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+TIntensityFunctor*
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+GetIntensityFunctor( ) const
 {
-  TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
-  if( mst != NULL )
-    this->GraftNthOutput( this->m_MSTIdx, mst );
+  return( this->m_IntensityFunctor );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-Dijkstra( )
-  : Superclass( ),
-    m_LocalCosts( false ),
-    m_FillNodeQueue( false )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+const typename
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+TVertexFunctor*
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+GetVertexFunctor( ) const
 {
-  this->m_MSTIdx = this->GetNumberOfRequiredOutputs( );
-  this->SetNumberOfRequiredOutputs( this->m_MSTIdx + 1 );
-  this->itk::ProcessObject::SetNthOutput(
-    this->m_MSTIdx, TMinimumSpanningTree::New( )
-    );
+  return( this->m_VertexFunctor );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-~Dijkstra( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+SetFunctor( TIntensityFunctor* functor )
 {
-}
+  if( this->m_IntensityFunctor.GetPointer( ) != functor )
+  {
+    this->m_IntensityFunctor = functor;
+    this->Modified( );
 
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-_BeforeGenerateData( )
-{
-  this->Superclass::_BeforeGenerateData( );
-  this->GetMinimumSpanningTree( )->SetFillNodeQueue( this->m_FillNodeQueue );
+  } // fi
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-bool fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-_ComputeNeighborResult(
-  TResult& result, const TVertex& neighbor, const TVertex& parent
-  ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+SetFunctor( TVertexFunctor* functor )
 {
-  result  = this->_Cost( neighbor, parent );
-  result *= TResult( this->_Distance( neighbor, parent ) );
-
-  // WARNING: Dijkstra does not work on negative values!
-  if( result >= TResult( 0 ) )
+  if( this->m_VertexFunctor.GetPointer( ) != functor )
   {
-    _TNode pn = this->_Node( parent );
-    if( pn.Label == Self::AliveLabel && !this->m_LocalCosts )
-      result += pn.Result;
-    return( true );
-  }
-  else
-    return( false );
-}
+    this->m_VertexFunctor = functor;
+    this->Modified( );
 
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-_SetResult( const TVertex& v, const _TNode& n )
-{
-  this->GetMinimumSpanningTree( )->SetNode( v, n.Parent, n.FrontId, n.Result );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-bool fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-_IsQueueEmpty( ) const
-{
-  return( this->m_Queue.empty( ) );
+  } // fi
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-_QueuePush( const TVertex& v, const _TNode& n )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+Dijkstra( )
+  : Superclass( ),
+    _TMarksInterface( this ),
+    _TSeedsInterface( this )
 {
-  _TQueueNode qn;
-  qn.Vertex = v;
-  qn.Node = n;
-  this->m_Queue.push_back( qn );
-  std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
+  this->m_MSTIndex = this->GetNumberOfRequiredOutputs( );
+  this->SetNumberOfRequiredOutputs( this->m_MSTIndex + 1 );
+  this->itk::ProcessObject::SetNthOutput( this->m_MSTIndex, TMST::New( ) );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-_QueuePop( TVertex& v, _TNode& n )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+~Dijkstra( )
 {
-  _TQueueNode qn = this->m_Queue.front( );
-  std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
-  this->m_Queue.pop_back( );
-  v = qn.Vertex;
-  n = qn.Node;
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class MST, class B >
-void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
-_QueueClear( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+GenerateData( )
 {
-  this->m_Queue.clear( );
+  // Init objects
+  this->_ConfigureOutputs( std::numeric_limits< TOutputValue >::max( ) );
+  this->_InitMarks( this->GetNumberOfSeeds( ) );
+  TMST* mst = this->GetMinimumSpanningTree( );
+
+  // Init queue
+  std::vector< _TNode > q;
+  unsigned long frontId = 1;
+  typename TSeedsInterface::TSeeds::const_iterator sIt = this->BeginSeeds( );
+  for( ; sIt != this->EndSeeds( ); ++sIt )
+    q.push_back( _TNode( *sIt, *sIt, frontId++ ) );
+
+  // Main loop
+  while( q.size( ) > 0 )
+  {
+    // Get next candidate
+    std::pop_heap( q.begin( ), q.end( ) );
+    _TNode node = q.back( );
+    q.pop_back( );
+    if( this->_IsMarked( node.Vertex ) )
+      continue;
+    this->_Mark( node.Vertex, node.FrontId );
+
+    // Ok, pixel lays inside region
+    this->_SetOutputValue( node.Vertex, node.Cost );
+    mst->SetParent( node.Vertex, node.Parent );
+
+    // Add neighborhood
+    TVertices neighbors = this->_GetNeighbors( node.Vertex );
+    typename TVertices::const_iterator neighIt = neighbors.begin( );
+    bool coll = false;
+    while( neighIt != neighbors.end( ) && !coll )
+    {
+      TVertex neigh = *neighIt;
+      if( this->_IsMarked( neigh ) )
+      {
+        // Invoke stop at collisions
+        unsigned long nColl = this->_Collisions( node.Vertex, neigh );
+        if(
+          this->StopAtOneFront( ) &&
+          this->GetNumberOfSeeds( ) > 1 &&
+          nColl == 1
+          )
+        {
+          q.clear( );
+          coll = true;
+
+        } // fi
+      }
+      else
+      {
+        // Compute new cost
+        TOutputValue ncost =
+          this->m_VertexFunctor->Evaluate( neigh, node.Vertex );
+        if( this->m_IntensityFunctor.IsNotNull( ) )
+          ncost = this->m_IntensityFunctor->Evaluate( ncost );
+
+        // This algorithm only supports positive values
+        if( ncost >= TOutputValue( 0 ) )
+        {
+          // Insert new node
+          _TNode nn( neigh, node.Vertex, node.FrontId );
+          nn.Cost = node.Cost + ncost;
+          q.push_back( nn );
+          std::push_heap( q.begin( ), q.end( ) );
+
+        } // fi
+
+      } // fi
+      ++neighIt;
+
+    } // elihw
+
+  } // elihw
+  this->_FreeMarks( );
+
+  // Complete data into minimum spanning tree
+  mst->ClearSeeds( );
+  mst->SetCollisions( this->m_Collisions );
+  for( sIt = this->BeginSeeds( ); sIt != this->EndSeeds( ); ++sIt )
+    mst->AddSeed( *sIt );
 }
 
-#endif // __FPA__BASE__DIJKSTRA__HXX__
+#endif // __fpa__Base__Dijkstra__hxx__
 
 // eof - $RCSfile$