lib/fpa/Base/MinimumSpanningTree.h

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