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       typename TVertices::iterator BeginVertices( );
  60       typename TVertices::iterator EndVertices( );
  61       typename TVertices::const_iterator BeginVertices( ) const;
  62       typename TVertices::const_iterator EndVertices( ) const;
  63
  64       /*! \brief Iterators over edges.
  65        *         These allow you to iterate over all of graph's edges.
  66        *
  67        * Typical iteration should be done as:
  68        *
  69        *  TGraph g;
  70        *  ...
  71        *  TGraph::TMatrix::[const_]iterator mIt = g.BeginEdgesRows( );
  72        *  for( ; mIt != g.EndEdgesRows( ); ++mIt )
  73        *  {
  74        *    mIt->first; --> this is the row index. <--
  75        *    TGraph::TMatrixRow::[const_]iterator rIt = mIt->second.begin( );
  76        *    for( ; rIt != mIt->second.end( ); ++rIt )
  77        *    {
  78        *      rIt->first;  --> this is the column index.
  79        *      TGraph::TEdges::[const_]iterator eIt = rIt->second.begin( );
  80        *      for( ; eIt != rIt->second.end( ); ++eIt )
  81        *        *eIt; --> this is the cost between mIt->first and rIt->first
  82        *    }
  83        *  }
  84        */
  85       typename TMatrix::iterator BeginEdgesRows( );
  86       typename TMatrix::iterator EndEdgetsRows( );
  87       typename TMatrix::const_iterator BeginEdgesRows( ) const;
  88       typename TMatrix::const_iterator EndEdgesRows( ) const;
  89
  90       /*! \brief Clear all vertices and edges.
  91        */
  92       void Clear( );
  93
  94       /*! \brief Clear all edges.
  95        */
  96       void ClearEdges( );
  97
  98       /*! \brief Vertex manipulation methods.
  99        *         Names are self-explanatory.
 100        */
 101       bool HasVertexIndex( const I& index ) const;
 102       void SetVertex( const I& index, V& vertex );
 103       bool RenameVertex( const I& old_index, const I& new_index );
 104       void RemoveVertex( const I& index );
 105       V& GetVertex( const I& index );
 106       const V& GetVertex( const I& index ) const;
 107
 108       /*! \brief Edge manipulation methods.
 109        *         Names are self-explanatory.
 110        */
 111       bool HasEdge( const I& orig, const I& dest ) const;
 112       void AddEdge( const I& orig, const I& dest, const C& cost );
 113       void RemoveEdge( const I& orig, const I& dest, const C& cost );
 114       void RemoveEdges( const I& orig, const I& dest );
 115       TEdges& GetEdges( const I& orig, const I& dest );
 116       const TEdges& GetEdges( const I& orig, const I& dest ) const;
 117
 118       /*! \brief Returns graph's sinks.
 119        *
 120        *  A sink is a special vertex which does not have any "exiting" edges.
 121        *
 122        *  @return Sinks ordered by their index.
 123        */
 124       std::set< I > GetSinks( ) const;
 125
 126     protected:
 127       Graph( );
 128       virtual ~Graph( );
 129
 130     private:
 131       // Purposely not implemented
 132       Graph( const Self& other );
 133       Self& operator=( const Self& other );
 134
 135     protected:
 136       TVertices m_Vertices;
 137       TMatrix   m_Matrix;
 138     };
 139
 140   } // ecapseman
 141
 142 } // ecapseman
 143
 144 #ifndef ITK_MANUAL_INSTANTIATION
 145 #include <cpExtensions/DataStructures/Graph.hxx>
 146 #endif // ITK_MANUAL_INSTANTIATION
 147
 148 #endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__
 149
 150 // eof - $RCSfile$