1 #ifndef __cpExtensions__DataStructures__Graph__hxx__
2 #define __cpExtensions__DataStructures__Graph__hxx__
4 // -------------------------------------------------------------------------
5 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
6 void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
9 this->m_Vertices.clear( );
10 this->m_Matrix.clear( );
13 // -------------------------------------------------------------------------
14 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
15 bool cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
16 RenameVertex( const TIndex& old_index, const TIndex& new_index )
18 auto old_v = this->m_Vertices.find( old_index );
19 auto new_v = this->m_Vertices.find( new_index );
20 if( old_v != this->m_Vertices.end( ) && new_v == this->m_Vertices.end( ) )
23 this->m_Vertices[ new_index ] = old_v->second;
24 this->m_Vertices.erase( old_index );
27 auto mIt = this->m_Matrix.begin( );
28 auto found_row = this->m_Matrix.end( );
29 for( ; mIt != this->m_Matrix.end( ); ++mIt )
31 if( mIt->first == old_index )
34 auto rIt = mIt->second.begin( );
35 for( ; rIt != mIt->second.end( ); ++rIt )
37 if( mIt->first == old_index )
38 this->m_Matrix[ new_index ][ rIt->first ] = rIt->second;
39 else if( rIt->first == old_index )
40 this->m_Matrix[ mIt->first ][ new_index ] = rIt->second;
47 if( found_row != this->m_Matrix.end( ) )
48 this->m_Matrix.erase( found_row );
50 mIt = this->m_Matrix.begin( );
51 for( ; mIt != this->m_Matrix.end( ); ++mIt )
53 auto rIt = mIt->second.begin( );
54 while( rIt != mIt->second.end( ) )
56 if( rIt->first == old_index )
58 mIt->second.erase( rIt );
59 rIt = mIt->second.begin( );
73 // -------------------------------------------------------------------------
74 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
75 void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
76 RemoveVertex( const TIndex& index )
78 auto i = this->m_Vertices.find( index );
79 if( i != this->m_Vertices.end( ) )
82 this->m_Vertices.erase( i );
84 // Delete edges starting from given vertex
85 auto mIt = this->m_Matrix.find( index );
86 if( mIt != this->m_Matrix.end( ) )
87 this->m_Matrix.erase( mIt );
89 // Delete edges arriving to given vertex
90 mIt = this->m_Matrix.begin( );
91 for( ; mIt != this->m_Matrix.end( ); ++mIt )
93 auto rIt = mIt->second.begin( );
94 while( rIt != mIt->second.end( ) )
96 if( rIt->first == index )
98 mIt->second.erase( rIt );
99 rIt = mIt->second.begin( );
111 // -------------------------------------------------------------------------
112 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
114 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
116 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
117 GetEdges( const TIndex& orig, const TIndex& dest )
119 static TEdges null_edges;
120 auto o = this->m_Matrix.find( orig );
121 if( o != this->m_Matrix.find( orig ) )
123 auto d = o->second.find( dest );
124 if( d == o->second.end( ) )
127 return( null_edges );
135 return( null_edges );
140 // -------------------------------------------------------------------------
141 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
143 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
145 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
146 GetEdges( const TIndex& orig, const TIndex& dest ) const
148 static const TEdges null_edges;
149 auto o = this->m_Matrix.find( orig );
150 if( o != this->m_Matrix.find( orig ) )
152 auto d = o->second.find( dest );
153 if( d == o->second.end( ) )
154 return( null_edges );
159 return( null_edges );
162 // -------------------------------------------------------------------------
163 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
164 bool cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
165 HasEdge( const TIndex& orig, const TIndex& dest ) const
167 auto mIt = this->m_Matrix.find( orig );
168 if( mIt != this->m_Matrix.end( ) )
169 return( mIt->second.find( dest ) != mIt->second.end( ) );
174 // -------------------------------------------------------------------------
175 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
176 void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
177 RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
179 auto m = this->m_Matrix.find( orig );
180 if( m != this->m_Matrix.end( ) )
182 auto r = m->second.find( dest );
183 if( r != m->second.end( ) )
185 auto e = r->second.end( );
187 auto i = r->second.begin( );
188 i != r->second.end( ) && e == r->second.end( );
193 if( e != r->second.end( ) )
195 r->second.erase( e );
196 if( r->second.size( ) == 0 )
198 m->second.erase( r );
199 if( m->second.size( ) == 0 )
200 this->m_Matrix.erase( m );
211 // -------------------------------------------------------------------------
212 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
213 void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
214 RemoveEdges( const TIndex& orig, const TIndex& dest )
216 auto m = this->m_Matrix.find( orig );
217 if( m != this->m_Matrix.end( ) )
219 auto r = m->second.find( dest );
220 if( r != m->second.end( ) )
222 m->second.erase( r );
223 if( m->second.size( ) == 0 )
224 this->m_Matrix.erase( m );
232 // -------------------------------------------------------------------------
233 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
234 std::set< _TIndex, _TIndexCompare >
235 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
238 std::set< _TIndex, _TIndexCompare > sinks;
240 auto vIt = this->m_Vertices.begin( );
241 for( ; vIt != this->m_Vertices.end( ); ++vIt )
242 sinks.insert( vIt->first );
243 auto mIt = this->m_Matrix.begin( );
244 for( ; mIt != this->m_Matrix.end( ); ++mIt )
245 sinks.erase( mIt->first );
250 // -------------------------------------------------------------------------
251 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
252 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
258 // -------------------------------------------------------------------------
259 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
260 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
265 #endif // __cpExtensions__DataStructures__Graph__hxx__