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      */
  13     template< class V, class C, class VV, class VC >
  14     class DijkstraTraits
  15     {
  16     public:
  17       typedef V TVertex;
  18       typedef C TResult;
  19       typedef C TCost;
  20       typedef VV TVertexValue;
  21       typedef VC TVertexCmp;
  22       typedef long TFrontId;
  23
  24       class TNode
  25       {
  26       public:
  27         TNode( )
  28           : Cost( 0 )
  29           { }
  30         TNode( const TVertex& v, const TFrontId& f )
  31           : Vertex( v ),
  32             Parent( v ),
  33             Result( TResult( 0 ) ),
  34             FrontId( f ),
  35             Cost( TCost( 0 ) )
  36           { }
  37         TNode( const TVertex& v, const TResult& r, const TFrontId& f )
  38           : Vertex( v ),
  39             Parent( v ),
  40             Result( r ),
  41             FrontId( f ),
  42             Cost( TCost( 0 ) )
  43           { }
  44         virtual ~TNode( )
  45           { }
  46
  47         // NOTE: stl::heaps work as maximum priority queues
  48         bool operator<( const TNode& other ) const
  49           { return( other.Cost < this->Cost ); }
  50
  51         TVertex Vertex;
  52         TVertex Parent;
  53         TResult Result;
  54         TFrontId FrontId;
  55         TCost Cost;
  56       };
  57
  58       typedef std::vector< TNode > TNodes;
  59     };
  60
  61     /**
  62      * Dijkstra is a front propagation algorithm that minimizes costs
  63      */
  64     template< class V, class C, class VV, class VC, class B >
  65     class Dijkstra
  66       : public Algorithm< DijkstraTraits< V, C, VV, VC >, B >
  67     {
  68     public:
  69       // Templated types
  70       typedef V TVertex;
  71       typedef C TCost;
  72       typedef VV TVertexValue;
  73       typedef B  TBaseFilter;
  74       typedef DijkstraTraits< V, C, VV, VC > TTraits;
  75
  76       // Standard class typdedefs
  77       typedef Dijkstra                        Self;
  78       typedef Algorithm< TTraits, B >         Superclass;
  79       typedef itk::SmartPointer< Self >       Pointer;
  80       typedef itk::SmartPointer< const Self > ConstPointer;
  81
  82     protected:
  83       typedef typename TTraits::TFrontId  _TFrontId;
  84       typedef typename TTraits::TNode     _TNode;
  85       typedef typename TTraits::TNodes    _TNodes;
  86
  87       typedef std::vector< _TNode > _TQueue;
  88
  89     public:
  90       itkTypeMacro( Dijkstra, Base );
  91
  92     protected:
  93       Dijkstra( );
  94       virtual ~Dijkstra( );
  95
  96       virtual   void _InitializeQueue ( );
  97       virtual   bool _IsQueueEmpty    ( ) const;
  98       virtual   void _QueuePush       ( const _TNode& n );
  99       virtual _TNode _QueuePop        ( );
 100       virtual   void _QueueClear      ( );
 101       virtual   bool _UpdateNeigh     ( _TNode& nn, const _TNode& n );
 102
 103     private:
 104       // Purposely not implemented
 105       Dijkstra( const Self& );
 106       void operator=( const Self& );
 107
 108     private:
 109       _TQueue m_Queue;
 110     };
 111
 112   } // ecapseman
 113
 114 } // ecapseman
 115
 116 #include <fpa/Base/Dijkstra.hxx>
 117
 118 #endif // __FPA__BASE__DIJKSTRA__H__
 119
 120 // eof - $RCSfile$