X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FDijkstra.hxx;h=25a7bd90caffba6e1ffc0fe36be116ce24f5b4f6;hb=56b8bb48cc05a297a3faa264f8f2a88de21ef203;hp=25d56504051fbb1b2b1bccd01a9a239487764051;hpb=015105c2f44abb80923a59adfb1a01713506744f;p=FrontAlgorithms.git

diff --git a/lib/fpa/Base/Dijkstra.hxx b/lib/fpa/Base/Dijkstra.hxx
index 25d5650..25a7bd9 100644
--- a/lib/fpa/Base/Dijkstra.hxx
+++ b/lib/fpa/Base/Dijkstra.hxx
@@ -4,37 +4,98 @@
 #include <algorithm>
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-fpa::Base::Dijkstra< V, C, R, S, VC, B >::
+template< class _TSuperclass >
+const typename fpa::Base::Dijkstra< _TSuperclass >::TDijkstraCmp
+fpa::Base::Dijkstra< _TSuperclass >::DijkstraCmp =
+fpa::Base::Dijkstra< _TSuperclass >::TDijkstraCmp( );
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass >
+typename fpa::Base::Dijkstra< _TSuperclass >::
+TMinimumSpanningTree* fpa::Base::Dijkstra< _TSuperclass >::
+GetMinimumSpanningTree( )
+{
+  return(
+    dynamic_cast< TMinimumSpanningTree* >(
+      this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
+      )
+    );
+}
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass >
+const typename fpa::Base::Dijkstra< _TSuperclass >::
+TMinimumSpanningTree* fpa::Base::Dijkstra< _TSuperclass >::
+GetMinimumSpanningTree( ) const
+{
+  return(
+    dynamic_cast< const TMinimumSpanningTree* >(
+      this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
+      )
+    );
+}
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass >
+void fpa::Base::Dijkstra< _TSuperclass >::
+GraftMinimumSpanningTree( itk::DataObject* obj )
+{
+  TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
+  if( mst != NULL )
+    this->GraftNthOutput( this->m_MSTIdx, mst );
+}
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass >
+fpa::Base::Dijkstra< _TSuperclass >::
 Dijkstra( )
   : Superclass( ),
-    m_LocalCosts( false )
+    m_CostConversionFunction( NULL )
 {
+  this->m_MSTIdx = this->GetNumberOfRequiredOutputs( );
+  this->SetNumberOfRequiredOutputs( this->m_MSTIdx + 1 );
+  typename TMinimumSpanningTree::Pointer mst = TMinimumSpanningTree::New( );
+  this->itk::ProcessObject::SetNthOutput( this->m_MSTIdx, mst );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-fpa::Base::Dijkstra< V, C, R, S, VC, B >::
+template< class _TSuperclass >
+fpa::Base::Dijkstra< _TSuperclass >::
 ~Dijkstra( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-bool fpa::Base::Dijkstra< V, C, R, S, VC, B >::
-_ComputeNeighborResult(
-  TResult& result, const TVertex& neighbor, const TVertex& parent
-  ) const
+template< class _TSuperclass >
+void fpa::Base::Dijkstra< _TSuperclass >::
+_AfterGenerateData( )
 {
-  result  = this->_Cost( neighbor, parent );
-  result *= TResult( this->_Distance( neighbor, parent ) );
+  this->Superclass::_AfterGenerateData( );
+  this->GetMinimumSpanningTree( )->SetCollisions( this->m_Collisions );
+}
 
-  // WARNING: Dijkstra does not work on negative values!
-  if( result >= TResult( 0 ) )
+// -------------------------------------------------------------------------
+template< class _TSuperclass >
+void fpa::Base::Dijkstra< _TSuperclass >::
+_Visit( const TNode& n )
+{
+  this->Superclass::_Visit( n );
+  this->GetMinimumSpanningTree( )->SetNode(
+    n.Vertex, n.Parent, n.FrontId, n.Result
+    );
+}
+
+// -------------------------------------------------------------------------
+template< class _TSuperclass >
+bool fpa::Base::Dijkstra< _TSuperclass >::
+_Result( TNode& node, const TNode& parent )
+{
+  node.Result = this->_Cost( node.Vertex, parent.Vertex );
+  if( node.Result >= TScalar( 0 ) )
   {
-    _TNode pn = this->_Node( parent );
-    if( pn.Label == Self::AliveLabel && !this->m_LocalCosts )
-      result += pn.Result;
+    if( this->m_CostConversionFunction.IsNotNull( ) )
+      node.Result = this->m_CostConversionFunction->Evaluate( node.Result );
+    node.Result += parent.Result;
     return( true );
   }
   else
@@ -42,43 +103,40 @@ _ComputeNeighborResult(
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-bool fpa::Base::Dijkstra< V, C, R, S, VC, B >::
-_IsQueueEmpty( ) const
+template< class _TSuperclass >
+void fpa::Base::Dijkstra< _TSuperclass >::
+_QueueClear( )
 {
-  return( this->m_Queue.empty( ) );
+  this->m_Queue.clear( );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Dijkstra< V, C, R, S, VC, B >::
-_QueuePush( const TVertex& v, const _TNode& n )
+template< class _TSuperclass >
+void fpa::Base::Dijkstra< _TSuperclass >::
+_QueuePush( const TNode& node )
 {
-  _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_Queue.push_back( node );
+  std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ), DijkstraCmp );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Dijkstra< V, C, R, S, VC, B >::
-_QueuePop( TVertex& v, _TNode& n )
+template< class _TSuperclass >
+typename fpa::Base::Dijkstra< _TSuperclass >::
+TNode fpa::Base::Dijkstra< _TSuperclass >::
+_QueuePop( )
 {
-  _TQueueNode qn = this->m_Queue.front( );
-  std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
+  std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ), DijkstraCmp );
+  TNode n = this->m_Queue.back( );
   this->m_Queue.pop_back( );
-  v = qn.Vertex;
-  n = qn.Node;
+  return( n );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Dijkstra< V, C, R, S, VC, B >::
-_QueueClear( )
+template< class _TSuperclass >
+bool fpa::Base::Dijkstra< _TSuperclass >::
+_IsQueueEmpty( ) const
 {
-  this->m_Queue.clear( );
+  return( this->m_Queue.size( ) == 0 );
 }
 
 #endif // __FPA__BASE__DIJKSTRA__HXX__