1 // =========================================================================
2 // @author Leonardo Florez Valencia
3 // @email florez-l@javeriana.edu.co
4 // =========================================================================
5 #ifndef __fpa__DataStructures__Graph__hxx__
6 #define __fpa__DataStructures__Graph__hxx__
8 // -------------------------------------------------------------------------
9 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
10 void fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
13 this->m_Vertices.clear( );
14 this->m_Matrix.clear( );
17 // -------------------------------------------------------------------------
18 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
19 bool fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
20 RenameVertex( const TIndex& old_index, const TIndex& new_index )
22 typename TVertices::iterator old_v = this->m_Vertices.find( old_index );
23 typename TVertices::iterator new_v = this->m_Vertices.find( new_index );
24 if( old_v != this->m_Vertices.end( ) && new_v == this->m_Vertices.end( ) )
27 this->m_Vertices[ new_index ] = old_v->second;
28 this->m_Vertices.erase( old_index );
31 typename TMatrix::iterator mIt = this->m_Matrix.begin( );
32 typename TMatrix::iterator found_row = this->m_Matrix.end( );
33 for( ; mIt != this->m_Matrix.end( ); ++mIt )
35 if( mIt->first == old_index )
38 typename TMatrixRow::iterator rIt = mIt->second.begin( );
39 for( ; rIt != mIt->second.end( ); ++rIt )
41 if( mIt->first == old_index )
42 this->m_Matrix[ new_index ][ rIt->first ] = rIt->second;
43 else if( rIt->first == old_index )
44 this->m_Matrix[ mIt->first ][ new_index ] = rIt->second;
51 if( found_row != this->m_Matrix.end( ) )
52 this->m_Matrix.erase( found_row );
54 mIt = this->m_Matrix.begin( );
55 for( ; mIt != this->m_Matrix.end( ); ++mIt )
57 typename TMatrixRow::iterator rIt = mIt->second.begin( );
58 while( rIt != mIt->second.end( ) )
60 if( rIt->first == old_index )
62 mIt->second.erase( rIt );
63 rIt = mIt->second.begin( );
77 // -------------------------------------------------------------------------
78 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
79 void fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
80 RemoveVertex( const TIndex& index )
82 typename TVertices::iterator i = this->m_Vertices.find( index );
83 if( i != this->m_Vertices.end( ) )
86 this->m_Vertices.erase( i );
88 // Delete edges starting from given vertex
89 typename TMatrix::iterator mIt = this->m_Matrix.find( index );
90 if( mIt != this->m_Matrix.end( ) )
91 this->m_Matrix.erase( mIt );
93 // Delete edges arriving to given vertex
94 mIt = this->m_Matrix.begin( );
95 for( ; mIt != this->m_Matrix.end( ); ++mIt )
97 typename TMatrixRow::iterator rIt = mIt->second.begin( );
98 while( rIt != mIt->second.end( ) )
100 if( rIt->first == index )
102 mIt->second.erase( rIt );
103 rIt = mIt->second.begin( );
115 // -------------------------------------------------------------------------
116 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
118 fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
120 fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
121 GetEdges( const TIndex& orig, const TIndex& dest )
123 static TEdges null_edges;
124 typename TMatrix::iterator o = this->m_Matrix.find( orig );
125 if( o != this->m_Matrix.find( orig ) )
127 typename TMatrixRow::iterator d = o->second.find( dest );
128 if( d == o->second.end( ) )
131 return( null_edges );
139 return( null_edges );
144 // -------------------------------------------------------------------------
145 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
147 fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
149 fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
150 GetEdges( const TIndex& orig, const TIndex& dest ) const
152 static const TEdges null_edges;
153 typename TMatrix::iterator o = this->m_Matrix.find( orig );
154 if( o != this->m_Matrix.find( orig ) )
156 typename TMatrixRow::iterator d = o->second.find( dest );
157 if( d == o->second.end( ) )
158 return( null_edges );
163 return( null_edges );
166 // -------------------------------------------------------------------------
167 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
168 bool fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
169 HasEdge( const TIndex& orig, const TIndex& dest ) const
171 typename TMatrix::const_iterator mIt = this->m_Matrix.find( orig );
172 if( mIt != this->m_Matrix.end( ) )
173 return( mIt->second.find( dest ) != mIt->second.end( ) );
178 // -------------------------------------------------------------------------
179 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
180 void fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
181 RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
183 typename TMatrix::iterator m = this->m_Matrix.find( orig );
184 if( m != this->m_Matrix.end( ) )
186 typename TMatrixRow::iterator r = m->second.find( dest );
187 if( r != m->second.end( ) )
189 typename TEdges::iterator e = r->second.end( );
191 typename TEdges::iterator i = r->second.begin( );
192 i != r->second.end( ) && e == r->second.end( );
197 if( e != r->second.end( ) )
199 r->second.erase( e );
200 if( r->second.size( ) == 0 )
202 m->second.erase( r );
203 if( m->second.size( ) == 0 )
204 this->m_Matrix.erase( m );
215 // -------------------------------------------------------------------------
216 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
217 void fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
218 RemoveEdges( const TIndex& orig, const TIndex& dest )
220 typename TMatrix::iterator m = this->m_Matrix.find( orig );
221 if( m != this->m_Matrix.end( ) )
223 typename TMatrixRow::iterator r = m->second.find( dest );
224 if( r != m->second.end( ) )
226 m->second.erase( r );
227 if( m->second.size( ) == 0 )
228 this->m_Matrix.erase( m );
236 // -------------------------------------------------------------------------
237 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
238 std::set< _TIndex, _TIndexCompare >
239 fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
242 std::set< _TIndex, _TIndexCompare > sinks;
244 typename TVertices::iterator vIt = this->m_Vertices.begin( );
245 for( ; vIt != this->m_Vertices.end( ); ++vIt )
246 sinks.insert( vIt->first );
247 typename TMatrix::iterator mIt = this->m_Matrix.begin( );
248 for( ; mIt != this->m_Matrix.end( ); ++mIt )
249 sinks.erase( mIt->first );
254 // -------------------------------------------------------------------------
255 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
256 fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
262 // -------------------------------------------------------------------------
263 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
264 fpa::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
269 #endif // __fpa__DataStructures__Graph__hxx__