X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FDijkstra.h;h=602608eb9973cfbf0849cbd8db594b5b3a2b5d6f;hb=b4ed6ddfa7e90e892f07cad9a760961bd4e84e6b;hp=a6212cf9b770fe178605f0d241fdfd3430dfd0d6;hpb=9622bd5b833a8845881003228207e0caca59b081;p=FrontAlgorithms.git

diff --git a/lib/fpa/Base/Dijkstra.h b/lib/fpa/Base/Dijkstra.h
index a6212cf..602608e 100644
--- a/lib/fpa/Base/Dijkstra.h
+++ b/lib/fpa/Base/Dijkstra.h
@@ -8,104 +8,90 @@ namespace fpa
 {
   namespace Base
   {
-    /**
-     */
-    template< class V, class C, class VV, class VC >
-    class DijkstraTraits
-    {
-    public:
-      typedef V TVertex;
-      typedef C TResult;
-      typedef C TCost;
-      typedef VV TVertexValue;
-      typedef VC TVertexCmp;
-      typedef long TFrontId;
-
-      class TNode
-      {
-      public:
-        TNode( )
-          : Cost( 0 )
-          { }
-        TNode( const TVertex& v, const TFrontId& f )
-          : Vertex( v ),
-            Parent( v ),
-            Result( TResult( 0 ) ),
-            FrontId( f ),
-            Cost( TCost( 0 ) )
-          { }
-        TNode( const TVertex& v, const TResult& r, const TFrontId& f )
-          : Vertex( v ),
-            Parent( v ),
-            Result( r ),
-            FrontId( f ),
-            Cost( TCost( 0 ) )
-          { }
-        virtual ~TNode( )
-          { }
-
-        // NOTE: stl::heaps work as maximum priority queues
-        bool operator<( const TNode& other ) const
-          { return( other.Cost < this->Cost ); }
-
-        TVertex Vertex;
-        TVertex Parent;
-        TResult Result;
-        TFrontId FrontId;
-        TCost Cost;
-      };
-
-      typedef std::vector< TNode > TNodes;
-    };
-
     /**
      * 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 VV, class VC, class B >
+    template< class V, class C, class R, class VC, class B >
     class Dijkstra
-      : public Algorithm< DijkstraTraits< V, C, VV, VC >, B >
+      : public Algorithm< V, C, R, VC, B >
     {
     public:
-      // Templated types
-      typedef V TVertex;
-      typedef C TCost;
-      typedef VV TVertexValue;
-      typedef B  TBaseFilter;
-      typedef DijkstraTraits< V, C, VV, VC > TTraits;
-
-      // Standard class typdedefs
-      typedef Dijkstra                        Self;
-      typedef Algorithm< TTraits, B >         Superclass;
-      typedef itk::SmartPointer< Self >       Pointer;
-      typedef itk::SmartPointer< const Self > ConstPointer;
+      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::TMinimumSpanningTree TMinimumSpanningTree;
+
+      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;
 
     protected:
-      typedef typename TTraits::TFrontId  _TFrontId;
-      typedef typename TTraits::TNode     _TNode;
-      typedef typename TTraits::TNodes    _TNodes;
+      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;
 
-      typedef std::vector< _TNode > _TQueue;
+        // 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;
 
     public:
-      itkTypeMacro( Dijkstra, Base );
+      itkTypeMacro( Dijkstra, Algorithm );
 
     protected:
       Dijkstra( );
       virtual ~Dijkstra( );
 
-      virtual   void _InitializeQueue ( );
-      virtual   bool _IsQueueEmpty    ( ) const;
-      virtual   void _QueuePush       ( const _TNode& n );
-      virtual _TNode _QueuePop        ( );
-      virtual   void _QueueClear      ( );
-      virtual   bool _UpdateNeigh     ( _TNode& nn, const _TNode& n );
+      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( );
 
     private:
       // Purposely not implemented
-      Dijkstra( const Self& );
-      void operator=( const Self& );
+      Dijkstra( const Self& other );
+      Self& operator=( const Self& other );
 
-    private:
+    protected:
       _TQueue m_Queue;
     };