1 #ifndef __FPA__BASE__ALGORITHM__H__
2 #define __FPA__BASE__ALGORITHM__H__
7 #include <fpa/Base/Events.h>
8 #include <fpa/Base/MinimumSpanningTree.h>
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"
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).
29 template< class V, class C, class R, class S, class VC, class B >
34 typedef Algorithm Self;
36 typedef itk::SmartPointer< Self > Pointer;
37 typedef itk::SmartPointer< const Self > ConstPointer;
43 typedef VC TVertexCompare;
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 );
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;
85 typedef std::map< TVertex, _TNode, TVertexCompare > _TNodes;
88 typedef fpa::Base::MinimumSpanningTree< TVertex, _TCollisions, TVertexCompare > TMinimumSpanningTree;
91 itkTypeMacro( Algorithm, B );
93 itkBooleanMacro( ThrowEvents );
94 itkBooleanMacro( StopAtOneFront );
96 itkGetConstMacro( ThrowEvents, bool );
97 itkGetConstMacro( StopAtOneFront, bool );
99 itkSetMacro( ThrowEvents, bool );
100 itkSetMacro( StopAtOneFront, bool );
103 TMinimumSpanningTree* GetMinimumSpanningTree( );
104 const TMinimumSpanningTree* GetMinimumSpanningTree( ) const;
105 void GraftMinimumSpanningTree( itk::DataObject* obj );
107 virtual void InvokeEvent( const itk::EventObject& e );
108 virtual void InvokeEvent( const itk::EventObject& e ) const;
110 void AddSeed( const TVertex& s, const TResult& r );
111 const TVertex& GetSeed( const unsigned int& id ) const;
113 unsigned long GetNumberOfSeeds( ) const;
117 virtual ~Algorithm( );
119 // Connection with itk's pipeline
120 virtual void GenerateData( );
122 // Main loop algorithm
123 virtual void _Loop( );
125 // Supporting methods for loop
126 virtual void _BeforeGenerateData( );
127 virtual void _AfterGenerateData( );
128 virtual void _BeforeLoop( );
129 virtual void _AfterLoop( );
131 // Methods to control forced stops
132 virtual bool _UpdateCollisions( const TVertex& a, const TVertex& b );
133 virtual bool _NeedToStop( ) const;
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
141 virtual bool _HasEdge( const TVertex& a, const TVertex& b ) const = 0;
142 virtual void _Neighborhood(
143 _TVertices& neighborhood, const TVertex& v
146 // Results-related abstract methods
147 virtual bool _ComputeNeighborResult(
148 TResult& result, const TVertex& neighbor, const TVertex& parent
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;
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 );
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;
168 // Purposely not implemented
169 Algorithm( const Self& other );
170 Self& operator=( const Self& other );
174 bool m_StopAtOneFront;
176 _TVertices m_SeedVertices;
178 _TCollisions m_Collisions;
180 unsigned int m_MinimumSpanningTreeIndex;
187 #include <fpa/Base/Algorithm.hxx>
189 #endif // __FPA__BASE__ALGORITHM__H__