lib/fpa/Base/MinimumSpanningTree.h

   1 #ifndef __FPA__BASE__MINIMUMSPANNINGTREE__H__
   2 #define __FPA__BASE__MINIMUMSPANNINGTREE__H__
   3
   4 #include <map>
   5 #include <vector>
   6 #include <utility>
   7 #include <itkPoint.h>
   8 #include <itkSmartPointer.h>
   9
  10 namespace fpa
  11 {
  12   namespace Base
  13   {
  14     /**
  15      */
  16     template< class _TSuperclass, class _TVertex >
  17     class MinimumSpanningTree
  18       : public _TSuperclass
  19     {
  20     public:
  21       typedef MinimumSpanningTree             Self;
  22       typedef _TSuperclass                    Superclass;
  23       typedef itk::SmartPointer< Self >       Pointer;
  24       typedef itk::SmartPointer< const Self > ConstPointer;
  25
  26       typedef _TVertex                       TVertex;
  27       typedef std::vector< TVertex >         TVertices;
  28       typedef std::pair< TVertex, bool >     TCollision;
  29       typedef std::vector< TCollision >      TCollisionsRow;
  30       typedef std::vector< TCollisionsRow >  TCollisions;
  31
  32       typedef itk::Point< double, TVertex::Dimension > TPoint;
  33       typedef std::vector< TPoint >                    TPoints;
  34       typedef std::multimap< double, TVertex >         TNodeQueue;
  35
  36     protected:
  37       typedef std::vector< unsigned long > _TRow;
  38       typedef std::vector< _TRow >         _TMatrix;
  39
  40     public:
  41       itkTypeMacro( MinimumSpanningTree, _TSuperclass );
  42
  43       itkBooleanMacro( FillNodeQueue );
  44
  45       itkGetConstReferenceMacro( Collisions, TCollisions );
  46       itkGetConstReferenceMacro( NodeQueue, TNodeQueue );
  47       itkGetConstMacro( FillNodeQueue, bool );
  48
  49       itkSetMacro( FillNodeQueue, bool );
  50
  51     public:
  52       void SetCollisions( const TCollisions& collisions );
  53       TVertices GetPath( const TVertex& a ) const;
  54       TVertices GetPath( const TVertex& a, const TVertex& b ) const;
  55
  56       virtual TPoints GetEuclideanPath( const TVertex& a ) const;
  57       virtual TPoints GetEuclideanPath(
  58         const TVertex& a, const TVertex& b
  59         ) const;
  60       virtual bool IsDefinedInEuclideanSpace( ) const;
  61
  62       virtual void SetNode(
  63         const TVertex& v,
  64         const TVertex& p,
  65         const short& fid,
  66         const double& cost
  67         );
  68       virtual void Clear( );
  69
  70     protected:
  71       MinimumSpanningTree( );
  72       virtual ~MinimumSpanningTree( );
  73
  74       virtual bool _HasVertex( const TVertex& a ) const = 0;
  75       virtual short _FrontId( const TVertex& a ) const = 0;
  76       virtual void _Path( TVertices& path, const TVertex& a ) const = 0;
  77
  78     private:
  79       // Purposely not implemented
  80       MinimumSpanningTree( const Self& other );
  81       Self& operator=( const Self& other );
  82
  83     protected:
  84       TCollisions m_Collisions;
  85       _TMatrix    m_FrontPaths;
  86       TNodeQueue  m_NodeQueue;
  87       bool        m_FillNodeQueue;
  88
  89       static const unsigned long INF_VALUE;
  90     };
  91
  92   } // ecapseman
  93
  94 } // ecapseman
  95
  96 #ifndef ITK_MANUAL_INSTANTIATION
  97 #include <fpa/Base/MinimumSpanningTree.hxx>
  98 #endif // ITK_MANUAL_INSTANTIATION
  99
 100 #endif // __FPA__BASE__MINIMUMSPANNINGTREE__H__
 101
 102 // eof - $RCSfile$