...

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

diff --git a/lib/cpExtensions/DataStructures/Graph.h b/lib/cpExtensions/DataStructures/Graph.h
index 5fb2707f5def3e5257054285d6805d59acd9e63f..db07f2e0cf8ca52eeed617b92f832c8a49cacbd7 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,36 +31,96 @@ 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:
+      /*! \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 <--
+       *  }
+       */
       typename TVertices::iterator BeginVertices( );
       typename TVertices::iterator EndVertices( );
       typename TVertices::const_iterator BeginVertices( ) const;
       typename TVertices::const_iterator EndVertices( ) const;
 
+      /*! \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
+       *    }
+       *  }
+       */
       typename TMatrix::iterator BeginEdgesRows( );
       typename TMatrix::iterator EndEdgetsRows( );
       typename TMatrix::const_iterator BeginEdgesRows( ) const;
       typename TMatrix::const_iterator EndEdgesRows( ) const;
 
+      /*! \brief Clear all vertices and edges.
+       */
       void Clear( );
 
+      /*! \brief Clear all edges.
+       */
+      void ClearEdges( );
+
+      /*! \brief Vertex manipulation methods.
+       *         Names are self-explanatory.
+       */
       bool HasVertexIndex( const I& index ) const;
-      void InsertVertex( const I& index, V& vertex );
+      void SetVertex( const I& index, V& vertex );
+      bool RenameVertex( const I& old_index, const I& new_index );
+      void RemoveVertex( const I& index );
       V& GetVertex( const I& index );
       const V& GetVertex( const I& index ) const;
 
-      void AddConnection( const I& orig, const I& dest, const C& cost );
-
+      /*! \brief Edge manipulation methods.
+       *         Names are self-explanatory.
+       */
+      bool HasEdge( const I& orig, const I& dest ) const;
+      void AddEdge( const I& orig, const I& dest, const C& cost );
+      void RemoveEdge( const I& orig, const I& dest, const C& cost );
+      void RemoveEdges( const I& orig, const I& dest );
+      TEdges& GetEdges( const I& orig, const I& dest );
+      const TEdges& GetEdges( const I& orig, const I& dest ) const;
+
+      /*! \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: