#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__
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff