X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FDataStructures%2FGraph.h;fp=lib%2Ffpa%2FDataStructures%2FGraph.h;h=76a617aa66b237a23f887802ca2a5b8d16da6339;hb=bd89a1af0c14ed2ac0afeca923103de54283cbaf;hp=0000000000000000000000000000000000000000;hpb=a8ac405fe1422bc0792a810f7f0693096a22c20e;p=FrontAlgorithms.git diff --git a/lib/fpa/DataStructures/Graph.h b/lib/fpa/DataStructures/Graph.h new file mode 100644 index 0000000..76a617a --- /dev/null +++ b/lib/fpa/DataStructures/Graph.h @@ -0,0 +1,167 @@ +// ========================================================================= +// @author Leonardo Florez Valencia +// @email florez-l@javeriana.edu.co +// ========================================================================= +#ifndef __fpa__DataStructures__Graph__h__ +#define __fpa__DataStructures__Graph__h__ + +#include +#include +#include +#include +#include + +namespace fpa +{ + 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 _TVertex, class _TCost, class _TIndex = unsigned long, class _TIndexCompare = std::less< _TIndex > > + class Graph + : public itk::DataObject + { + public: + typedef Graph Self; + typedef itk::DataObject Superclass; + typedef itk::SmartPointer< Self > Pointer; + typedef itk::SmartPointer< const Self > ConstPointer; + + typedef _TVertex TVertex; + typedef _TCost TCost; + typedef _TIndex TIndex; + typedef _TIndexCompare TIndexCompare; + + // 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::DataObject ); + + 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 <-- + * } + */ + 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( ); + virtual ~Graph( ); + + private: + // Purposely not implemented + Graph( const Self& other ); + Self& operator=( const Self& other ); + + protected: + TVertices m_Vertices; + TMatrix m_Matrix; + }; + + } // ecapseman + +} // ecapseman + +#ifndef ITK_MANUAL_INSTANTIATION +# include +#endif // ITK_MANUAL_INSTANTIATION +#endif // __fpa__DataStructures__Graph__h__ +// eof - $RCSfile$