...

[cpPlugins.git] / lib / cpExtensions / DataStructures / Graph.h

diff --git a/lib/cpExtensions/DataStructures/Graph.h b/lib/cpExtensions/DataStructures/Graph.h
index b11b7031891437142ee70ce33dd3665dc872b3b4..75bdd6821aef2a1be03cce89b7ce627b8ceff72c 100644 (file)
--- a/lib/cpExtensions/DataStructures/Graph.h
+++ b/lib/cpExtensions/DataStructures/Graph.h
@@ -11,7 +11,11 @@ namespace cpExtensions
 {
   namespace DataStructures
   {
-    /**
+    /** \brief A generic graph with templated index types.
+     *
+     *  @param V Vertex type.
+     *  @param C Cost type.
+     *  @param I Index type (it should be a strict weak ordering type).
      */
     template< class V, class C, class I = unsigned long >
     class Graph
@@ -27,37 +31,112 @@ namespace cpExtensions
       typedef C TCost;
       typedef I TIndex;
 
-      // Graph types
-      typedef std::map< I, V >          TVertices;
-      typedef std::vector< C >          TEdges;
-      typedef std::map< I, TEdges >     TMatrixRow;
-      typedef std::map< I, TMatrixRow > TMatrix;
+      // Base types
+      typedef std::map< TIndex, TVertex >    TVertices;
+      typedef std::vector< TCost >           TEdges;
+      typedef std::map< TIndex, TEdges >     TMatrixRow;
+      typedef std::map< TIndex, TMatrixRow > TMatrix;
 
     public:
       itkNewMacro( Self );
       itkTypeMacro( Graph, itk::LightObject );
 
     public:
-      typename TVertices::iterator BeginVertices( );
-      typename TVertices::iterator EndVertices( );
-      typename TVertices::const_iterator BeginVertices( ) const;
-      typename TVertices::const_iterator EndVertices( ) const;
-
-      typename TMatrix::iterator BeginEdgesRows( );
-      typename TMatrix::iterator EndEdgetsRows( );
-      typename TMatrix::const_iterator BeginEdgesRows( ) const;
-      typename TMatrix::const_iterator EndEdgesRows( ) const;
-
+      /*! \brief Iterators over vertices.
+       *         These allow you to iterate over all of graph's vertices.
+       *
+       * Typical iteration should be done as:
+       *
+       *  TGraph g;
+       *  ...
+       *  TGraph::TVertices::[const_]iterator vIt = g.BeginVertices( );
+       *  for( ; vIt != g.EndVertices( ); ++vIt )
+       *  {
+       *    vIt->first;  --> this is the vertex's index <--
+       *    vIt->second; --> this is the vertex's value <--
+       *  }
+       */
+      inline typename TVertices::iterator BeginVertices( )
+        { return( this->m_Vertices.begin( ) ); }
+      inline typename TVertices::iterator EndVertices( )
+        { return( this->m_Vertices.end( ) ); }
+      inline typename TVertices::const_iterator BeginVertices( ) const
+        { return( this->m_Vertices.begin( ) ); }
+      inline typename TVertices::const_iterator EndVertices( ) const
+        { return( this->m_Vertices.end( ) ); }
+
+      /*! \brief Iterators over edges.
+       *         These allow you to iterate over all of graph's edges.
+       *
+       * Typical iteration should be done as:
+       *
+       *  TGraph g;
+       *  ...
+       *  TGraph::TMatrix::[const_]iterator mIt = g.BeginEdgesRows( );
+       *  for( ; mIt != g.EndEdgesRows( ); ++mIt )
+       *  {
+       *    mIt->first; --> this is the row index. <--
+       *    TGraph::TMatrixRow::[const_]iterator rIt = mIt->second.begin( );
+       *    for( ; rIt != mIt->second.end( ); ++rIt )
+       *    {
+       *      rIt->first;  --> this is the column index.
+       *      TGraph::TEdges::[const_]iterator eIt = rIt->second.begin( );
+       *      for( ; eIt != rIt->second.end( ); ++eIt )
+       *        *eIt; --> this is the cost between mIt->first and rIt->first
+       *    }
+       *  }
+       */
+      inline typename TMatrix::iterator BeginEdgesRows( )
+        { return( this->m_Matrix.begin( ) ); }
+      inline typename TMatrix::iterator EndEdgetsRows( )
+        { return( this->m_Matrix.end( ) ); }
+      inline typename TMatrix::const_iterator BeginEdgesRows( ) const
+        { return( this->m_Matrix.begin( ) ); }
+      inline typename TMatrix::const_iterator EndEdgesRows( ) const
+        { return( this->m_Matrix.end( ) ); }
+
+      /*! \brief Clear all vertices and edges.
+       */
       void Clear( );
 
-      bool HasVertexIndex( const I& index ) const;
-      void SetVertex( const I& index, V& vertex );
+      /*! \brief Clear all edges.
+       */
+      inline void ClearEdges( )
+        { this->m_Matrix.clear( ); }
+
+      /*! \brief Vertex manipulation methods.
+       *         Names are self-explanatory.
+       */
+      inline bool HasVertexIndex( const I& i ) const
+        { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); }
+      inline void SetVertex( const I& index, V& vertex )
+        { this->m_Vertices[ index ] = vertex; }
+      inline V& GetVertex( const I& index )
+        { return( this->m_Vertices[ index ] ); }
+      inline const V& GetVertex( const I& index ) const
+        { return( this->m_Vertices[ index ] ); }
       bool RenameVertex( const I& old_index, const I& new_index );
-      V& GetVertex( const I& index );
-      const V& GetVertex( const I& index ) const;
-
-      void AddConnection( const I& orig, const I& dest, const C& cost );
-
+      void RemoveVertex( const I& index );
+
+      /*! \brief Edge manipulation methods.
+       *         Names are self-explanatory.
+       */
+      inline void AddEdge( const I& orig, const I& dest, const C& cost )
+        { this->m_Matrix[ orig ][ dest ].push_back( cost ); }
+      inline TEdges& GetEdges( const I& orig, const I& dest )
+        { return( this->m_Matrix[ orig ][ dest ] ); }
+      inline const TEdges& GetEdges( const I& orig, const I& dest ) const
+        { return( this->m_Matrix[ orig ][ dest ] ); }
+      bool HasEdge( const I& orig, const I& dest ) const;
+      void RemoveEdge( const I& orig, const I& dest, const C& cost );
+      void RemoveEdges( const I& orig, const I& dest );
+
+      /*! \brief Returns graph's sinks.
+       *
+       *  A sink is a special vertex which does not have any "exiting" edges.
+       *
+       *  @return Sinks ordered by their index.
+       */
       std::set< I > GetSinks( ) const;
 
     protected: