X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FDijkstra.h;h=d231c7c41da897886b69c63d97f0fca117908646;hb=60785c9e18cab1a338f1ce54551e97a5ddfabac1;hp=e711f4f56c844cde21766d47a6c2e789683737a4;hpb=8fafb83c41ab35dfc25eb637170882a612924433;p=FrontAlgorithms.git diff --git a/lib/fpa/Base/Dijkstra.h b/lib/fpa/Base/Dijkstra.h index e711f4f..d231c7c 100644 --- a/lib/fpa/Base/Dijkstra.h +++ b/lib/fpa/Base/Dijkstra.h @@ -1,120 +1,91 @@ -#ifndef __FPA__BASE__DIJKSTRA__H__ -#define __FPA__BASE__DIJKSTRA__H__ +// ========================================================================= +// @author Leonardo Florez Valencia +// @email florez-l@javeriana.edu.co +// ========================================================================= -#include -#include +#ifndef __fpa__Base__Dijkstra__h__ +#define __fpa__Base__Dijkstra__h__ + +#include #include +#include namespace fpa { namespace Base { /** - * Dijkstra is a front propagation algorithm that minimizes costs - * - * @param V Vertex type. - * @param C Vertex value type. - * @param R Result value type. - * @param S Space type where vertices are. - * @param VC Vertex lexicographical compare. - * @param MST Minimum spanning tree type. - * @param B Base class for this algorithm. It should be any itk-based - * filter (itk::ProcessObject). - * */ - template< class V, class C, class R, class S, class VC, class MST, class B > + template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST > class Dijkstra - : public Algorithm< V, C, R, S, VC, B > + : public _TFilter, + public _TMarksInterface, + public _TSeedsInterface { public: - typedef Dijkstra Self; - typedef Algorithm< V, C, R, S, VC, B > Superclass; - typedef itk::SmartPointer< Self > Pointer; - typedef itk::SmartPointer< const Self > ConstPointer; - - typedef MST TMinimumSpanningTree; - typedef typename Superclass::TVertex TVertex; - typedef typename Superclass::TValue TValue; - typedef typename Superclass::TResult TResult; - typedef typename Superclass::TSpace TSpace; - typedef typename Superclass::TVertexCompare TVertexCompare; - - typedef typename Superclass::TStartEvent TStartEvent; - typedef typename Superclass::TStartLoopEvent TStartLoopEvent; - typedef typename Superclass::TEndEvent TEndEvent; - typedef typename Superclass::TEndLoopEvent TEndLoopEvent; - typedef typename Superclass::TAliveEvent TAliveEvent; - typedef typename Superclass::TFrontEvent TFrontEvent; - typedef typename Superclass::TFreezeEvent TFreezeEvent; - - typedef typename Superclass::TStartBacktrackingEvent TStartBacktrackingEvent; - typedef typename Superclass::TEndBacktrackingEvent TEndBacktrackingEvent; - typedef typename Superclass::TBacktrackingEvent TBacktrackingEvent; + typedef Dijkstra Self; + typedef _TFilter Superclass; + typedef _TMarksInterface TMarksInterface; + typedef _TSeedsInterface TSeedsInterface; + typedef _TMST TMST; + typedef itk::SmartPointer< Self > Pointer; + typedef itk::SmartPointer< const Self > ConstPointer; + + typedef typename Superclass::TInputValue TInputValue; + typedef typename Superclass::TOutputValue TOutputValue; + typedef typename Superclass::TVertex TVertex; + typedef typename Superclass::TVertices TVertices; + + typedef itk::FunctionBase< TInputValue, TOutputValue > TIntensityFunctor; + typedef fpa::Base::Functors::VertexParentBase< TVertex, TOutputValue > TVertexFunctor; protected: - typedef typename Superclass::_TVertices _TVertices; - typedef typename Superclass::_TCollision _TCollision; - typedef typename Superclass::_TCollisionsRow _TCollisionsRow; - typedef typename Superclass::_TCollisions _TCollisions; - typedef typename Superclass::_TNode _TNode; - typedef typename Superclass::_TNodes _TNodes; - - struct _TQueueNode + struct _TNode { TVertex Vertex; - _TNode Node; - - // Make the min-heap behave as a max-heap - bool operator<( const _TQueueNode& other ) const - { return( other.Node.Result < this->Node.Result ); } + TVertex Parent; + TOutputValue Cost; + unsigned long FrontId; + _TNode( const TVertex& v, const TVertex& p, const unsigned long& fId ) + { + this->Vertex = v; + this->Parent = p; + this->FrontId = fId; + this->Cost = TOutputValue( 0 ); + } + bool operator<( const _TNode& b ) const + { + return( b.Cost < this->Cost ); + } }; - typedef std::vector< _TQueueNode > _TQueue; public: - itkTypeMacro( Dijkstra, Algorithm ); - - itkBooleanMacro( LocalCosts ); - itkBooleanMacro( FillNodeQueue ); - itkGetConstMacro( LocalCosts, bool ); - itkGetConstMacro( FillNodeQueue, bool ); - itkSetMacro( LocalCosts, bool ); - itkSetMacro( FillNodeQueue, bool ); + itkTypeMacro( Dijkstra, TFilter ); public: - TMinimumSpanningTree* GetMinimumSpanningTree( ); - const TMinimumSpanningTree* GetMinimumSpanningTree( ) const; - void GraftMinimumSpanningTree( itk::DataObject* obj ); + TMST* GetMinimumSpanningTree( ); + const TMST* GetMinimumSpanningTree( ) const; + + const TIntensityFunctor* GetIntensityFunctor( ) const; + const TVertexFunctor* GetVertexFunctor( ) const; + + void SetFunctor( TIntensityFunctor* functor ); + void SetFunctor( TVertexFunctor* functor ); protected: Dijkstra( ); virtual ~Dijkstra( ); - virtual TResult _Cost( const TVertex& v, const TVertex& p ) const = 0; - - virtual void _BeforeGenerateData( ); - - // Results-related abstract methods - virtual bool _ComputeNeighborResult( - TResult& result, const TVertex& neighbor, const TVertex& parent - ) const; - virtual void _SetResult( const TVertex& v, const _TNode& n ); - - // Queue-related abstract methods - virtual bool _IsQueueEmpty( ) const; - virtual void _QueuePush( const TVertex& v, const _TNode& n ); - virtual void _QueuePop( TVertex& v, _TNode& n ); - virtual void _QueueClear( ); + virtual void GenerateData( ) override; private: - // Purposely not implemented Dijkstra( const Self& other ); Self& operator=( const Self& other ); protected: - bool m_LocalCosts; - bool m_FillNodeQueue; - _TQueue m_Queue; - unsigned int m_MSTIdx; + typename TIntensityFunctor::Pointer m_IntensityFunctor; + typename TVertexFunctor::Pointer m_VertexFunctor; + unsigned long m_MSTIndex; }; } // ecapseman @@ -122,9 +93,9 @@ namespace fpa } // ecapseman #ifndef ITK_MANUAL_INSTANTIATION -#include +# include #endif // ITK_MANUAL_INSTANTIATION -#endif // __FPA__BASE__DIJKSTRA__H__ +#endif // __fpa__Base__Dijkstra__h__ // eof - $RCSfile$