X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FDijkstra.h;h=5633f221f5b3bddedda29ab40575c6bcba12f397;hb=86a6d5df2aa1aa5292a5fa851d98bfc13939bdf3;hp=e711f4f56c844cde21766d47a6c2e789683737a4;hpb=8fafb83c41ab35dfc25eb637170882a612924433;p=FrontAlgorithms.git diff --git a/lib/fpa/Base/Dijkstra.h b/lib/fpa/Base/Dijkstra.h index e711f4f..5633f22 100644 --- a/lib/fpa/Base/Dijkstra.h +++ b/lib/fpa/Base/Dijkstra.h @@ -1,120 +1,83 @@ -#ifndef __FPA__BASE__DIJKSTRA__H__ -#define __FPA__BASE__DIJKSTRA__H__ +#ifndef __fpa__Base__Dijkstra__h__ +#define __fpa__Base__Dijkstra__h__ #include -#include -#include +#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 _TSuperclass, class _TMST > class Dijkstra - : public Algorithm< V, C, R, S, VC, B > + : public _TSuperclass { 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 _TSuperclass Superclass; + typedef itk::SmartPointer< Self > Pointer; + typedef itk::SmartPointer< const Self > ConstPointer; + + typedef _TMST TMST; + typedef typename Superclass::TOutput TOutput; + typedef typename Superclass::TVertex TVertex; + + typedef itk::FunctionBase< TOutput, TOutput > TCostConversionFunction; + typedef DijkstraCostFunctionBase< TVertex, TOutput > TCostFunction; 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 + typedef typename Superclass::_TQueueNode _TQueueNode; + struct _TQueueNodeCompare { - 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 ); } + bool operator( )( const _TQueueNode& a, const _TQueueNode& b ) + { + return( b.Result < a.Result ); + } }; 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 ); + itkGetObjectMacro( CostFunction, TCostFunction ); + itkGetObjectMacro( CostConversionFunction, TCostConversionFunction ); + itkSetObjectMacro( CostFunction, TCostFunction ); + itkSetObjectMacro( CostConversionFunction, TCostConversionFunction ); public: - TMinimumSpanningTree* GetMinimumSpanningTree( ); - const TMinimumSpanningTree* GetMinimumSpanningTree( ) const; - void GraftMinimumSpanningTree( itk::DataObject* obj ); + _TMST* GetMinimumSpanningTree( ); + const _TMST* GetMinimumSpanningTree( ) const; protected: Dijkstra( ); virtual ~Dijkstra( ); - virtual TResult _Cost( const TVertex& v, const TVertex& p ) const = 0; + virtual void _AfterGenerateData( ) fpa_OVERRIDE; - 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 _UpdateResult( const _TQueueNode& n ) fpa_OVERRIDE; + virtual bool _UpdateValue( + _TQueueNode& v, const _TQueueNode& p + ) fpa_OVERRIDE; + virtual unsigned long _QueueSize( ) const fpa_OVERRIDE; + virtual void _QueueClear( ) fpa_OVERRIDE; + virtual void _QueuePush( const _TQueueNode& node ) fpa_OVERRIDE; + virtual _TQueueNode _QueuePop( ) fpa_OVERRIDE; private: - // Purposely not implemented + // Purposely not defined Dijkstra( const Self& other ); Self& operator=( const Self& other ); protected: - bool m_LocalCosts; - bool m_FillNodeQueue; _TQueue m_Queue; - unsigned int m_MSTIdx; + typename TCostFunction::Pointer m_CostFunction; + typename TCostConversionFunction::Pointer m_CostConversionFunction; + + unsigned long m_MSTIndex; }; } // ecapseman @@ -122,9 +85,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$