1 #ifndef __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__
2 #define __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__
7 #include <itkLightObject.h>
8 #include <itkObjectFactory.h>
10 namespace cpExtensions
12 namespace DataStructures
14 /** \brief A generic graph with templated index types.
16 * @param V Vertex type.
18 * @param I Index type (it should be a strict weak ordering type).
20 template< class V, class C, class I = unsigned long >
22 : public itk::LightObject
26 typedef itk::LightObject Superclass;
27 typedef itk::SmartPointer< Self > Pointer;
28 typedef itk::SmartPointer< const Self > ConstPointer;
35 typedef std::map< TIndex, TVertex > TVertices;
36 typedef std::vector< TCost > TEdges;
37 typedef std::map< TIndex, TEdges > TMatrixRow;
38 typedef std::map< TIndex, TMatrixRow > TMatrix;
42 itkTypeMacro( Graph, itk::LightObject );
45 /*! \brief Iterators over vertices.
46 * These allow you to iterate over all of graph's vertices.
48 * Typical iteration should be done as:
52 * TGraph::TVertices::[const_]iterator vIt = g.BeginVertices( );
53 * for( ; vIt != g.EndVertices( ); ++vIt )
55 * vIt->first; --> this is the vertex's index <--
56 * vIt->second; --> this is the vertex's value <--
59 inline typename TVertices::iterator BeginVertices( )
60 { return( this->m_Vertices.begin( ) ); }
61 inline typename TVertices::iterator EndVertices( )
62 { return( this->m_Vertices.end( ) ); }
63 inline typename TVertices::const_iterator BeginVertices( ) const
64 { return( this->m_Vertices.begin( ) ); }
65 inline typename TVertices::const_iterator EndVertices( ) const
66 { return( this->m_Vertices.end( ) ); }
68 /*! \brief Iterators over edges.
69 * These allow you to iterate over all of graph's edges.
71 * Typical iteration should be done as:
75 * TGraph::TMatrix::[const_]iterator mIt = g.BeginEdgesRows( );
76 * for( ; mIt != g.EndEdgesRows( ); ++mIt )
78 * mIt->first; --> this is the row index. <--
79 * TGraph::TMatrixRow::[const_]iterator rIt = mIt->second.begin( );
80 * for( ; rIt != mIt->second.end( ); ++rIt )
82 * rIt->first; --> this is the column index.
83 * TGraph::TEdges::[const_]iterator eIt = rIt->second.begin( );
84 * for( ; eIt != rIt->second.end( ); ++eIt )
85 * *eIt; --> this is the cost between mIt->first and rIt->first
89 inline typename TMatrix::iterator BeginEdgesRows( )
90 { return( this->m_Matrix.begin( ) ); }
91 inline typename TMatrix::iterator EndEdgetsRows( )
92 { return( this->m_Matrix.end( ) ); }
93 inline typename TMatrix::const_iterator BeginEdgesRows( ) const
94 { return( this->m_Matrix.begin( ) ); }
95 inline typename TMatrix::const_iterator EndEdgesRows( ) const
96 { return( this->m_Matrix.end( ) ); }
98 /*! \brief Clear all vertices and edges.
102 /*! \brief Clear all edges.
104 inline void ClearEdges( )
105 { this->m_Matrix.clear( ); }
107 /*! \brief Vertex manipulation methods.
108 * Names are self-explanatory.
110 inline bool HasVertexIndex( const I& i ) const
111 { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); }
112 inline void SetVertex( const I& index, V& vertex )
113 { this->m_Vertices[ index ] = vertex; }
114 inline V& GetVertex( const I& index )
115 { return( this->m_Vertices[ index ] ); }
116 inline const V& GetVertex( const I& index ) const
117 { return( this->m_Vertices[ index ] ); }
118 bool RenameVertex( const I& old_index, const I& new_index );
119 void RemoveVertex( const I& index );
121 /*! \brief Edge manipulation methods.
122 * Names are self-explanatory.
124 inline void AddEdge( const I& orig, const I& dest, const C& cost )
125 { this->m_Matrix[ orig ][ dest ].push_back( cost ); }
126 inline TEdges& GetEdges( const I& orig, const I& dest )
127 { return( this->m_Matrix[ orig ][ dest ] ); }
128 inline const TEdges& GetEdges( const I& orig, const I& dest ) const
129 { return( this->m_Matrix[ orig ][ dest ] ); }
130 bool HasEdge( const I& orig, const I& dest ) const;
131 void RemoveEdge( const I& orig, const I& dest, const C& cost );
132 void RemoveEdges( const I& orig, const I& 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< I > 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__