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 T Traits used for this algorithm
21 template< class T, class B >
26 // Standard class typdedefs
27 typedef Algorithm Self;
29 typedef itk::SmartPointer< Self > Pointer;
30 typedef itk::SmartPointer< const Self > ConstPointer;
34 typedef B TBaseFilter;
35 typedef typename T::TCost TCost;
36 typedef typename T::TResult TResult;
37 typedef typename T::TVertex TVertex;
38 typedef typename T::TVertexValue TVertexValue;
41 typedef typename T::TFrontId _TFrontId;
42 typedef typename T::TNode _TNode;
43 typedef typename T::TNodes _TNodes;
44 typedef typename T::TVertexCmp _TVertexCmp;
46 typedef std::map< TVertex, _TNode, _TVertexCmp > _TMarks;
48 typedef std::pair< TVertex, bool > _TCollision;
49 typedef std::vector< _TCollision > _TCollisionSitesRow;
50 typedef std::vector< _TCollisionSitesRow > _TCollisionSites;
53 typedef BaseEvent< _TNode > TEvent;
54 typedef FrontEvent< _TNode > TFrontEvent;
55 typedef MarkEvent< _TNode > TMarkEvent;
56 typedef CollisionEvent< _TNode > TCollisionEvent;
57 typedef EndEvent< _TNode > TEndEvent;
58 typedef BacktrackingEvent< TVertex > TBacktrackingEvent;
61 itkTypeMacro( Algorithm, itkProcessObject );
63 itkBooleanMacro( StopAtOneFront );
64 itkBooleanMacro( ThrowEvents );
66 itkGetConstMacro( StopAtOneFront, bool );
67 itkGetConstMacro( ThrowEvents, bool );
69 itkSetMacro( StopAtOneFront, bool );
70 itkSetMacro( ThrowEvents, bool );
73 virtual void InvokeEvent( const itk::EventObject& e );
74 virtual void InvokeEvent( const itk::EventObject& e ) const;
76 /// Seeds manipulation
77 void AddSeed( const TVertex& s, const TResult& v );
78 const TVertex& GetSeed( const unsigned long& i ) const;
80 unsigned long GetNumberOfSeeds( ) const;
84 virtual ~Algorithm( );
86 /// itk::ProcessObject
87 virtual void GenerateData( );
90 virtual void _BeforeMainLoop ( );
91 virtual void _AfterMainLoop ( );
92 virtual void _BeforeLoop ( );
93 virtual void _AfterLoop ( );
94 virtual void _Loop ( );
95 virtual bool _CheckCollisions ( const _TNode& a, const _TNode& b );
96 virtual bool _CheckStopCondition ( );
97 virtual bool _UpdateResult ( _TNode& n );
100 virtual void _InitializeMarks ( );
101 virtual bool _IsMarked ( const TVertex& v ) const;
102 virtual _TFrontId _FrontId ( const TVertex& v ) const;
103 virtual TVertex _Parent ( const TVertex& v ) const;
104 virtual void _Mark ( const _TNode& n );
106 /// Pure virtual interface: vertices
107 virtual unsigned long _NumberOfVertices ( ) const = 0;
108 virtual TVertexValue _Value ( const TVertex& v ) const = 0;
109 virtual TResult _Result ( const TVertex& v ) const = 0;
111 /// Pure virtual interface: edges
112 virtual double _Norm ( const TVertex& a, const TVertex& b ) const = 0;
113 virtual bool _Edge ( const TVertex& a, const TVertex& b ) const = 0;
114 virtual TCost _Cost ( const TVertex& a, const TVertex& b ) const = 0;
116 /// Pure virtual interface: neighborhood
117 virtual void _Neighs ( const _TNode& n, _TNodes& N ) const = 0;
118 virtual bool _UpdateNeigh ( _TNode& nn, const _TNode& n ) = 0;
119 virtual void _NeighsInDim ( const _TNode& n,
120 const unsigned int& d,
123 /// Pure virtual interface: queue
124 virtual void _InitializeQueue ( ) = 0;
125 virtual bool _IsQueueEmpty ( ) const = 0;
126 virtual void _QueuePush ( const _TNode& n ) = 0;
127 virtual _TNode _QueuePop ( ) = 0;
128 virtual void _QueueClear ( ) = 0;
130 /// Pure virtual interface: results
131 virtual void _InitializeResults ( ) = 0;
134 // Purposely not implemented
135 Algorithm( const Self& );
136 void operator=( const Self& );
139 bool m_StopAtOneFront;
145 _TCollisionSites m_CollisionSites;
152 #include <fpa/Base/Algorithm.hxx>
154 #endif // __FPA__BASE__ALGORITHM__H__