lib/cpExtensions/DataStructures/Graph.h

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