1 #ifndef __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
2 #define __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
4 // -------------------------------------------------------------------------
5 template< class V, class C, class I >
6 typename cpExtensions::DataStructures::Graph< V, C, I >::
7 TVertices::iterator cpExtensions::DataStructures::Graph< V, C, I >::
10 return( this->m_Vertices.begin( ) );
13 // -------------------------------------------------------------------------
14 template< class V, class C, class I >
15 typename cpExtensions::DataStructures::Graph< V, C, I >::
16 TVertices::iterator cpExtensions::DataStructures::Graph< V, C, I >::
19 return( this->m_Vertices.end( ) );
22 // -------------------------------------------------------------------------
23 template< class V, class C, class I >
24 typename cpExtensions::DataStructures::Graph< V, C, I >::
25 TVertices::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
26 BeginVertices( ) const
28 return( this->m_Vertices.begin( ) );
31 // -------------------------------------------------------------------------
32 template< class V, class C, class I >
33 typename cpExtensions::DataStructures::Graph< V, C, I >::
34 TVertices::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
37 return( this->m_Vertices.end( ) );
40 // -------------------------------------------------------------------------
41 template< class V, class C, class I >
42 typename cpExtensions::DataStructures::Graph< V, C, I >::
43 TMatrix::iterator cpExtensions::DataStructures::Graph< V, C, I >::
46 return( this->m_Matrix.begin( ) );
49 // -------------------------------------------------------------------------
50 template< class V, class C, class I >
51 typename cpExtensions::DataStructures::Graph< V, C, I >::
52 TMatrix::iterator cpExtensions::DataStructures::Graph< V, C, I >::
55 return( this->m_Matrix.end( ) );
58 // -------------------------------------------------------------------------
59 template< class V, class C, class I >
60 typename cpExtensions::DataStructures::Graph< V, C, I >::
61 TMatrix::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
62 BeginEdgesRows( ) const
64 return( this->m_Matrix.begin( ) );
67 // -------------------------------------------------------------------------
68 template< class V, class C, class I >
69 typename cpExtensions::DataStructures::Graph< V, C, I >::
70 TMatrix::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
73 return( this->m_Matrix.end( ) );
76 // -------------------------------------------------------------------------
77 template< class V, class C, class I >
78 void cpExtensions::DataStructures::Graph< V, C, I >::
81 this->m_Vertices.clear( );
82 this->m_Matrix.clear( );
85 // -------------------------------------------------------------------------
86 template< class V, class C, class I >
87 void cpExtensions::DataStructures::Graph< V, C, I >::
90 this->m_Matrix.clear( );
93 // -------------------------------------------------------------------------
94 template< class V, class C, class I >
95 bool cpExtensions::DataStructures::Graph< V, C, I >::
96 HasVertexIndex( const I& index ) const
98 return( this->m_Vertices.find( index ) != this->m_Vertices.end( ) );
101 // -------------------------------------------------------------------------
102 template< class V, class C, class I >
103 void cpExtensions::DataStructures::Graph< V, C, I >::
104 SetVertex( const I& index, V& vertex )
106 this->m_Vertices[ index ] = vertex;
109 // -------------------------------------------------------------------------
110 template< class V, class C, class I >
111 bool cpExtensions::DataStructures::Graph< V, C, I >::
112 RenameVertex( const I& old_index, const I& new_index )
114 auto old_v = this->m_Vertices.find( old_index );
115 auto new_v = this->m_Vertices.find( new_index );
116 if( old_v != this->m_Vertices.end( ) && new_v == this->m_Vertices.end( ) )
119 this->m_Vertices[ new_index ] = old_v->second;
120 this->m_Vertices.erase( old_index );
123 auto mIt = this->m_Matrix.begin( );
124 auto found_row = this->m_Matrix.end( );
125 for( ; mIt != this->m_Matrix.end( ); ++mIt )
127 if( mIt->first == old_index )
130 auto rIt = mIt->second.begin( );
131 for( ; rIt != mIt->second.end( ); ++rIt )
133 if( mIt->first == old_index )
134 this->m_Matrix[ new_index ][ rIt->first ] = rIt->second;
135 else if( rIt->first == old_index )
136 this->m_Matrix[ mIt->first ][ new_index ] = rIt->second;
143 if( found_row != this->m_Matrix.end( ) )
144 this->m_Matrix.erase( found_row );
146 mIt = this->m_Matrix.begin( );
147 for( ; mIt != this->m_Matrix.end( ); ++mIt )
149 auto rIt = mIt->second.begin( );
150 while( rIt != mIt->second.end( ) )
152 if( rIt->first == old_index )
154 mIt->second.erase( rIt );
155 rIt = mIt->second.begin( );
169 // -------------------------------------------------------------------------
170 template< class V, class C, class I >
171 void cpExtensions::DataStructures::Graph< V, C, I >::
172 RemoveVertex( const I& index )
174 auto i = this->m_Vertices.find( index );
175 if( i != this->m_Vertices.end( ) )
178 this->m_Vertices.erase( i );
180 // Delete edges starting from given vertex
181 auto mIt = this->m_Matrix.find( index );
182 if( mIt != this->m_Matrix.end( ) )
183 this->m_Matrix.erase( mIt );
185 // Delete edges arriving to given vertex
186 mIt = this->m_Matrix.begin( );
187 for( ; mIt != this->m_Matrix.end( ); ++mIt )
189 auto rIt = mIt->second.begin( );
190 while( rIt != mIt->second.end( ) )
192 if( rIt->first == index )
194 mIt->second.erase( rIt );
195 rIt = mIt->second.begin( );
209 // -------------------------------------------------------------------------
210 template< class V, class C, class I >
211 V& cpExtensions::DataStructures::Graph< V, C, I >::
212 GetVertex( const I& index )
214 return( this->m_Vertices[ index ] );
217 // -------------------------------------------------------------------------
218 template< class V, class C, class I >
219 const V& cpExtensions::DataStructures::Graph< V, C, I >::
220 GetVertex( const I& index ) const
222 return( this->m_Vertices[ index ] );
225 // -------------------------------------------------------------------------
226 template< class V, class C, class I >
227 bool cpExtensions::DataStructures::Graph< V, C, I >::
228 HasEdge( const I& orig, const I& dest ) const
230 auto mIt = this->m_Matrix.find( orig );
231 if( mIt != this->m_Matrix.end( ) )
232 return( mIt->second.find( dest ) != mIt->second.end( ) );
237 // -------------------------------------------------------------------------
238 template< class V, class C, class I >
239 void cpExtensions::DataStructures::Graph< V, C, I >::
240 AddEdge( const I& orig, const I& dest, const C& cost )
242 this->m_Matrix[ orig ][ dest ].push_back( cost );
245 // -------------------------------------------------------------------------
246 template< class V, class C, class I >
247 void cpExtensions::DataStructures::Graph< V, C, I >::
248 RemoveEdge( const I& orig, const I& dest, const C& cost )
250 auto m = this->m_Matrix.find( orig );
251 if( m != this->m_Matrix.end( ) )
253 auto r = m->second.find( dest );
254 if( r != m->second.end( ) )
256 auto e = std::find( r->second.begin( ), r->second.end( ), cost );
257 if( e != r->second.end( ) )
259 r->second.erase( e );
260 if( r->second.size( ) == 0 )
262 m->second.erase( r );
263 if( m->second.size( ) == 0 )
264 this->m_Matrix.erase( m );
275 // -------------------------------------------------------------------------
276 template< class V, class C, class I >
277 void cpExtensions::DataStructures::Graph< V, C, I >::
278 RemoveEdges( const I& orig, const I& dest )
280 auto m = this->m_Matrix.find( orig );
281 if( m != this->m_Matrix.end( ) )
283 auto r = m->second.find( dest );
284 if( r != m->second.end( ) )
286 m->second.erase( r );
287 if( m->second.size( ) == 0 )
288 this->m_Matrix.erase( m );
296 // -------------------------------------------------------------------------
297 template< class V, class C, class I >
298 typename cpExtensions::DataStructures::Graph< V, C, I >::
299 TEdges& cpExtensions::DataStructures::Graph< V, C, I >::
300 GetEdges( const I& orig, const I& dest )
302 return( this->m_Matrix[ orig ][ dest ] );
305 // -------------------------------------------------------------------------
306 template< class V, class C, class I >
307 const typename cpExtensions::DataStructures::Graph< V, C, I >::
308 TEdges& cpExtensions::DataStructures::Graph< V, C, I >::
309 GetEdges( const I& orig, const I& dest ) const
311 return( this->m_Matrix[ orig ][ dest ] );
314 // -------------------------------------------------------------------------
315 template< class V, class C, class I >
316 std::set< I > cpExtensions::DataStructures::Graph< V, C, I >::
321 auto vIt = this->m_Vertices.begin( );
322 for( ; vIt != this->m_Vertices.end( ); ++vIt )
323 sinks.insert( vIt->first );
324 auto mIt = this->m_Matrix.begin( );
325 for( ; mIt != this->m_Matrix.end( ); ++mIt )
326 sinks.erase( mIt->first );
331 // -------------------------------------------------------------------------
332 template< class V, class C, class I >
333 cpExtensions::DataStructures::Graph< V, C, I >::
339 // -------------------------------------------------------------------------
340 template< class V, class C, class I >
341 cpExtensions::DataStructures::Graph< V, C, I >::
346 #endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__