lib/fpa/Base/Algorithm.h

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