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
  89       fpa::Base::MinimumSpanningTree< V, _TCollisions, VC >
  90       TMinimumSpanningTree;
  91
  92     public:
  93       itkTypeMacro( Algorithm, B );
  94
  95       itkBooleanMacro( ThrowEvents );
  96       itkBooleanMacro( StopAtOneFront );
  97
  98       itkGetConstMacro( ThrowEvents, bool );
  99       itkGetConstMacro( StopAtOneFront, bool );
 100
 101       itkSetMacro( ThrowEvents, bool );
 102       itkSetMacro( StopAtOneFront, bool );
 103
 104     public:
 105       TMinimumSpanningTree* GetMinimumSpanningTree( );
 106       const TMinimumSpanningTree* GetMinimumSpanningTree( ) const;
 107       void GraftMinimumSpanningTree( itk::DataObject* obj );
 108
 109       virtual void InvokeEvent( const itk::EventObject& e );
 110       virtual void InvokeEvent( const itk::EventObject& e ) const;
 111
 112       void AddSeed( const TVertex& s, const TResult& r );
 113       const TVertex& GetSeed( const unsigned int& id ) const;
 114       void ClearSeeds( );
 115       unsigned long GetNumberOfSeeds( ) const;
 116
 117     protected:
 118       Algorithm( );
 119       virtual ~Algorithm( );
 120
 121       // Connection with itk's pipeline
 122       virtual void GenerateData( );
 123
 124       // Main loop algorithm
 125       virtual void _Loop( );
 126
 127       // Supporting methods for loop
 128       virtual void _BeforeGenerateData( );
 129       virtual void _AfterGenerateData( );
 130       virtual void _BeforeLoop( );
 131       virtual void _AfterLoop( );
 132
 133       // Methods to control forced stops
 134       virtual bool _UpdateCollisions( const TVertex& a, const TVertex& b );
 135       virtual bool _NeedToStop( ) const;
 136
 137       // Graph-related abstract methods
 138       virtual unsigned long _NumberOfVertices( ) const = 0;
 139       virtual const TValue& _VertexValue( const TVertex& v ) const = 0;
 140       virtual double _Distance(
 141         const TVertex& a, const TVertex& b
 142         ) const = 0;
 143       virtual bool _HasEdge( const TVertex& a, const TVertex& b ) const = 0;
 144       virtual void _Neighborhood(
 145         _TVertices& neighborhood, const TVertex& v
 146         ) const = 0;
 147
 148       // Results-related abstract methods
 149       virtual bool _ComputeNeighborResult(
 150         TResult& result, const TVertex& neighbor, const TVertex& parent
 151         ) const = 0;
 152       virtual void _InitResults( ) = 0;
 153       virtual const TResult& _Result( const TVertex& v ) const = 0;
 154       virtual void _SetResult( const TVertex& v, const _TNode& n ) = 0;
 155
 156       // Marks-related abstract methods
 157       virtual _TNode& _Node( const TVertex& v );
 158       virtual const _TNode& _Node( const TVertex& v ) const;
 159       virtual void _InitMarks( );
 160       virtual void _Mark( const TVertex& v, const _TNode& node );
 161
 162       // Queue-related abstract methods
 163       virtual void _InitQueue( );
 164       virtual bool _IsQueueEmpty( ) const = 0;
 165       virtual void _QueuePush( const TVertex& v, const _TNode& n ) = 0;
 166       virtual void _QueuePop( TVertex& v, _TNode& n ) = 0;
 167       virtual void _QueueClear( ) = 0;
 168
 169     private:
 170       // Purposely not implemented
 171       Algorithm( const Self& other );
 172       Self& operator=( const Self& other );
 173
 174     protected:
 175       bool         m_ThrowEvents;
 176       bool         m_StopAtOneFront;
 177       _TNodes      m_Seeds;
 178       _TVertices   m_SeedVertices;
 179       _TNodes      m_Marks;
 180       _TCollisions m_Collisions;
 181
 182       unsigned int m_MinimumSpanningTreeIndex;
 183     };
 184
 185   } // ecapseman
 186
 187 } // ecapseman
 188
 189 #include <fpa/Base/Algorithm.hxx>
 190
 191 #endif // __FPA__BASE__ALGORITHM__H__
 192
 193 // eof - $RCSfile$