lib/fpa/Base/Dijkstra.h

   1 #ifndef __FPA__BASE__DIJKSTRA__H__
   2 #define __FPA__BASE__DIJKSTRA__H__
   3
   4 #include <vector>
   5 #include <itkFunctionBase.h>
   6 #include <fpa/Base/Algorithm.h>
   7 #include <fpa/Base/MinimumSpanningTree.h>
   8
   9 namespace fpa
  10 {
  11   namespace Base
  12   {
  13     /**
  14      */
  15     template< class _TSuperclass >
  16     class Dijkstra
  17       : public _TSuperclass
  18     {
  19     public:
  20       typedef Dijkstra                        Self;
  21       typedef _TSuperclass                    Superclass;
  22       typedef itk::SmartPointer< Self >       Pointer;
  23       typedef itk::SmartPointer< const Self > ConstPointer;
  24
  25       // Template arguments
  26       typedef typename Superclass::TVertex        TVertex;
  27       typedef typename Superclass::TScalar        TScalar;
  28       typedef typename Superclass::TFilter        TFilter;
  29       typedef typename Superclass::TVertexCompare TVertexCompare;
  30       typedef typename Superclass::TFrontId       TFrontId;
  31       typedef typename Superclass::TCollision     TCollision;
  32       typedef typename Superclass::TCollisionsRow TCollisionsRow;
  33       typedef typename Superclass::TCollisions    TCollisions;
  34       typedef typename Superclass::TNodeLabel     TNodeLabel;
  35       typedef typename Superclass::TNode          TNode;
  36       typedef typename Superclass::TNodes         TNodes;
  37       typedef typename Superclass::TVertices      TVertices;
  38
  39       typedef itk::FunctionBase< TScalar, TScalar > TCostConversionFunction;
  40
  41       typedef
  42       fpa::Base::MinimumSpanningTree< TVertex, TScalar, TVertexCompare >
  43       TMinimumSpanningTree;
  44
  45       struct TDijkstraCmp
  46       {
  47         bool operator()( const TNode& a, const TNode& b )
  48           { return( b.Result < a.Result ); }
  49       };
  50       static const TDijkstraCmp DijkstraCmp;
  51
  52     public:
  53       itkTypeMacro( Dijkstra, Algorithm );
  54
  55       itkGetObjectMacro( CostConversionFunction, TCostConversionFunction );
  56       itkSetObjectMacro( CostConversionFunction, TCostConversionFunction );
  57
  58     public:
  59       TMinimumSpanningTree* GetMinimumSpanningTree( );
  60       const TMinimumSpanningTree* GetMinimumSpanningTree( ) const;
  61       void GraftMinimumSpanningTree( itk::DataObject* obj );
  62
  63     protected:
  64       // Methods to extend itk-based architecture
  65       Dijkstra( );
  66       virtual ~Dijkstra( );
  67
  68       // Front propagation methods to be overloaded
  69       virtual void _AfterGenerateData( ) fpa_OVERRIDE;
  70       virtual void _Visit( const TNode& n ) fpa_OVERRIDE;
  71       virtual bool _Result( TNode& node, const TNode& parent ) fpa_OVERRIDE;
  72       virtual void  _QueueClear( ) fpa_OVERRIDE;
  73       virtual void  _QueuePush( const TNode& node ) fpa_OVERRIDE;
  74       virtual TNode _QueuePop( ) fpa_OVERRIDE;
  75       virtual bool  _IsQueueEmpty( ) const fpa_OVERRIDE;
  76
  77       // Dijkstra methods to be overloaded
  78       virtual TScalar _Cost( const TVertex& a, const TVertex& b ) const = 0;
  79
  80     private:
  81       // Purposely not implemented
  82       Dijkstra( const Self& other );
  83       Self& operator=( const Self& other );
  84
  85     protected:
  86       unsigned int m_MSTIdx;
  87       std::vector< TNode > m_Queue;
  88       typename TCostConversionFunction::Pointer m_CostConversionFunction;
  89     };
  90
  91   } // ecapseman
  92
  93 } // ecapseman
  94
  95 #ifndef ITK_MANUAL_INSTANTIATION
  96 #  include <fpa/Base/Dijkstra.hxx>
  97 #endif
  98
  99 #endif // __FPA__BASE__DIJKSTRA__H__
 100
 101 // eof - $RCSfile$