lib/fpa/DataStructures/Graph.h

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