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 VC Vertex lexicographical compare.
18 * @param B Base class for this algorithm. It should be any itk-based
19 * filter (itk::ProcessObject).
22 template< class V, class C, class R, class VC, class B >
24 : public Algorithm< V, C, R, VC, B >
27 typedef Dijkstra Self;
28 typedef Algorithm< V, C, R, VC, B > Superclass;
29 typedef itk::SmartPointer< Self > Pointer;
30 typedef itk::SmartPointer< const Self > ConstPointer;
32 typedef typename Superclass::TVertex TVertex;
33 typedef typename Superclass::TValue TValue;
34 typedef typename Superclass::TResult TResult;
35 typedef typename Superclass::TVertexCompare TVertexCompare;
36 typedef typename Superclass::TMinimumSpanningTree TMinimumSpanningTree;
38 typedef typename Superclass::TStartEvent TStartEvent;
39 typedef typename Superclass::TStartLoopEvent TStartLoopEvent;
40 typedef typename Superclass::TEndEvent TEndEvent;
41 typedef typename Superclass::TEndLoopEvent TEndLoopEvent;
42 typedef typename Superclass::TAliveEvent TAliveEvent;
43 typedef typename Superclass::TFrontEvent TFrontEvent;
44 typedef typename Superclass::TFreezeEvent TFreezeEvent;
46 typedef typename Superclass::TStartBacktrackingEvent TStartBacktrackingEvent;
47 typedef typename Superclass::TEndBacktrackingEvent TEndBacktrackingEvent;
48 typedef typename Superclass::TBacktrackingEvent TBacktrackingEvent;
51 typedef typename Superclass::_TVertices _TVertices;
52 typedef typename Superclass::_TCollision _TCollision;
53 typedef typename Superclass::_TCollisionsRow _TCollisionsRow;
54 typedef typename Superclass::_TCollisions _TCollisions;
55 typedef typename Superclass::_TNode _TNode;
56 typedef typename Superclass::_TNodes _TNodes;
63 // Make the min-heap behave as a max-heap
64 bool operator<( const _TQueueNode& other ) const
65 { return( other.Node.Result < this->Node.Result ); }
67 typedef std::vector< _TQueueNode > _TQueue;
70 itkTypeMacro( Dijkstra, Algorithm );
76 virtual TResult _Cost( const TVertex& v, const TVertex& p ) const = 0;
78 // Results-related abstract methods
79 virtual bool _ComputeNeighborResult(
80 TResult& result, const TVertex& neighbor, const TVertex& parent
83 // Queue-related abstract methods
84 virtual bool _IsQueueEmpty( ) const;
85 virtual void _QueuePush( const TVertex& v, const _TNode& n );
86 virtual void _QueuePop( TVertex& v, _TNode& n );
87 virtual void _QueueClear( );
90 // Purposely not implemented
91 Dijkstra( const Self& other );
92 Self& operator=( const Self& other );
102 #include <fpa/Base/Dijkstra.hxx>
104 #endif // __FPA__BASE__DIJKSTRA__H__