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 typename TVertices::iterator BeginVertices( );
60 typename TVertices::iterator EndVertices( );
61 typename TVertices::const_iterator BeginVertices( ) const;
62 typename TVertices::const_iterator EndVertices( ) const;
64 /*! \brief Iterators over edges.
65 * These allow you to iterate over all of graph's edges.
67 * Typical iteration should be done as:
71 * TGraph::TMatrix::[const_]iterator mIt = g.BeginEdgesRows( );
72 * for( ; mIt != g.EndEdgesRows( ); ++mIt )
74 * mIt->first; --> this is the row index. <--
75 * TGraph::TMatrixRow::[const_]iterator rIt = mIt->second.begin( );
76 * for( ; rIt != mIt->second.end( ); ++rIt )
78 * rIt->first; --> this is the column index.
79 * TGraph::TEdges::[const_]iterator eIt = rIt->second.begin( );
80 * for( ; eIt != rIt->second.end( ); ++eIt )
81 * *eIt; --> this is the cost between mIt->first and rIt->first
85 typename TMatrix::iterator BeginEdgesRows( );
86 typename TMatrix::iterator EndEdgetsRows( );
87 typename TMatrix::const_iterator BeginEdgesRows( ) const;
88 typename TMatrix::const_iterator EndEdgesRows( ) const;
90 /*! \brief Clear all vertices and edges.
94 /*! \brief Clear all edges.
98 /*! \brief Vertex manipulation methods.
99 * Names are self-explanatory.
101 bool HasVertexIndex( const I& index ) const;
102 void SetVertex( const I& index, V& vertex );
103 bool RenameVertex( const I& old_index, const I& new_index );
104 void RemoveVertex( const I& index );
105 V& GetVertex( const I& index );
106 const V& GetVertex( const I& index ) const;
108 /*! \brief Edge manipulation methods.
109 * Names are self-explanatory.
111 bool HasEdge( const I& orig, const I& dest ) const;
112 void AddEdge( const I& orig, const I& dest, const C& cost );
113 void RemoveEdge( const I& orig, const I& dest, const C& cost );
114 void RemoveEdges( const I& orig, const I& dest );
115 TEdges& GetEdges( const I& orig, const I& dest );
116 const TEdges& GetEdges( const I& orig, const I& dest ) const;
118 /*! \brief Returns graph's sinks.
120 * A sink is a special vertex which does not have any "exiting" edges.
122 * @return Sinks ordered by their index.
124 std::set< I > GetSinks( ) const;
131 // Purposely not implemented
132 Graph( const Self& other );
133 Self& operator=( const Self& other );
136 TVertices m_Vertices;
144 #ifndef ITK_MANUAL_INSTANTIATION
145 #include <cpExtensions/DataStructures/Graph.hxx>
146 #endif // ITK_MANUAL_INSTANTIATION
148 #endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__