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