1 #ifndef __FPA__BASE__DIJKSTRA__H__
2 #define __FPA__BASE__DIJKSTRA__H__
5 #include <fpa/Base/Algorithm.h>
12 * Dijkstra is a front propagation algorithm that minimizes costs
14 * @param V Vertex type.
15 * @param C Vertex value type.
16 * @param R Result value type.
17 * @param S Space type where vertices are.
18 * @param VC Vertex lexicographical compare.
19 * @param B Base class for this algorithm. It should be any itk-based
20 * filter (itk::ProcessObject).
23 template< class V, class C, class R, class S, class VC, class B >
25 : public Algorithm< V, C, R, S, VC, B >
28 typedef Dijkstra Self;
29 typedef Algorithm< V, C, R, S, VC, B > Superclass;
30 typedef itk::SmartPointer< Self > Pointer;
31 typedef itk::SmartPointer< const Self > ConstPointer;
33 typedef typename Superclass::TVertex TVertex;
34 typedef typename Superclass::TValue TValue;
35 typedef typename Superclass::TResult TResult;
36 typedef typename Superclass::TSpace TSpace;
37 typedef typename Superclass::TVertexCompare TVertexCompare;
38 typedef typename Superclass::TMinimumSpanningTree TMinimumSpanningTree;
40 typedef typename Superclass::TStartEvent TStartEvent;
41 typedef typename Superclass::TStartLoopEvent TStartLoopEvent;
42 typedef typename Superclass::TEndEvent TEndEvent;
43 typedef typename Superclass::TEndLoopEvent TEndLoopEvent;
44 typedef typename Superclass::TAliveEvent TAliveEvent;
45 typedef typename Superclass::TFrontEvent TFrontEvent;
46 typedef typename Superclass::TFreezeEvent TFreezeEvent;
48 typedef typename Superclass::TStartBacktrackingEvent TStartBacktrackingEvent;
49 typedef typename Superclass::TEndBacktrackingEvent TEndBacktrackingEvent;
50 typedef typename Superclass::TBacktrackingEvent TBacktrackingEvent;
53 typedef typename Superclass::_TVertices _TVertices;
54 typedef typename Superclass::_TCollision _TCollision;
55 typedef typename Superclass::_TCollisionsRow _TCollisionsRow;
56 typedef typename Superclass::_TCollisions _TCollisions;
57 typedef typename Superclass::_TNode _TNode;
58 typedef typename Superclass::_TNodes _TNodes;
65 // Make the min-heap behave as a max-heap
66 bool operator<( const _TQueueNode& other ) const
67 { return( other.Node.Result < this->Node.Result ); }
69 typedef std::vector< _TQueueNode > _TQueue;
72 itkTypeMacro( Dijkstra, Algorithm );
74 itkBooleanMacro( LocalCosts );
75 itkGetConstMacro( LocalCosts, bool );
76 itkSetMacro( LocalCosts, bool );
82 virtual TResult _Cost( const TVertex& v, const TVertex& p ) const = 0;
84 // Results-related abstract methods
85 virtual bool _ComputeNeighborResult(
86 TResult& result, const TVertex& neighbor, const TVertex& parent
89 // Queue-related abstract methods
90 virtual bool _IsQueueEmpty( ) const;
91 virtual void _QueuePush( const TVertex& v, const _TNode& n );
92 virtual void _QueuePop( TVertex& v, _TNode& n );
93 virtual void _QueueClear( );
96 // Purposely not implemented
97 Dijkstra( const Self& other );
98 Self& operator=( const Self& other );
109 #include <fpa/Base/Dijkstra.hxx>
111 #endif // __FPA__BASE__DIJKSTRA__H__