1 #ifndef __cpExtensions__DataStructures__Graph__h__
2 #define __cpExtensions__DataStructures__Graph__h__
4 #include <cpExtensions/Config.h>
8 #include <itkDataObject.h>
9 #include <itkObjectFactory.h>
11 namespace cpExtensions
13 namespace DataStructures
15 /** \brief A generic graph with templated index types.
17 * @param _TVertex Vertex type.
18 * @param _TCost Cost type.
19 * @param _TIndex Index type (it should be a strict weak ordering type).
21 template< class _TVertex, class _TCost, class _TIndex = unsigned long, class _TIndexCompare = std::less< _TIndex > >
23 : public itk::DataObject
27 typedef itk::DataObject Superclass;
28 typedef itk::SmartPointer< Self > Pointer;
29 typedef itk::SmartPointer< const Self > ConstPointer;
31 typedef _TVertex TVertex;
33 typedef _TIndex TIndex;
34 typedef _TIndexCompare TIndexCompare;
37 typedef std::map< TIndex, TVertex, TIndexCompare > TVertices;
38 typedef std::vector< TCost > TEdges;
39 typedef std::map< TIndex, TEdges, TIndexCompare > TMatrixRow;
40 typedef std::map< TIndex, TMatrixRow, TIndexCompare > TMatrix;
44 itkTypeMacro( Graph, itk::DataObject );
47 /*! \brief Iterators over vertices.
48 * These allow you to iterate over all of graph's vertices.
50 * Typical iteration should be done as:
54 * TGraph::TVertices::[const_]iterator vIt = g.BeginVertices( );
55 * for( ; vIt != g.EndVertices( ); ++vIt )
57 * vIt->first; --> this is the vertex's index <--
58 * vIt->second; --> this is the vertex's value <--
61 inline typename TVertices::iterator BeginVertices( )
62 { return( this->m_Vertices.begin( ) ); }
63 inline typename TVertices::iterator EndVertices( )
64 { return( this->m_Vertices.end( ) ); }
65 inline typename TVertices::const_iterator BeginVertices( ) const
66 { return( this->m_Vertices.begin( ) ); }
67 inline typename TVertices::const_iterator EndVertices( ) const
68 { return( this->m_Vertices.end( ) ); }
70 /*! \brief Iterators over edges.
71 * These allow you to iterate over all of graph's edges.
73 * Typical iteration should be done as:
77 * TGraph::TMatrix::[const_]iterator mIt = g.BeginEdgesRows( );
78 * for( ; mIt != g.EndEdgesRows( ); ++mIt )
80 * mIt->first; --> this is the row index. <--
81 * TGraph::TMatrixRow::[const_]iterator rIt = mIt->second.begin( );
82 * for( ; rIt != mIt->second.end( ); ++rIt )
84 * rIt->first; --> this is the column index.
85 * TGraph::TEdges::[const_]iterator eIt = rIt->second.begin( );
86 * for( ; eIt != rIt->second.end( ); ++eIt )
87 * *eIt; --> this is the cost between mIt->first and rIt->first
91 inline typename TMatrix::iterator BeginEdgesRows( )
92 { return( this->m_Matrix.begin( ) ); }
93 inline typename TMatrix::iterator EndEdgetsRows( )
94 { return( this->m_Matrix.end( ) ); }
95 inline typename TMatrix::const_iterator BeginEdgesRows( ) const
96 { return( this->m_Matrix.begin( ) ); }
97 inline typename TMatrix::const_iterator EndEdgesRows( ) const
98 { return( this->m_Matrix.end( ) ); }
100 /*! \brief Clear all vertices and edges.
104 /*! \brief Clear all edges.
106 inline void ClearEdges( )
107 { this->m_Matrix.clear( ); }
109 /*! \brief Vertex manipulation methods.
110 * Names are self-explanatory.
112 inline bool HasVertexIndex( const TIndex& i ) const
113 { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); }
114 inline void SetVertex( const TIndex& index, TVertex& vertex )
115 { this->m_Vertices[ index ] = vertex; }
116 inline TVertex& GetVertex( const TIndex& index )
117 { return( this->m_Vertices[ index ] ); }
118 inline const TVertex& GetVertex( const TIndex& index ) const
119 { return( this->m_Vertices[ index ] ); }
120 bool RenameVertex( const TIndex& old_index, const TIndex& new_index );
121 void RemoveVertex( const TIndex& index );
123 /*! \brief Edge manipulation methods.
124 * Names are self-explanatory.
126 inline void AddEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
127 { this->m_Matrix[ orig ][ dest ].push_back( cost ); }
128 TEdges& GetEdges( const TIndex& orig, const TIndex& dest );
129 const TEdges& GetEdges( const TIndex& orig, const TIndex& dest ) const;
130 bool HasEdge( const TIndex& orig, const TIndex& dest ) const;
131 void RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost );
132 void RemoveEdges( const TIndex& orig, const TIndex& dest );
134 /*! \brief Returns graph's sinks.
136 * A sink is a special vertex which does not have any "exiting" edges.
138 * @return Sinks ordered by their index.
140 std::set< TIndex, TIndexCompare > GetSinks( ) const;
147 // Purposely not implemented
148 Graph( const Self& other );
149 Self& operator=( const Self& other );
152 TVertices m_Vertices;
160 #ifndef ITK_MANUAL_INSTANTIATION
161 # include <cpExtensions/DataStructures/Graph.hxx>
162 #endif // ITK_MANUAL_INSTANTIATION
164 #endif // __cpExtensions__DataStructures__Graph__h__