lib/fpa/Base/Algorithm.h

   1 #ifndef __FPA__BASE__ALGORITHM__H__
   2 #define __FPA__BASE__ALGORITHM__H__
   3
   4 #include <functional>
   5 #include <set>
   6 #include <utility>
   7 #include <vector>
   8 #include <fpa/Config.h>
   9 #include <fpa/Base/Events.h>
  10
  11 namespace fpa
  12 {
  13   namespace Base
  14   {
  15     /**
  16      * Base front propagation algorithm. From a series of start seeds with
  17      * costs, a priority queue is filled and emptied updating costs. Each
  18      * vertex could be marked as "visited", "in the front", "not yet there"
  19      * or "freezed".
  20      *
  21      * @param _TVertex Vertex type.
  22      * @param _TScalar Scalar (real computations) type.
  23      * @param _TFilter Base class for this algorithm. It should be any
  24      *                 itk-based filter (itk::ProcessObject).
  25      * @param _TVertexCompare Vertex lexicographical compare.
  26      *
  27      */
  28     template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare = std::less< _TVertex > >
  29     class Algorithm
  30       : public _TFilter
  31     {
  32     public:
  33       typedef Algorithm                       Self;
  34       typedef _TFilter                        Superclass;
  35       typedef itk::SmartPointer< Self >       Pointer;
  36       typedef itk::SmartPointer< const Self > ConstPointer;
  37
  38       // Template arguments
  39       typedef _TVertex        TVertex;
  40       typedef _TScalar        TScalar;
  41       typedef _TFilter        TFilter;
  42       typedef _TVertexCompare TVertexCompare;
  43
  44       // Some useful types
  45       typedef unsigned long TFrontId;
  46
  47       // Minigraph to represent collisions
  48       typedef std::pair< TVertex, bool >    TCollision;
  49       typedef std::vector< TCollision >     TCollisionsRow;
  50       typedef std::vector< TCollisionsRow > TCollisions;
  51
  52       enum TNodeLabel
  53       {
  54         FarLabel = 0,
  55         FrontLabel,
  56         AliveLabel
  57       };
  58
  59       /**
  60        * WARNING: std::set< T > objects are immutable
  61        */
  62       struct TNode
  63       {
  64         static const TVertexCompare VertexCompare;
  65         TVertex            Vertex;
  66         mutable TVertex    Parent;
  67         mutable TScalar    Result;
  68         mutable TFrontId   FrontId;
  69         mutable TNodeLabel Label;
  70         bool operator<( const TNode& other ) const
  71           { return( VertexCompare( this->Vertex, other.Vertex ) ); }
  72       };
  73       typedef std::set< TNode >      TNodes;
  74       typedef std::vector< TVertex > TVertices;
  75
  76     public:
  77       itkTypeMacro( Algorithm, _TFilter );
  78
  79       itkBooleanMacro( StopAtOneFront );
  80       itkGetConstMacro( StopAtOneFront, bool );
  81       itkSetMacro( StopAtOneFront, bool );
  82
  83       itkBooleanMacro( ThrowEvents );
  84       itkGetConstMacro( ThrowEvents, bool );
  85       itkSetMacro( ThrowEvents, bool );
  86
  87       fpa_Base_NewEvent( TStartEvent );
  88       fpa_Base_NewEvent( TStartLoopEvent );
  89       fpa_Base_NewEvent( TStartBacktrackingEvent );
  90       fpa_Base_NewEvent( TEndEvent );
  91       fpa_Base_NewEvent( TEndLoopEvent );
  92       fpa_Base_NewEvent( TEndBacktrackingEvent );
  93       fpa_Base_NewEventWithVertex( TCollisionEvent, TVertex );
  94       fpa_Base_NewEventWithVertex( TAliveEvent, TVertex );
  95       fpa_Base_NewEventWithVertex( TFrontEvent, TVertex );
  96       fpa_Base_NewEventWithVertex( TFreezeEvent, TVertex );
  97       fpa_Base_NewEventWithVertex( TBacktrackingEvent, TVertex );
  98
  99     public:
 100       virtual void InvokeEvent( const itk::EventObject& e );
 101       virtual void InvokeEvent( const itk::EventObject& e ) const;
 102
 103       unsigned long GetNumberOfSeeds( ) const;
 104       void AddSeed( const TVertex& s, const TScalar& v = TScalar( 0 ) );
 105       void AddSeed( const TNode& n );
 106       void RemoveSeed( const TVertex& s );
 107       void RemoveAllSeeds( );
 108
 109     protected:
 110       // Methods to extend itk-based architecture
 111       Algorithm( );
 112       virtual ~Algorithm( );
 113       virtual void GenerateData( ) fpa_OVERRIDE;
 114
 115       // Front propagation generic methods
 116       virtual void _Loop( );
 117
 118       // Front propagation methods to be overloaded
 119       virtual void _BeforeGenerateData( );
 120       virtual void _AfterGenerateData( );
 121       virtual void _BeforeLoop( );
 122       virtual void _AfterLoop( );
 123
 124       virtual void _InitMarks( ) = 0;
 125       virtual void _InitResults( ) = 0;
 126       virtual void _DeallocateAuxiliary( ) = 0;
 127
 128       virtual TFrontId _GetMark( const TVertex& v ) = 0;
 129       virtual TFrontId _GetMark( const TNode& v );
 130
 131       virtual void _Visit( const TNode& n ) = 0;
 132       virtual bool _NeedToStop( );
 133
 134       virtual TVertices _GetNeighborhood( const TVertex& v ) const = 0;
 135       virtual TVertices _GetNeighborhood( const TNode& n ) const;
 136
 137       virtual bool _Result( TNode& node, const TNode& parent ) = 0;
 138
 139       virtual void  _QueueClear( ) = 0;
 140       virtual void  _QueuePush( const TNode& node ) = 0;
 141       virtual TNode _QueuePop( ) = 0;
 142       virtual bool  _IsQueueEmpty( ) const = 0;
 143
 144       virtual bool _UpdateCollisions( const TVertex& a, const TVertex& b );
 145
 146     private:
 147       // Purposely not implemented
 148       Algorithm( const Self& other );
 149       Self& operator=( const Self& other );
 150
 151     protected:
 152       TNodes      m_Seeds;
 153       TCollisions m_Collisions;
 154       bool        m_StopAtOneFront;
 155       bool        m_ThrowEvents;
 156     };
 157
 158   } // ecapseman
 159
 160 } // ecapseman
 161
 162 #ifndef ITK_MANUAL_INSTANTIATION
 163 #  include <fpa/Base/Algorithm.hxx>
 164 #endif
 165
 166 #endif // __FPA__BASE__ALGORITHM__H__
 167
 168 // eof - $RCSfile$