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;
59 typedef EndBacktrackingEvent< TVertex > TEndBacktrackingEvent;
62 itkTypeMacro( Algorithm, itkProcessObject );
64 itkBooleanMacro( StopAtOneFront );
65 itkBooleanMacro( ThrowEvents );
67 itkGetConstMacro( StopAtOneFront, bool );
68 itkGetConstMacro( ThrowEvents, bool );
70 itkSetMacro( StopAtOneFront, bool );
71 itkSetMacro( ThrowEvents, bool );
74 virtual void InvokeEvent( const itk::EventObject& e );
75 virtual void InvokeEvent( const itk::EventObject& e ) const;
77 /// Seeds manipulation
78 void AddSeed( const TVertex& s, const TResult& v );
79 const TVertex& GetSeed( const unsigned long& i ) const;
81 unsigned long GetNumberOfSeeds( ) const;
85 virtual ~Algorithm( );
87 /// itk::ProcessObject
88 virtual void GenerateData( );
91 virtual void _BeforeMainLoop ( );
92 virtual void _AfterMainLoop ( );
93 virtual void _BeforeLoop ( );
94 virtual void _AfterLoop ( );
95 virtual void _Loop ( );
96 virtual bool _CheckCollisions ( const _TNode& a, const _TNode& b );
97 virtual bool _CheckStopCondition ( );
98 virtual bool _UpdateResult ( _TNode& n );
101 virtual void _InitializeMarks ( );
102 virtual bool _IsMarked ( const TVertex& v ) const;
103 virtual _TFrontId _FrontId ( const TVertex& v ) const;
104 virtual TVertex _Parent ( const TVertex& v ) const;
105 virtual void _Mark ( const _TNode& n );
107 /// Pure virtual interface: vertices
108 virtual unsigned long _NumberOfVertices ( ) const = 0;
109 virtual TVertexValue _Value ( const TVertex& v ) const = 0;
110 virtual TResult _Result ( const TVertex& v ) const = 0;
112 /// Pure virtual interface: edges
113 virtual double _Norm ( const TVertex& a, const TVertex& b ) const = 0;
114 virtual bool _Edge ( const TVertex& a, const TVertex& b ) const = 0;
115 virtual TCost _Cost ( const TVertex& a, const TVertex& b ) const = 0;
117 /// Pure virtual interface: neighborhood
118 virtual void _Neighs ( const _TNode& n, _TNodes& N ) const = 0;
119 virtual bool _UpdateNeigh ( _TNode& nn, const _TNode& n ) = 0;
120 virtual void _NeighsInDim ( const _TNode& n,
121 const unsigned int& d,
124 /// Pure virtual interface: queue
125 virtual void _InitializeQueue ( ) = 0;
126 virtual bool _IsQueueEmpty ( ) const = 0;
127 virtual void _QueuePush ( const _TNode& n ) = 0;
128 virtual _TNode _QueuePop ( ) = 0;
129 virtual void _QueueClear ( ) = 0;
131 /// Pure virtual interface: results
132 virtual void _InitializeResults ( ) = 0;
135 // Purposely not implemented
136 Algorithm( const Self& );
137 void operator=( const Self& );
140 bool m_StopAtOneFront;
146 _TCollisionSites m_CollisionSites;
153 #include <fpa/Base/Algorithm.hxx>
155 #endif // __FPA__BASE__ALGORITHM__H__