lib/cpExtensions/DataStructures/Graph.h

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