X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FDijkstra.hxx;h=bad348b1156ac276f388bfbfb367dec486f0b91a;hb=826a318db2e9b41fbd865e41ebb5906efdefbb02;hp=4920ab551628489db9f03d42660ba408e40b31df;hpb=9622bd5b833a8845881003228207e0caca59b081;p=FrontAlgorithms.git

diff --git a/lib/fpa/Base/Dijkstra.hxx b/lib/fpa/Base/Dijkstra.hxx
index 4920ab5..bad348b 100644
--- a/lib/fpa/Base/Dijkstra.hxx
+++ b/lib/fpa/Base/Dijkstra.hxx
@@ -4,90 +4,140 @@
 #include <algorithm>
 
 // -------------------------------------------------------------------------
-template< class V, class C, class VV, class VC, class B >
-fpa::Base::Dijkstra< V, C, VV, VC, B >::
+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 >::
+GetMinimumSpanningTree( )
+{
+  return(
+    dynamic_cast< TMinimumSpanningTree* >(
+      this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
+      )
+    );
+}
+
+// -------------------------------------------------------------------------
+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 >::
+GetMinimumSpanningTree( ) const
+{
+  return(
+    dynamic_cast< const TMinimumSpanningTree* >(
+      this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
+      )
+    );
+}
+
+// -------------------------------------------------------------------------
+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 )
+{
+  TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
+  if( mst != NULL )
+    this->GraftNthOutput( this->m_MSTIdx, mst );
+}
+
+// -------------------------------------------------------------------------
+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( )
+  : Superclass( ),
+    m_LocalCosts( false ),
+    m_FillNodeQueue( false )
 {
+  this->m_MSTIdx = this->GetNumberOfRequiredOutputs( );
+  this->SetNumberOfRequiredOutputs( this->m_MSTIdx + 1 );
+  this->itk::ProcessObject::SetNthOutput(
+    this->m_MSTIdx, TMinimumSpanningTree::New( )
+    );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class VV, class VC, class B >
-fpa::Base::Dijkstra< V, C, VV, VC, B >::
+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 V, class C, class VV, class VC, class B >
-void fpa::Base::Dijkstra< V, C, VV, VC, B >::
-_InitializeQueue( )
+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( )
 {
-  for(
-    typename _TNodes::const_iterator vIt = this->m_Seeds.begin( );
-    vIt != this->m_Seeds.end( );
-    vIt++
-    )
-    this->_QueuePush( *vIt );
+  this->Superclass::_BeforeGenerateData( );
+  this->GetMinimumSpanningTree( )->SetFillNodeQueue( this->m_FillNodeQueue );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class VV, class VC, class B >
-bool fpa::Base::Dijkstra< V, C, VV, VC, B >::
-_IsQueueEmpty( ) const
+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
 {
-  return( this->m_Queue.empty( ) );
+  result  = this->_Cost( neighbor, parent );
+  result *= TResult( this->_Distance( neighbor, parent ) );
+
+  // WARNING: Dijkstra does not work on negative values!
+  if( result >= TResult( 0 ) )
+  {
+    _TNode pn = this->_Node( parent );
+    if( pn.Label == Self::AliveLabel && !this->m_LocalCosts )
+      result += pn.Result;
+    return( true );
+  }
+  else
+    return( false );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class VV, class VC, class B >
-void fpa::Base::Dijkstra< V, C, VV, VC, B >::
-_QueuePush( const _TNode& n )
+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->m_Queue.push_back( n );
-  std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
+  this->GetMinimumSpanningTree( )->SetNode( v, n.Parent, n.FrontId, n.Result );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class VV, class VC, class B >
-typename fpa::Base::Dijkstra< V, C, VV, VC, B >::
-_TNode fpa::Base::Dijkstra< V, C, VV, VC, B >::
-_QueuePop( )
+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
 {
-  _TNode n;
-  if( !( this->m_Queue.empty( ) ) )
-  {
-    // n = *( this->m_Queue.begin( ) );
-    n = this->m_Queue.front( );
-    std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
-    this->m_Queue.pop_back( );
+  return( this->m_Queue.empty( ) );
+}
 
-  } // fi
-  return( n );
+// -------------------------------------------------------------------------
+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 )
+{
+  _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( ) );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class VV, class VC, class B >
-void fpa::Base::Dijkstra< V, C, VV, VC, B >::
-_QueueClear( )
+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 )
 {
-  this->m_Queue.clear( );
+  _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 VV, class VC, class B >
-bool fpa::Base::Dijkstra< V, C, VV, VC, B >::
-_UpdateNeigh( _TNode& nn, const _TNode& n )
+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( )
 {
-  TCost nc = this->_Cost( nn.Vertex, n.Vertex );
-  if( C( 0 ) <= nc )
-  {
-    nn.Cost = n.Cost + nc;
-    nn.Result = nn.Cost;
-    return( true );
-  }
-  else
-    return( false );
+  this->m_Queue.clear( );
 }
 
 #endif // __FPA__BASE__DIJKSTRA__HXX__