Skeleton representation added.

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

diff --git a/lib/cpExtensions/DataStructures/Graph.h b/lib/cpExtensions/DataStructures/Graph.h
index db07f2e0cf8ca52eeed617b92f832c8a49cacbd7..ed2d6ae337086d941fa19909d9eea3720d2935cd 100644 (file)
--- a/lib/cpExtensions/DataStructures/Graph.h
+++ b/lib/cpExtensions/DataStructures/Graph.h
@@ -1,6 +1,7 @@
-#ifndef __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__
-#define __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__
+#ifndef __cpExtensions__DataStructures__Graph__h__
+#define __cpExtensions__DataStructures__Graph__h__
 
+#include <cpExtensions/Config.h>
 #include <map>
 #include <set>
 #include <vector>
@@ -13,11 +14,11 @@ namespace cpExtensions
   {
     /** \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).
+     *  @param _TVertex Vertex type.
+     *  @param _TCost   Cost type.
+     *  @param _TIndex  Index type (it should be a strict weak ordering type).
      */
-    template< class V, class C, class I = unsigned long >
+    template< class _TVertex, class _TCost, class _TIndex = unsigned long, class _TIndexCompare = std::less< _TIndex > >
     class Graph
       : public itk::LightObject
     {
@@ -27,15 +28,16 @@ namespace cpExtensions
       typedef itk::SmartPointer< Self >       Pointer;
       typedef itk::SmartPointer< const Self > ConstPointer;
 
-      typedef V TVertex;
-      typedef C TCost;
-      typedef I TIndex;
+      typedef _TVertex       TVertex;
+      typedef _TCost         TCost;
+      typedef _TIndex        TIndex;
+      typedef _TIndexCompare TIndexCompare;
 
       // 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;
+      typedef std::map< TIndex, TVertex, TIndexCompare >    TVertices;
+      typedef std::vector< TCost >                          TEdges;
+      typedef std::map< TIndex, TEdges, TIndexCompare >     TMatrixRow;
+      typedef std::map< TIndex, TMatrixRow, TIndexCompare > TMatrix;
 
     public:
       itkNewMacro( Self );
@@ -56,10 +58,14 @@ namespace cpExtensions
        *    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;
+      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.
@@ -82,10 +88,14 @@ namespace cpExtensions
        *    }
        *  }
        */
-      typename TMatrix::iterator BeginEdgesRows( );
-      typename TMatrix::iterator EndEdgetsRows( );
-      typename TMatrix::const_iterator BeginEdgesRows( ) const;
-      typename TMatrix::const_iterator EndEdgesRows( ) const;
+      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.
        */
@@ -93,27 +103,33 @@ namespace cpExtensions
 
       /*! \brief Clear all edges.
        */
-      void ClearEdges( );
+      inline void ClearEdges( )
+        { this->m_Matrix.clear( ); }
 
       /*! \brief Vertex manipulation methods.
        *         Names are self-explanatory.
        */
-      bool HasVertexIndex( const I& index ) const;
-      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;
+      inline bool HasVertexIndex( const TIndex& i ) const
+        { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); }
+      inline void SetVertex( const TIndex& index, TVertex& vertex )
+        { this->m_Vertices[ index ] = vertex; }
+      inline TVertex& GetVertex( const TIndex& index )
+        { return( this->m_Vertices[ index ] ); }
+      inline const TVertex& GetVertex( const TIndex& index ) const
+        { return( this->m_Vertices[ index ] ); }
+      bool RenameVertex( const TIndex& old_index, const TIndex& new_index );
+      void RemoveVertex( const TIndex& index );
 
       /*! \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;
+      inline void AddEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
+        { this->m_Matrix[ orig ][ dest ].push_back( cost ); }
+      TEdges& GetEdges( const TIndex& orig, const TIndex& dest );
+      const TEdges& GetEdges( const TIndex& orig, const TIndex& dest ) const;
+      bool HasEdge( const TIndex& orig, const TIndex& dest ) const;
+      void RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost );
+      void RemoveEdges( const TIndex& orig, const TIndex& dest );
 
       /*! \brief Returns graph's sinks.
        *
@@ -121,7 +137,7 @@ namespace cpExtensions
        *
        *  @return Sinks ordered by their index.
        */
-      std::set< I > GetSinks( ) const;
+      std::set< TIndex, TIndexCompare > GetSinks( ) const;
 
     protected:
       Graph( );
@@ -142,9 +158,9 @@ namespace cpExtensions
 } // ecapseman
 
 #ifndef ITK_MANUAL_INSTANTIATION
-#include <cpExtensions/DataStructures/Graph.hxx>
+#  include <cpExtensions/DataStructures/Graph.hxx>
 #endif // ITK_MANUAL_INSTANTIATION
 
-#endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__
+#endif // __cpExtensions__DataStructures__Graph__h__
 
 // eof - $RCSfile$