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 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 VC, class B >
33 typedef Algorithm Self;
35 typedef itk::SmartPointer< Self > Pointer;
36 typedef itk::SmartPointer< const Self > ConstPointer;
41 typedef VC TVertexCompare;
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 );
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;
83 typedef std::map< TVertex, _TNode, TVertexCompare > _TNodes;
86 typedef fpa::Base::MinimumSpanningTree< TVertex, _TCollisions, TVertexCompare > TMinimumSpanningTree;
89 itkTypeMacro( Algorithm, B );
91 itkBooleanMacro( ThrowEvents );
92 itkBooleanMacro( StopAtOneFront );
94 itkGetConstMacro( ThrowEvents, bool );
95 itkGetConstMacro( StopAtOneFront, bool );
97 itkSetMacro( ThrowEvents, bool );
98 itkSetMacro( StopAtOneFront, bool );
101 TMinimumSpanningTree* GetMinimumSpanningTree( );
102 const TMinimumSpanningTree* GetMinimumSpanningTree( ) const;
103 void GraftMinimumSpanningTree( itk::DataObject* obj );
105 virtual void InvokeEvent( const itk::EventObject& e );
106 virtual void InvokeEvent( const itk::EventObject& e ) const;
108 void AddSeed( const TVertex& s, const TResult& r );
109 const TVertex& GetSeed( const unsigned int& id ) const;
111 unsigned long GetNumberOfSeeds( ) const;
115 virtual ~Algorithm( );
117 // Connection with itk's pipeline
118 virtual void GenerateData( );
120 // Main loop algorithm
121 virtual void _Loop( );
123 // Supporting methods for loop
124 virtual void _BeforeGenerateData( );
125 virtual void _AfterGenerateData( );
126 virtual void _BeforeLoop( );
127 virtual void _AfterLoop( );
129 // Methods to control forced stops
130 virtual bool _UpdateCollisions( const TVertex& a, const TVertex& b );
131 virtual bool _NeedToStop( ) const;
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
139 virtual bool _HasEdge( const TVertex& a, const TVertex& b ) const = 0;
140 virtual void _Neighborhood(
141 _TVertices& neighborhood, const TVertex& v
144 // Results-related abstract methods
145 virtual bool _ComputeNeighborResult(
146 TResult& result, const TVertex& neighbor, const TVertex& parent
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;
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 );
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;
166 // Purposely not implemented
167 Algorithm( const Self& other );
168 Self& operator=( const Self& other );
172 bool m_StopAtOneFront;
174 _TVertices m_SeedVertices;
176 _TCollisions m_Collisions;
178 unsigned int m_MinimumSpanningTreeIndex;
185 #include <fpa/Base/Algorithm.hxx>
187 #endif // __FPA__BASE__ALGORITHM__H__