lib/fpa/Base/Dijkstra.h

   1 #ifndef __FPA__BASE__DIJKSTRA__H__
   2 #define __FPA__BASE__DIJKSTRA__H__
   3
   4 #include <vector>
   5 #include <fpa/Base/Algorithm.h>
   6 #include <fpa/Base/MinimumSpanningTree.h>
   7
   8 namespace fpa
   9 {
  10   namespace Base
  11   {
  12     /**
  13      * Dijkstra is a front propagation algorithm that minimizes costs
  14      *
  15      * @param V   Vertex type.
  16      * @param C   Vertex value type.
  17      * @param R   Result value type.
  18      * @param S   Space type where vertices are.
  19      * @param VC  Vertex lexicographical compare.
  20      * @param MST Minimum spanning tree type.
  21      * @param B   Base class for this algorithm. It should be any itk-based
  22      *            filter (itk::ProcessObject).
  23      *
  24      */
  25     template< class V, class C, class R, class S, class VC, class MST, class B >
  26     class Dijkstra
  27       : public Algorithm< V, C, R, S, VC, B >
  28     {
  29     public:
  30       typedef Dijkstra                         Self;
  31       typedef Algorithm< V, C, R, S, VC, B >   Superclass;
  32       typedef itk::SmartPointer< Self >        Pointer;
  33       typedef itk::SmartPointer< const Self >  ConstPointer;
  34
  35       typedef MST TMinimumSpanningTree;
  36       typedef typename Superclass::TVertex        TVertex;
  37       typedef typename Superclass::TValue         TValue;
  38       typedef typename Superclass::TResult        TResult;
  39       typedef typename Superclass::TSpace         TSpace;
  40       typedef typename Superclass::TVertexCompare TVertexCompare;
  41
  42       typedef typename Superclass::TStartEvent     TStartEvent;
  43       typedef typename Superclass::TStartLoopEvent TStartLoopEvent;
  44       typedef typename Superclass::TEndEvent       TEndEvent;
  45       typedef typename Superclass::TEndLoopEvent   TEndLoopEvent;
  46       typedef typename Superclass::TAliveEvent     TAliveEvent;
  47       typedef typename Superclass::TFrontEvent     TFrontEvent;
  48       typedef typename Superclass::TFreezeEvent    TFreezeEvent;
  49
  50       typedef typename Superclass::TStartBacktrackingEvent TStartBacktrackingEvent;
  51       typedef typename Superclass::TEndBacktrackingEvent TEndBacktrackingEvent;
  52       typedef typename Superclass::TBacktrackingEvent TBacktrackingEvent;
  53
  54     protected:
  55       typedef typename Superclass::_TVertices      _TVertices;
  56       typedef typename Superclass::_TCollision     _TCollision;
  57       typedef typename Superclass::_TCollisionsRow _TCollisionsRow;
  58       typedef typename Superclass::_TCollisions    _TCollisions;
  59       typedef typename Superclass::_TNode          _TNode;
  60       typedef typename Superclass::_TNodes         _TNodes;
  61
  62       struct _TQueueNode
  63       {
  64         TVertex Vertex;
  65         _TNode  Node;
  66
  67         // Make the min-heap behave as a max-heap
  68         bool operator<( const _TQueueNode& other ) const
  69           { return( other.Node.Result < this->Node.Result ); }
  70       };
  71       typedef std::vector< _TQueueNode > _TQueue;
  72
  73     public:
  74       itkTypeMacro( Dijkstra, Algorithm );
  75
  76       itkBooleanMacro( LocalCosts );
  77       itkBooleanMacro( FillNodeQueue );
  78       itkGetConstMacro( LocalCosts, bool );
  79       itkGetConstMacro( FillNodeQueue, bool );
  80       itkSetMacro( LocalCosts, bool );
  81       itkSetMacro( FillNodeQueue, bool );
  82
  83     public:
  84       TMinimumSpanningTree* GetMinimumSpanningTree( );
  85       const TMinimumSpanningTree* GetMinimumSpanningTree( ) const;
  86       void GraftMinimumSpanningTree( itk::DataObject* obj );
  87
  88     protected:
  89       Dijkstra( );
  90       virtual ~Dijkstra( );
  91
  92       virtual TResult _Cost( const TVertex& v, const TVertex& p ) const = 0;
  93
  94       virtual void _BeforeGenerateData( ) ITK_OVERRIDE;
  95
  96       // Results-related abstract methods
  97       virtual bool _ComputeNeighborResult(
  98         TResult& result, const TVertex& neighbor, const TVertex& parent
  99         ) const ITK_OVERRIDE;
 100       virtual void _SetResult( const TVertex& v, const _TNode& n ) ITK_OVERRIDE;
 101
 102       // Queue-related abstract methods
 103       virtual bool _IsQueueEmpty( ) const ITK_OVERRIDE;
 104       virtual void _QueuePush( const TVertex& v, const _TNode& n ) ITK_OVERRIDE;
 105       virtual void _QueuePop( TVertex& v, _TNode& n ) ITK_OVERRIDE;
 106       virtual void _QueueClear( ) ITK_OVERRIDE;
 107
 108     private:
 109       // Purposely not implemented
 110       Dijkstra( const Self& other );
 111       Self& operator=( const Self& other );
 112
 113     protected:
 114       bool m_LocalCosts;
 115       bool m_FillNodeQueue;
 116       _TQueue m_Queue;
 117       unsigned int m_MSTIdx;
 118     };
 119
 120   } // ecapseman
 121
 122 } // ecapseman
 123
 124 #ifndef ITK_MANUAL_INSTANTIATION
 125 #include <fpa/Base/Dijkstra.hxx>
 126 #endif // ITK_MANUAL_INSTANTIATION
 127
 128 #endif // __FPA__BASE__DIJKSTRA__H__
 129
 130 // eof - $RCSfile$