X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2FcpExtensions%2FDataStructures%2FGraph.h;h=d9e913d579b326a535d2ebcc8cb59261cea9874f;hb=aee3cafa7e93f996580777976636ed625dbc43f5;hp=a23582ff03346c2b215456031458603c0fbfc080;hpb=950ea6d252c9a5bc5be29d413497fe0ef69e6703;p=cpPlugins.git diff --git a/lib/cpExtensions/DataStructures/Graph.h b/lib/cpExtensions/DataStructures/Graph.h index a23582f..d9e913d 100644 --- a/lib/cpExtensions/DataStructures/Graph.h +++ b/lib/cpExtensions/DataStructures/Graph.h @@ -1,61 +1,143 @@ -#ifndef __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__ -#define __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__ +#ifndef __cpExtensions__DataStructures__Graph__h__ +#define __cpExtensions__DataStructures__Graph__h__ +#include #include #include #include -#include +#include #include namespace cpExtensions { namespace DataStructures { - /** + /** \brief A generic graph with templated index types. + * + * @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 + : public itk::DataObject { public: typedef Graph Self; - typedef itk::LightObject Superclass; + typedef itk::DataObject Superclass; 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; - // 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, TIndexCompare > TVertices; + typedef std::vector< TCost > TEdges; + typedef std::map< TIndex, TEdges, TIndexCompare > TMatrixRow; + typedef std::map< TIndex, TMatrixRow, TIndexCompare > TMatrix; public: itkNewMacro( Self ); - itkTypeMacro( Graph, itk::LightObject ); + itkTypeMacro( Graph, itk::DataObject ); 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; - - bool HasVertexIndex( const I& index ) const; - void InsertVertex( const I& index, V& vertex ); - V& GetVertex( const I& index ); - const V& GetVertex( const I& index ) const; - - void AddConnection( const I& orig, const I& dest, const C& cost ); - - std::set< I > GetSinks( ) 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( ); + + /*! \brief Clear all edges. + */ + inline void ClearEdges( ) + { this->m_Matrix.clear( ); } + + /*! \brief Vertex manipulation methods. + * Names are self-explanatory. + */ + 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. + */ + 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. + * + * A sink is a special vertex which does not have any "exiting" edges. + * + * @return Sinks ordered by their index. + */ + std::set< TIndex, TIndexCompare > GetSinks( ) const; protected: Graph( ); @@ -76,9 +158,9 @@ namespace cpExtensions } // ecapseman #ifndef ITK_MANUAL_INSTANTIATION -#include +# include #endif // ITK_MANUAL_INSTANTIATION -#endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__ +#endif // __cpExtensions__DataStructures__Graph__h__ // eof - $RCSfile$