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