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 B Base class for this algorithm. It should be any itk-based
18 * filter (itk::ProcessObject).
21 template< class V, class C, class R, class B >
23 : public Algorithm< V, C, R, B >
26 typedef Dijkstra Self;
27 typedef Algorithm< V, C, R, B > Superclass;
28 typedef itk::SmartPointer< Self > Pointer;
29 typedef itk::SmartPointer< const Self > ConstPointer;
31 typedef typename Superclass::TVertex TVertex;
32 typedef typename Superclass::TValue TValue;
33 typedef typename Superclass::TResult TResult;
36 typedef typename Superclass::_TVertices _TVertices;
37 typedef typename Superclass::_TCollision _TCollision;
38 typedef typename Superclass::_TCollisionsRow _TCollisionsRow;
39 typedef typename Superclass::_TCollisions _TCollisions;
40 typedef typename Superclass::_TNode _TNode;
41 typedef typename Superclass::_TNodes _TNodes;
43 typedef std::vector< _TNode > _TQueue;
46 // Make the min-heap behave as a max-heap
47 bool operator()( const _TNode& a, const _TNode& b ) const
48 { return( b.Result < a.Result ); }
52 itkTypeMacro( Dijkstra, Algorithm );
58 virtual TResult _Cost( const TVertex& v, const TVertex& p ) const = 0;
60 // Results-related abstract methods
61 virtual bool _ComputeNeighborResult(
62 TResult& result, const TVertex& neighbor, const TVertex& parent
65 // Queue-related abstract methods
66 virtual bool _IsQueueEmpty( ) const;
67 virtual void _QueuePush( const _TNode& n );
68 virtual _TNode _QueuePop( );
69 virtual void _QueueClear( );
72 // Purposely not implemented
73 Dijkstra( const Self& other );
74 Self& operator=( const Self& other );
78 static _TNodeCompare m_NodeCompare;
85 #include <fpa/Base/Dijkstra.hxx>
87 #endif // __FPA__BASE__DIJKSTRA__H__