1 #ifndef __FPA__BASE__DIJKSTRA__H__
2 #define __FPA__BASE__DIJKSTRA__H__
5 #include <fpa/Base/Algorithm.h>
6 #include <fpa/Base/MinimumSpanningTree.h>
13 * Dijkstra is a front propagation algorithm that minimizes costs
15 * @param V Vertex type.
16 * @param C Vertex value type.
17 * @param R Result value type.
18 * @param S Space type where vertices are.
19 * @param VC Vertex lexicographical compare.
20 * @param MST Minimum spanning tree type.
21 * @param B Base class for this algorithm. It should be any itk-based
22 * filter (itk::ProcessObject).
25 template< class V, class C, class R, class S, class VC, class MST, class B >
27 : public Algorithm< V, C, R, S, VC, B >
30 typedef Dijkstra Self;
31 typedef Algorithm< V, C, R, S, VC, B > Superclass;
32 typedef itk::SmartPointer< Self > Pointer;
33 typedef itk::SmartPointer< const Self > ConstPointer;
35 typedef MST TMinimumSpanningTree;
36 typedef typename Superclass::TVertex TVertex;
37 typedef typename Superclass::TValue TValue;
38 typedef typename Superclass::TResult TResult;
39 typedef typename Superclass::TSpace TSpace;
40 typedef typename Superclass::TVertexCompare TVertexCompare;
42 typedef typename Superclass::TStartEvent TStartEvent;
43 typedef typename Superclass::TStartLoopEvent TStartLoopEvent;
44 typedef typename Superclass::TEndEvent TEndEvent;
45 typedef typename Superclass::TEndLoopEvent TEndLoopEvent;
46 typedef typename Superclass::TAliveEvent TAliveEvent;
47 typedef typename Superclass::TFrontEvent TFrontEvent;
48 typedef typename Superclass::TFreezeEvent TFreezeEvent;
50 typedef typename Superclass::TStartBacktrackingEvent TStartBacktrackingEvent;
51 typedef typename Superclass::TEndBacktrackingEvent TEndBacktrackingEvent;
52 typedef typename Superclass::TBacktrackingEvent TBacktrackingEvent;
55 typedef typename Superclass::_TVertices _TVertices;
56 typedef typename Superclass::_TCollision _TCollision;
57 typedef typename Superclass::_TCollisionsRow _TCollisionsRow;
58 typedef typename Superclass::_TCollisions _TCollisions;
59 typedef typename Superclass::_TNode _TNode;
60 typedef typename Superclass::_TNodes _TNodes;
67 // Make the min-heap behave as a max-heap
68 bool operator<( const _TQueueNode& other ) const
69 { return( other.Node.Result < this->Node.Result ); }
71 typedef std::vector< _TQueueNode > _TQueue;
74 itkTypeMacro( Dijkstra, Algorithm );
76 itkBooleanMacro( LocalCosts );
77 itkBooleanMacro( FillNodeQueue );
78 itkGetConstMacro( LocalCosts, bool );
79 itkGetConstMacro( FillNodeQueue, bool );
80 itkSetMacro( LocalCosts, bool );
81 itkSetMacro( FillNodeQueue, bool );
84 TMinimumSpanningTree* GetMinimumSpanningTree( );
85 const TMinimumSpanningTree* GetMinimumSpanningTree( ) const;
86 void GraftMinimumSpanningTree( itk::DataObject* obj );
92 virtual TResult _Cost( const TVertex& v, const TVertex& p ) const = 0;
94 virtual void _BeforeGenerateData( ) ITK_OVERRIDE;
96 // Results-related abstract methods
97 virtual bool _ComputeNeighborResult(
98 TResult& result, const TVertex& neighbor, const TVertex& parent
100 virtual void _SetResult( const TVertex& v, const _TNode& n ) ITK_OVERRIDE;
102 // Queue-related abstract methods
103 virtual bool _IsQueueEmpty( ) const ITK_OVERRIDE;
104 virtual void _QueuePush( const TVertex& v, const _TNode& n ) ITK_OVERRIDE;
105 virtual void _QueuePop( TVertex& v, _TNode& n ) ITK_OVERRIDE;
106 virtual void _QueueClear( ) ITK_OVERRIDE;
109 // Purposely not implemented
110 Dijkstra( const Self& other );
111 Self& operator=( const Self& other );
115 bool m_FillNodeQueue;
117 unsigned int m_MSTIdx;
124 #ifndef ITK_MANUAL_INSTANTIATION
125 #include <fpa/Base/Dijkstra.hxx>
126 #endif // ITK_MANUAL_INSTANTIATION
128 #endif // __FPA__BASE__DIJKSTRA__H__