+++ /dev/null
-#ifndef __cpExtensions__DataStructures__Graph__h__
-#define __cpExtensions__DataStructures__Graph__h__
-
-#include <cpExtensions/Config.h>
-#include <map>
-#include <set>
-#include <vector>
-#include <itkDataObject.h>
-#include <itkObjectFactory.h>
-
-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 _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 <cpExtensions/DataStructures/Graph.hxx>
-#endif // ITK_MANUAL_INSTANTIATION
-
-#endif // __cpExtensions__DataStructures__Graph__h__
-
-// eof - $RCSfile$