-#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>
-#include <itkLightObject.h>
+#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 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;
-
+ /*! \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( );
- bool HasVertexIndex( const I& index ) const;
- void SetVertex( const I& index, V& vertex );
- bool RenameVertex( const I& old_index, const I& new_index );
- 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 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( );
} // 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$
git://git.creatis.insa-lyon.fr / cpPlugins.git / blobdiff