1 #ifndef __FPA__BASE__ALGORITHM__H__
2 #define __FPA__BASE__ALGORITHM__H__
7 #include <fpa/Base/Events.h>
14 * Base front propagation algorithm. From a series of start seeds with
15 * costs, a priority queue is filled and emptied updating costs. Each
16 * vertex could be marked as "visited", "in the front", "not yet there"
19 * @param V Vertex type.
20 * @param C Vertex value type.
21 * @param R Result value type.
22 * @param S Space type where vertices are.
23 * @param VC Vertex lexicographical compare.
24 * @param B Base class for this algorithm. It should be any itk-based
25 * filter (itk::ProcessObject).
28 template< class V, class C, class R, class S, class VC, class B >
33 typedef Algorithm Self;
35 typedef itk::SmartPointer< Self > Pointer;
36 typedef itk::SmartPointer< const Self > ConstPointer;
42 typedef VC TVertexCompare;
44 fpa_Base_NewEvent( TStartEvent );
45 fpa_Base_NewEvent( TStartLoopEvent );
46 fpa_Base_NewEvent( TStartBacktrackingEvent );
47 fpa_Base_NewEvent( TEndEvent );
48 fpa_Base_NewEvent( TEndLoopEvent );
49 fpa_Base_NewEvent( TEndBacktrackingEvent );
50 fpa_Base_NewEventWithVertex( TAliveEvent, TVertex );
51 fpa_Base_NewEventWithVertex( TFrontEvent, TVertex );
52 fpa_Base_NewEventWithVertex( TFreezeEvent, TVertex );
53 fpa_Base_NewEventWithVertex( TBacktrackingEvent, TVertex );
56 typedef std::vector< TVertex > _TVertices;
57 typedef std::pair< TVertex, bool > _TCollision;
58 typedef std::vector< _TCollision > _TCollisionsRow;
59 typedef std::vector< _TCollisionsRow > _TCollisions;
84 typedef std::map< TVertex, _TNode, TVertexCompare > _TNodes;
87 itkTypeMacro( Algorithm, B );
89 itkBooleanMacro( ThrowEvents );
90 itkBooleanMacro( StopAtOneFront );
92 itkGetConstMacro( ThrowEvents, bool );
93 itkGetConstMacro( StopAtOneFront, bool );
95 itkSetMacro( ThrowEvents, bool );
96 itkSetMacro( StopAtOneFront, bool );
99 virtual void InvokeEvent( const itk::EventObject& e );
100 virtual void InvokeEvent( const itk::EventObject& e ) const;
102 void AddSeed( const TVertex& s, const TResult& r );
103 const TVertex& GetSeed( const unsigned int& id ) const;
105 unsigned long GetNumberOfSeeds( ) const;
109 virtual ~Algorithm( );
111 // Connection with itk's pipeline
112 virtual void GenerateData( ) ITK_OVERRIDE;
114 // Main loop algorithm
115 virtual void _Loop( );
117 // Supporting methods for loop
118 virtual void _BeforeGenerateData( );
119 virtual void _AfterGenerateData( );
120 virtual void _BeforeLoop( );
121 virtual void _AfterLoop( );
123 // Methods to control forced stops
124 virtual bool _UpdateCollisions( const TVertex& a, const TVertex& b );
125 virtual bool _NeedToStop( ) const;
127 // Graph-related abstract methods
128 virtual unsigned long _NumberOfVertices( ) const = 0;
129 virtual const TValue& _VertexValue( const TVertex& v ) const = 0;
130 virtual double _Distance(
131 const TVertex& a, const TVertex& b
133 virtual bool _HasEdge( const TVertex& a, const TVertex& b ) const = 0;
134 virtual void _Neighborhood(
135 _TVertices& neighborhood, const TVertex& v
138 // Results-related abstract methods
139 virtual bool _ComputeNeighborResult(
140 TResult& result, const TVertex& neighbor, const TVertex& parent
142 virtual void _InitResults( ) = 0;
143 virtual const TResult& _Result( const TVertex& v ) const = 0;
144 virtual void _SetResult( const TVertex& v, const _TNode& n );
146 // Marks-related abstract methods
147 virtual _TNode& _Node( const TVertex& v );
148 virtual const _TNode& _Node( const TVertex& v ) const;
149 virtual void _InitMarks( );
150 virtual void _Mark( const TVertex& v, const _TNode& node );
152 // Queue-related abstract methods
153 virtual void _InitQueue( );
154 virtual bool _IsQueueEmpty( ) const = 0;
155 virtual void _QueuePush( const TVertex& v, const _TNode& n ) = 0;
156 virtual void _QueuePop( TVertex& v, _TNode& n ) = 0;
157 virtual void _QueueClear( ) = 0;
160 // Purposely not implemented
161 Algorithm( const Self& other );
162 Self& operator=( const Self& other );
166 bool m_StopAtOneFront;
168 _TVertices m_SeedVertices;
170 _TCollisions m_Collisions;
177 #ifndef ITK_MANUAL_INSTANTIATION
178 #include <fpa/Base/Algorithm.hxx>
179 #endif // ITK_MANUAL_INSTANTIATION
181 #endif // __FPA__BASE__ALGORITHM__H__