1 #ifndef __cpExtensions__DataStructures__Graph__h__
2 #define __cpExtensions__DataStructures__Graph__h__
4 #include <cpExtensions/Config.h>
8 #include <itkLightObject.h>
9 #include <itkObjectFactory.h>
11 namespace cpExtensions
13 namespace DataStructures
15 /** \brief A generic graph with templated index types.
17 * @param V Vertex type.
19 * @param I Index type (it should be a strict weak ordering type).
21 template< class V, class C, class I = unsigned long >
23 : public itk::LightObject
27 typedef itk::LightObject Superclass;
28 typedef itk::SmartPointer< Self > Pointer;
29 typedef itk::SmartPointer< const Self > ConstPointer;
36 typedef std::map< TIndex, TVertex > TVertices;
37 typedef std::vector< TCost > TEdges;
38 typedef std::map< TIndex, TEdges > TMatrixRow;
39 typedef std::map< TIndex, TMatrixRow > TMatrix;
43 itkTypeMacro( Graph, itk::LightObject );
46 /*! \brief Iterators over vertices.
47 * These allow you to iterate over all of graph's vertices.
49 * Typical iteration should be done as:
53 * TGraph::TVertices::[const_]iterator vIt = g.BeginVertices( );
54 * for( ; vIt != g.EndVertices( ); ++vIt )
56 * vIt->first; --> this is the vertex's index <--
57 * vIt->second; --> this is the vertex's value <--
60 inline typename TVertices::iterator BeginVertices( )
61 { return( this->m_Vertices.begin( ) ); }
62 inline typename TVertices::iterator EndVertices( )
63 { return( this->m_Vertices.end( ) ); }
64 inline typename TVertices::const_iterator BeginVertices( ) const
65 { return( this->m_Vertices.begin( ) ); }
66 inline typename TVertices::const_iterator EndVertices( ) const
67 { return( this->m_Vertices.end( ) ); }
69 /*! \brief Iterators over edges.
70 * These allow you to iterate over all of graph's edges.
72 * Typical iteration should be done as:
76 * TGraph::TMatrix::[const_]iterator mIt = g.BeginEdgesRows( );
77 * for( ; mIt != g.EndEdgesRows( ); ++mIt )
79 * mIt->first; --> this is the row index. <--
80 * TGraph::TMatrixRow::[const_]iterator rIt = mIt->second.begin( );
81 * for( ; rIt != mIt->second.end( ); ++rIt )
83 * rIt->first; --> this is the column index.
84 * TGraph::TEdges::[const_]iterator eIt = rIt->second.begin( );
85 * for( ; eIt != rIt->second.end( ); ++eIt )
86 * *eIt; --> this is the cost between mIt->first and rIt->first
90 inline typename TMatrix::iterator BeginEdgesRows( )
91 { return( this->m_Matrix.begin( ) ); }
92 inline typename TMatrix::iterator EndEdgetsRows( )
93 { return( this->m_Matrix.end( ) ); }
94 inline typename TMatrix::const_iterator BeginEdgesRows( ) const
95 { return( this->m_Matrix.begin( ) ); }
96 inline typename TMatrix::const_iterator EndEdgesRows( ) const
97 { return( this->m_Matrix.end( ) ); }
99 /*! \brief Clear all vertices and edges.
103 /*! \brief Clear all edges.
105 inline void ClearEdges( )
106 { this->m_Matrix.clear( ); }
108 /*! \brief Vertex manipulation methods.
109 * Names are self-explanatory.
111 inline bool HasVertexIndex( const I& i ) const
112 { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); }
113 inline void SetVertex( const I& index, V& vertex )
114 { this->m_Vertices[ index ] = vertex; }
115 inline V& GetVertex( const I& index )
116 { return( this->m_Vertices[ index ] ); }
117 inline const V& GetVertex( const I& index ) const
118 { return( this->m_Vertices[ index ] ); }
119 bool RenameVertex( const I& old_index, const I& new_index );
120 void RemoveVertex( const I& index );
122 /*! \brief Edge manipulation methods.
123 * Names are self-explanatory.
125 inline void AddEdge( const I& orig, const I& dest, const C& cost )
126 { this->m_Matrix[ orig ][ dest ].push_back( cost ); }
127 inline TEdges& GetEdges( const I& orig, const I& dest )
128 { return( this->m_Matrix[ orig ][ dest ] ); }
129 inline const TEdges& GetEdges( const I& orig, const I& dest ) const
130 { return( this->m_Matrix[ orig ][ dest ] ); }
131 bool HasEdge( const I& orig, const I& dest ) const;
132 void RemoveEdge( const I& orig, const I& dest, const C& cost );
133 void RemoveEdges( const I& orig, const I& dest );
135 /*! \brief Returns graph's sinks.
137 * A sink is a special vertex which does not have any "exiting" edges.
139 * @return Sinks ordered by their index.
141 std::set< I > GetSinks( ) const;
148 // Purposely not implemented
149 Graph( const Self& other );
150 Self& operator=( const Self& other );
153 TVertices m_Vertices;
161 #ifndef ITK_MANUAL_INSTANTIATION
162 # include <cpExtensions/DataStructures/Graph.hxx>
163 #endif // ITK_MANUAL_INSTANTIATION
165 #endif // __cpExtensions__DataStructures__Graph__h__