lib/fpa/Base/Graph.h

   1 // =========================================================================
   2 // @author Leonardo Florez Valencia
   3 // @email florez-l@javeriana.edu.co
   4 // =========================================================================
   5
   6 #ifndef __fpa__Base__Graph__h__
   7 #define __fpa__Base__Graph__h__
   8
   9 #include <map>
  10 #include <set>
  11 #include <vector>
  12 #include <itkDataObject.h>
  13 #include <itkObjectFactory.h>
  14
  15 namespace fpa
  16 {
  17   namespace Base
  18   {
  19     /** \brief A generic graph with templated index types.
  20      *
  21      *  @param _TVertex Vertex type.
  22      *  @param _TCost   Cost type.
  23      *  @param _TIndex  Index type (it should be a strict weak ordering type).
  24      */
  25     template< class _TVertex, class _TCost, class _TIndex = unsigned long, class _TIndexCompare = std::less< _TIndex > >
  26     class Graph
  27       : public itk::DataObject
  28     {
  29     public:
  30       typedef Graph                           Self;
  31       typedef itk::DataObject                 Superclass;
  32       typedef itk::SmartPointer< Self >       Pointer;
  33       typedef itk::SmartPointer< const Self > ConstPointer;
  34
  35       typedef _TVertex       TVertex;
  36       typedef _TCost         TCost;
  37       typedef _TIndex        TIndex;
  38       typedef _TIndexCompare TIndexCompare;
  39
  40       // Base types
  41       typedef std::map< TIndex, TVertex, TIndexCompare >    TVertices;
  42       typedef std::vector< TCost >                          TEdges;
  43       typedef std::map< TIndex, TEdges, TIndexCompare >     TMatrixRow;
  44       typedef std::map< TIndex, TMatrixRow, TIndexCompare > TMatrix;
  45
  46     public:
  47       itkNewMacro( Self );
  48       itkTypeMacro( Graph, itk::DataObject );
  49
  50     public:
  51       /*! \brief Iterators over vertices.
  52        *         These allow you to iterate over all of graph's vertices.
  53        *
  54        * Typical iteration should be done as:
  55        *
  56        *  TGraph g;
  57        *  ...
  58        *  TGraph::TVertices::[const_]iterator vIt = g.BeginVertices( );
  59        *  for( ; vIt != g.EndVertices( ); ++vIt )
  60        *  {
  61        *    vIt->first;  --> this is the vertex's index <--
  62        *    vIt->second; --> this is the vertex's value <--
  63        *  }
  64        */
  65       inline typename TVertices::iterator BeginVertices( )
  66         { return( this->m_Vertices.begin( ) ); }
  67       inline typename TVertices::iterator EndVertices( )
  68         { return( this->m_Vertices.end( ) ); }
  69       inline typename TVertices::const_iterator BeginVertices( ) const
  70         { return( this->m_Vertices.begin( ) ); }
  71       inline typename TVertices::const_iterator EndVertices( ) const
  72         { return( this->m_Vertices.end( ) ); }
  73
  74       /*! \brief Iterators over edges.
  75        *         These allow you to iterate over all of graph's edges.
  76        *
  77        * Typical iteration should be done as:
  78        *
  79        *  TGraph g;
  80        *  ...
  81        *  TGraph::TMatrix::[const_]iterator mIt = g.BeginEdgesRows( );
  82        *  for( ; mIt != g.EndEdgesRows( ); ++mIt )
  83        *  {
  84        *    mIt->first; --> this is the row index. <--
  85        *    TGraph::TMatrixRow::[const_]iterator rIt = mIt->second.begin( );
  86        *    for( ; rIt != mIt->second.end( ); ++rIt )
  87        *    {
  88        *      rIt->first;  --> this is the column index.
  89        *      TGraph::TEdges::[const_]iterator eIt = rIt->second.begin( );
  90        *      for( ; eIt != rIt->second.end( ); ++eIt )
  91        *        *eIt; --> this is the cost between mIt->first and rIt->first
  92        *    }
  93        *  }
  94        */
  95       inline typename TMatrix::iterator BeginEdgesRows( )
  96         { return( this->m_Matrix.begin( ) ); }
  97       inline typename TMatrix::iterator EndEdgetsRows( )
  98         { return( this->m_Matrix.end( ) ); }
  99       inline typename TMatrix::const_iterator BeginEdgesRows( ) const
 100         { return( this->m_Matrix.begin( ) ); }
 101       inline typename TMatrix::const_iterator EndEdgesRows( ) const
 102         { return( this->m_Matrix.end( ) ); }
 103
 104       /*! \brief Clear all vertices and edges.
 105        */
 106       void Clear( );
 107
 108       /*! \brief Clear all edges.
 109        */
 110       inline void ClearEdges( )
 111         { this->m_Matrix.clear( ); }
 112
 113       /*! \brief Vertex manipulation methods.
 114        *         Names are self-explanatory.
 115        */
 116       inline bool HasVertexIndex( const TIndex& i ) const
 117         { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); }
 118       inline void SetVertex( const TIndex& index, TVertex& vertex )
 119         { this->m_Vertices[ index ] = vertex; }
 120       inline TVertex& GetVertex( const TIndex& index )
 121         { return( this->m_Vertices[ index ] ); }
 122       inline const TVertex& GetVertex( const TIndex& index ) const
 123         { return( this->m_Vertices[ index ] ); }
 124       bool RenameVertex( const TIndex& old_index, const TIndex& new_index );
 125       void RemoveVertex( const TIndex& index );
 126
 127       /*! \brief Edge manipulation methods.
 128        *         Names are self-explanatory.
 129        */
 130       inline void AddEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
 131         { this->m_Matrix[ orig ][ dest ].push_back( cost ); }
 132       TEdges& GetEdges( const TIndex& orig, const TIndex& dest );
 133       const TEdges& GetEdges( const TIndex& orig, const TIndex& dest ) const;
 134       bool HasEdge( const TIndex& orig, const TIndex& dest ) const;
 135       void RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost );
 136       void RemoveEdges( const TIndex& orig, const TIndex& dest );
 137
 138       /*! \brief Returns graph's sinks.
 139        *
 140        *  A sink is a special vertex which does not have any "exiting" edges.
 141        *
 142        *  @return Sinks ordered by their index.
 143        */
 144       std::set< TIndex, TIndexCompare > GetSinks( ) const;
 145
 146     protected:
 147       Graph( );
 148       virtual ~Graph( );
 149
 150     private:
 151       // Purposely not implemented
 152       Graph( const Self& other );
 153       Self& operator=( const Self& other );
 154
 155     protected:
 156       TVertices m_Vertices;
 157       TMatrix   m_Matrix;
 158     };
 159
 160   } // ecapseman
 161
 162 } // ecapseman
 163
 164 #ifndef ITK_MANUAL_INSTANTIATION
 165 #  include <fpa/Base/Graph.hxx>
 166 #endif // ITK_MANUAL_INSTANTIATION
 167
 168 #endif // __fpa__Base__Graph__h__
 169
 170 // eof - $RCSfile$