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