1 // =========================================================================
2 // @author Leonardo Florez Valencia
3 // @email florez-l@javeriana.edu.co
4 // =========================================================================
5 #ifndef __fpa__DataStructures__Graph__h__
6 #define __fpa__DataStructures__Graph__h__
11 #include <itkDataObject.h>
12 #include <itkObjectFactory.h>
16 namespace DataStructures
18 /** \brief A generic graph with templated index types.
20 * @param _TVertex Vertex type.
21 * @param _TCost Cost type.
22 * @param _TIndex Index type (it should be a strict weak ordering type).
24 template< class _TVertex, class _TCost, class _TIndex = unsigned long, class _TIndexCompare = std::less< _TIndex > >
26 : public itk::DataObject
30 typedef itk::DataObject Superclass;
31 typedef itk::SmartPointer< Self > Pointer;
32 typedef itk::SmartPointer< const Self > ConstPointer;
34 typedef _TVertex TVertex;
36 typedef _TIndex TIndex;
37 typedef _TIndexCompare TIndexCompare;
40 typedef std::map< TIndex, TVertex, TIndexCompare > TVertices;
41 typedef std::vector< TCost > TEdges;
42 typedef std::map< TIndex, TEdges, TIndexCompare > TMatrixRow;
43 typedef std::map< TIndex, TMatrixRow, TIndexCompare > TMatrix;
47 itkTypeMacro( Graph, itk::DataObject );
50 /*! \brief Iterators over vertices.
51 * These allow you to iterate over all of graph's vertices.
53 * Typical iteration should be done as:
57 * TGraph::TVertices::[const_]iterator vIt = g.BeginVertices( );
58 * for( ; vIt != g.EndVertices( ); ++vIt )
60 * vIt->first; --> this is the vertex's index <--
61 * vIt->second; --> this is the vertex's value <--
64 inline typename TVertices::iterator BeginVertices( )
65 { return( this->m_Vertices.begin( ) ); }
66 inline typename TVertices::iterator EndVertices( )
67 { return( this->m_Vertices.end( ) ); }
68 inline typename TVertices::const_iterator BeginVertices( ) const
69 { return( this->m_Vertices.begin( ) ); }
70 inline typename TVertices::const_iterator EndVertices( ) const
71 { return( this->m_Vertices.end( ) ); }
73 /*! \brief Iterators over edges.
74 * These allow you to iterate over all of graph's edges.
76 * Typical iteration should be done as:
80 * TGraph::TMatrix::[const_]iterator mIt = g.BeginEdgesRows( );
81 * for( ; mIt != g.EndEdgesRows( ); ++mIt )
83 * mIt->first; --> this is the row index. <--
84 * TGraph::TMatrixRow::[const_]iterator rIt = mIt->second.begin( );
85 * for( ; rIt != mIt->second.end( ); ++rIt )
87 * rIt->first; --> this is the column index.
88 * TGraph::TEdges::[const_]iterator eIt = rIt->second.begin( );
89 * for( ; eIt != rIt->second.end( ); ++eIt )
90 * *eIt; --> this is the cost between mIt->first and rIt->first
94 inline typename TMatrix::iterator BeginEdgesRows( )
95 { return( this->m_Matrix.begin( ) ); }
96 inline typename TMatrix::iterator EndEdgetsRows( )
97 { return( this->m_Matrix.end( ) ); }
98 inline typename TMatrix::const_iterator BeginEdgesRows( ) const
99 { return( this->m_Matrix.begin( ) ); }
100 inline typename TMatrix::const_iterator EndEdgesRows( ) const
101 { return( this->m_Matrix.end( ) ); }
103 /*! \brief Clear all vertices and edges.
107 /*! \brief Clear all edges.
109 inline void ClearEdges( )
110 { this->m_Matrix.clear( ); }
112 /*! \brief Vertex manipulation methods.
113 * Names are self-explanatory.
115 inline bool HasVertexIndex( const TIndex& i ) const
116 { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); }
117 inline void SetVertex( const TIndex& index, TVertex& vertex )
118 { this->m_Vertices[ index ] = vertex; }
119 inline TVertex& GetVertex( const TIndex& index )
120 { return( this->m_Vertices[ index ] ); }
121 inline const TVertex& GetVertex( const TIndex& index ) const
122 { return( this->m_Vertices[ index ] ); }
123 bool RenameVertex( const TIndex& old_index, const TIndex& new_index );
124 void RemoveVertex( const TIndex& index );
126 /*! \brief Edge manipulation methods.
127 * Names are self-explanatory.
129 inline void AddEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
130 { this->m_Matrix[ orig ][ dest ].push_back( cost ); }
131 TEdges& GetEdges( const TIndex& orig, const TIndex& dest );
132 const TEdges& GetEdges( const TIndex& orig, const TIndex& dest ) const;
133 bool HasEdge( const TIndex& orig, const TIndex& dest ) const;
134 void RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost );
135 void RemoveEdges( const TIndex& orig, const TIndex& dest );
137 /*! \brief Returns graph's sinks.
139 * A sink is a special vertex which does not have any "exiting" edges.
141 * @return Sinks ordered by their index.
143 std::set< TIndex, TIndexCompare > GetSinks( ) const;
150 // Purposely not implemented
151 Graph( const Self& other );
152 Self& operator=( const Self& other );
155 TVertices m_Vertices;
163 #ifndef ITK_MANUAL_INSTANTIATION
164 # include <fpa/DataStructures/Graph.hxx>
165 #endif // ITK_MANUAL_INSTANTIATION
166 #endif // __fpa__DataStructures__Graph__h__