-#ifndef __FPA__BASE__DIJKSTRA__H__
-#define __FPA__BASE__DIJKSTRA__H__
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
-#include <vector>
-#include <fpa/Base/Algorithm.h>
+#ifndef __fpa__Base__Dijkstra__h__
+#define __fpa__Base__Dijkstra__h__
+
+#include <fpa/Base/DijkstraBase.h>
namespace fpa
{
namespace Base
{
/**
- * Dijkstra is a front propagation algorithm that minimizes costs
- *
- * @param V Vertex type.
- * @param C Vertex value type.
- * @param R Result value type.
- * @param VC Vertex lexicographical compare.
- * @param B Base class for this algorithm. It should be any itk-based
- * filter (itk::ProcessObject).
- *
*/
- template< class V, class C, class R, class VC, class B >
+ template< class _TAlgorithm, class _TMST >
class Dijkstra
- : public Algorithm< V, C, R, VC, B >
+ : public fpa::Base::DijkstraBase< _TAlgorithm >
{
public:
- typedef Dijkstra Self;
- typedef Algorithm< V, C, R, VC, B > Superclass;
- typedef itk::SmartPointer< Self > Pointer;
- typedef itk::SmartPointer< const Self > ConstPointer;
-
- typedef typename Superclass::TVertex TVertex;
- typedef typename Superclass::TValue TValue;
- typedef typename Superclass::TResult TResult;
- typedef typename Superclass::TVertexCompare TVertexCompare;
-
- typedef typename Superclass::TStartEvent TStartEvent;
- typedef typename Superclass::TStartLoopEvent TStartLoopEvent;
- typedef typename Superclass::TEndEvent TEndEvent;
- typedef typename Superclass::TEndLoopEvent TEndLoopEvent;
- typedef typename Superclass::TAliveEvent TAliveEvent;
- typedef typename Superclass::TFrontEvent TFrontEvent;
- typedef typename Superclass::TFreezeEvent TFreezeEvent;
-
- typedef typename Superclass::TStartBacktrackingEvent TStartBacktrackingEvent;
- typedef typename Superclass::TEndBacktrackingEvent TEndBacktrackingEvent;
- typedef typename Superclass::TBacktrackingEvent TBacktrackingEvent;
+ typedef Dijkstra Self;
+ typedef fpa::Base::DijkstraBase< _TAlgorithm > Superclass;
+ typedef itk::SmartPointer< Self > Pointer;
+ typedef itk::SmartPointer< const Self > ConstPointer;
- protected:
- typedef typename Superclass::_TVertices _TVertices;
- typedef typename Superclass::_TCollision _TCollision;
- typedef typename Superclass::_TCollisionsRow _TCollisionsRow;
- typedef typename Superclass::_TCollisions _TCollisions;
- typedef typename Superclass::_TNode _TNode;
- typedef typename Superclass::_TNodes _TNodes;
-
- struct _TQueueNode
- {
- TVertex Vertex;
- _TNode Node;
-
- // Make the min-heap behave as a max-heap
- bool operator<( const _TQueueNode& other ) const
- { return( other.Node.Result < this->Node.Result ); }
- };
- typedef std::vector< _TQueueNode > _TQueue;
+ typedef _TMST TMST;
+
+ typedef typename Superclass::TNode TNode;
+ typedef typename Superclass::TNodes TNodes;
+ typedef typename Superclass::TInputValue TInputValue;
+ typedef typename Superclass::TOutputValue TOutputValue;
+ typedef typename Superclass::TFrontId TFrontId;
+ typedef typename Superclass::TVertex TVertex;
+ typedef typename Superclass::TSeeds TSeeds;
+
+ typedef typename Superclass::TQueue TQueue;
+ typedef typename Superclass::TQueueOrder TQueueOrder;
+ typedef typename Superclass::TWeightFunction TWeightFunction;
public:
- itkTypeMacro( Dijkstra, Algorithm );
+ TMST* GetMinimumSpanningTree( );
+ const TMST* GetMinimumSpanningTree( ) const;
protected:
Dijkstra( );
virtual ~Dijkstra( );
- virtual TResult _Cost( const TVertex& v, const TVertex& p ) const = 0;
-
- // Results-related abstract methods
- virtual bool _ComputeNeighborResult(
- TResult& result, const TVertex& neighbor, const TVertex& parent
- ) const;
-
- // Queue-related abstract methods
- virtual bool _IsQueueEmpty( ) const;
- virtual void _QueuePush( const TVertex& v, const _TNode& n );
- virtual void _QueuePop( TVertex& v, _TNode& n );
- virtual void _QueueClear( );
+ virtual void _AfterGenerateData( ) override;
+ virtual void _UpdateOutputValue( const TNode& n ) override;
private:
- // Purposely not implemented
+ // Purposely not implemented.
Dijkstra( const Self& other );
Self& operator=( const Self& other );
protected:
- _TQueue m_Queue;
+ unsigned int m_MSTIdx;
};
} // ecapseman
} // ecapseman
-#include <fpa/Base/Dijkstra.hxx>
+#ifndef ITK_MANUAL_INSTANTIATION
+# include <fpa/Base/Dijkstra.hxx>
+#endif // ITK_MANUAL_INSTANTIATION
-#endif // __FPA__BASE__DIJKSTRA__H__
+#endif // __fpa__Base__Dijkstra__h__
// eof - $RCSfile$