lib/fpa/Base/Algorithm.h

   1 #ifndef __FPA__BASE__ALGORITHM__H__
   2 #define __FPA__BASE__ALGORITHM__H__
   3
   4 #include <utility>
   5 #include <vector>
   6 #include <fpa/Base/Events.h>
   7
   8 namespace fpa
   9 {
  10   namespace Base
  11   {
  12     /**
  13      * Base front propagation algorithm. From a series of start seeds with
  14      * costs, a priority queue is filled and emptied updating costs. Each
  15      * vertex could be marked as "visited", "in the front", "not yet there"
  16      * or "freezed".
  17      *
  18      * @param V Vertex type.
  19      * @param C Vertex value type.
  20      * @param R Result value 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 B >
  26     class Algorithm
  27       : public B
  28     {
  29     public:
  30       typedef Algorithm                       Self;
  31       typedef B                               Superclass;
  32       typedef itk::SmartPointer< Self >       Pointer;
  33       typedef itk::SmartPointer< const Self > ConstPointer;
  34
  35       typedef V TVertex;
  36       typedef C TValue;
  37       typedef R TResult;
  38
  39       fpa_Base_NewEvent( TStartEvent );
  40       fpa_Base_NewEvent( TStartLoopEvent );
  41       fpa_Base_NewEvent( TEndEvent );
  42       fpa_Base_NewEvent( TEndLoopEvent );
  43       fpa_Base_NewEventWithVertex( TAliveEvent, TVertex );
  44       fpa_Base_NewEventWithVertex( TFrontEvent, TVertex );
  45       fpa_Base_NewEventWithVertex( TFreezeEvent, TVertex );
  46
  47     protected:
  48       typedef std::vector< TVertex >         _TVertices;
  49       typedef std::pair< TVertex, bool >     _TCollision;
  50       typedef std::vector< _TCollision >     _TCollisionsRow;
  51       typedef std::vector< _TCollisionsRow > _TCollisions;
  52
  53       /**
  54        */
  55       enum _TNodeLabel
  56       {
  57         FarLabel = 0,
  58         FrontLabel,
  59         AliveLabel
  60       };
  61
  62       /**
  63        */
  64       class _TNode
  65       {
  66       public:
  67         _TNode( );
  68         virtual ~_TNode( );
  69
  70       public:
  71         TVertex     Vertex;
  72         TVertex     Parent;
  73         TResult     Result;
  74         long        FrontId;
  75         _TNodeLabel Label;
  76       };
  77       typedef std::vector< _TNode > _TNodes;
  78
  79     public:
  80       itkTypeMacro( Algorithm, B );
  81
  82       itkBooleanMacro( ThrowEvents );
  83       itkBooleanMacro( StopAtOneFront );
  84
  85       itkGetConstMacro( ThrowEvents, bool );
  86       itkGetConstMacro( StopAtOneFront, bool );
  87
  88       itkSetMacro( ThrowEvents, bool );
  89       itkSetMacro( StopAtOneFront, bool );
  90
  91     public:
  92       virtual void InvokeEvent( const itk::EventObject& e );
  93       virtual void InvokeEvent( const itk::EventObject& e ) const;
  94
  95       void AddSeed( const TVertex& s, const TResult& r );
  96       const TVertex& GetSeed( const unsigned int& id ) const;
  97       void ClearSeeds( );
  98       unsigned long GetNumberOfSeeds( ) const;
  99
 100     protected:
 101       Algorithm( );
 102       virtual ~Algorithm( );
 103
 104       // Connection with itk's pipeline
 105       virtual void GenerateData( );
 106
 107       // Main loop algorithm
 108       virtual void _Loop( );
 109
 110       // Supporting methods for loop
 111       virtual void _BeforeGenerateData( );
 112       virtual void _AfterGenerateData( );
 113       virtual void _BeforeLoop( );
 114       virtual void _AfterLoop( );
 115
 116       // Methods to control forced stops
 117       virtual bool _UpdateCollisions( const TVertex& a, const TVertex& b );
 118       virtual bool _NeedToStop( ) const;
 119
 120       // Graph-related abstract methods
 121       virtual unsigned long _NumberOfVertices( ) const = 0;
 122       virtual const TValue& _VertexValue( const TVertex& v ) const = 0;
 123       virtual double _Distance(
 124         const TVertex& a, const TVertex& b
 125         ) const = 0;
 126       virtual bool _HasEdge( const TVertex& a, const TVertex& b ) const = 0;
 127       virtual void _Neighborhood(
 128         _TVertices& neighborhood, const TVertex& v
 129         ) const = 0;
 130
 131       // Results-related abstract methods
 132       virtual bool _ComputeNeighborResult(
 133         TResult& result, const TVertex& neighbor, const TVertex& parent
 134         ) const = 0;
 135       virtual void _InitResults( ) = 0;
 136       virtual const TResult& _Result( const TVertex& v ) const = 0;
 137       virtual void _SetResult( const TVertex& v, const TResult& r ) = 0;
 138
 139       // Marks-related abstract methods
 140       virtual const _TNode& _Node( const TVertex& v ) const = 0;
 141       virtual void _InitMarks( ) = 0;
 142       virtual void _Mark( const _TNode& node ) = 0;
 143
 144       // Queue-related abstract methods
 145       virtual void _InitQueue( );
 146       virtual bool _IsQueueEmpty( ) const = 0;
 147       virtual void _QueuePush( const _TNode& n ) = 0;
 148       virtual _TNode _QueuePop( ) = 0;
 149       virtual void _QueueClear( ) = 0;
 150
 151     private:
 152       // Purposely not implemented
 153       Algorithm( const Self& other );
 154       Self& operator=( const Self& other );
 155
 156     protected:
 157       bool         m_ThrowEvents;
 158       bool         m_StopAtOneFront;
 159       _TNodes      m_Seeds;
 160       _TCollisions m_Collisions;
 161     };
 162
 163   } // ecapseman
 164
 165 } // ecapseman
 166
 167 #include <fpa/Base/Algorithm.hxx>
 168
 169 #endif // __FPA__BASE__ALGORITHM__H__
 170
 171 // eof - $RCSfile$