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 <itkDataObject.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 _TVertex Vertex type.
  18      *  @param _TCost   Cost type.
  19      *  @param _TIndex  Index type (it should be a strict weak ordering type).
  20      */
  21     template< class _TVertex, class _TCost, class _TIndex = unsigned long, class _TIndexCompare = std::less< _TIndex > >
  22     class Graph
  23       : public itk::DataObject
  24     {
  25     public:
  26       typedef Graph                           Self;
  27       typedef itk::DataObject                 Superclass;
  28       typedef itk::SmartPointer< Self >       Pointer;
  29       typedef itk::SmartPointer< const Self > ConstPointer;
  30
  31       typedef _TVertex       TVertex;
  32       typedef _TCost         TCost;
  33       typedef _TIndex        TIndex;
  34       typedef _TIndexCompare TIndexCompare;
  35
  36       // Base types
  37       typedef std::map< TIndex, TVertex, TIndexCompare >    TVertices;
  38       typedef std::vector< TCost >                          TEdges;
  39       typedef std::map< TIndex, TEdges, TIndexCompare >     TMatrixRow;
  40       typedef std::map< TIndex, TMatrixRow, TIndexCompare > TMatrix;
  41
  42     public:
  43       itkNewMacro( Self );
  44       itkTypeMacro( Graph, itk::DataObject );
  45
  46     public:
  47       /*! \brief Iterators over vertices.
  48        *         These allow you to iterate over all of graph's vertices.
  49        *
  50        * Typical iteration should be done as:
  51        *
  52        *  TGraph g;
  53        *  ...
  54        *  TGraph::TVertices::[const_]iterator vIt = g.BeginVertices( );
  55        *  for( ; vIt != g.EndVertices( ); ++vIt )
  56        *  {
  57        *    vIt->first;  --> this is the vertex's index <--
  58        *    vIt->second; --> this is the vertex's value <--
  59        *  }
  60        */
  61       inline typename TVertices::iterator BeginVertices( )
  62         { return( this->m_Vertices.begin( ) ); }
  63       inline typename TVertices::iterator EndVertices( )
  64         { return( this->m_Vertices.end( ) ); }
  65       inline typename TVertices::const_iterator BeginVertices( ) const
  66         { return( this->m_Vertices.begin( ) ); }
  67       inline typename TVertices::const_iterator EndVertices( ) const
  68         { return( this->m_Vertices.end( ) ); }
  69
  70       /*! \brief Iterators over edges.
  71        *         These allow you to iterate over all of graph's edges.
  72        *
  73        * Typical iteration should be done as:
  74        *
  75        *  TGraph g;
  76        *  ...
  77        *  TGraph::TMatrix::[const_]iterator mIt = g.BeginEdgesRows( );
  78        *  for( ; mIt != g.EndEdgesRows( ); ++mIt )
  79        *  {
  80        *    mIt->first; --> this is the row index. <--
  81        *    TGraph::TMatrixRow::[const_]iterator rIt = mIt->second.begin( );
  82        *    for( ; rIt != mIt->second.end( ); ++rIt )
  83        *    {
  84        *      rIt->first;  --> this is the column index.
  85        *      TGraph::TEdges::[const_]iterator eIt = rIt->second.begin( );
  86        *      for( ; eIt != rIt->second.end( ); ++eIt )
  87        *        *eIt; --> this is the cost between mIt->first and rIt->first
  88        *    }
  89        *  }
  90        */
  91       inline typename TMatrix::iterator BeginEdgesRows( )
  92         { return( this->m_Matrix.begin( ) ); }
  93       inline typename TMatrix::iterator EndEdgetsRows( )
  94         { return( this->m_Matrix.end( ) ); }
  95       inline typename TMatrix::const_iterator BeginEdgesRows( ) const
  96         { return( this->m_Matrix.begin( ) ); }
  97       inline typename TMatrix::const_iterator EndEdgesRows( ) const
  98         { return( this->m_Matrix.end( ) ); }
  99
 100       /*! \brief Clear all vertices and edges.
 101        */
 102       void Clear( );
 103
 104       /*! \brief Clear all edges.
 105        */
 106       inline void ClearEdges( )
 107         { this->m_Matrix.clear( ); }
 108
 109       /*! \brief Vertex manipulation methods.
 110        *         Names are self-explanatory.
 111        */
 112       inline bool HasVertexIndex( const TIndex& i ) const
 113         { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); }
 114       inline void SetVertex( const TIndex& index, TVertex& vertex )
 115         { this->m_Vertices[ index ] = vertex; }
 116       inline TVertex& GetVertex( const TIndex& index )
 117         { return( this->m_Vertices[ index ] ); }
 118       inline const TVertex& GetVertex( const TIndex& index ) const
 119         { return( this->m_Vertices[ index ] ); }
 120       bool RenameVertex( const TIndex& old_index, const TIndex& new_index );
 121       void RemoveVertex( const TIndex& index );
 122
 123       /*! \brief Edge manipulation methods.
 124        *         Names are self-explanatory.
 125        */
 126       inline void AddEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
 127         { this->m_Matrix[ orig ][ dest ].push_back( cost ); }
 128       TEdges& GetEdges( const TIndex& orig, const TIndex& dest );
 129       const TEdges& GetEdges( const TIndex& orig, const TIndex& dest ) const;
 130       bool HasEdge( const TIndex& orig, const TIndex& dest ) const;
 131       void RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost );
 132       void RemoveEdges( const TIndex& orig, const TIndex& 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< TIndex, TIndexCompare > 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$