1 // =========================================================================
2 // @author Leonardo Florez Valencia
3 // @email florez-l@javeriana.edu.co
4 // =========================================================================
6 #ifndef __fpa__Base__Graph__hxx__
7 #define __fpa__Base__Graph__hxx__
9 // -------------------------------------------------------------------------
10 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
11 void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
14 this->m_Vertices.clear( );
15 this->m_Matrix.clear( );
18 // -------------------------------------------------------------------------
19 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
20 bool fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
21 RenameVertex( const TIndex& old_index, const TIndex& new_index )
23 auto old_v = this->m_Vertices.find( old_index );
24 auto new_v = this->m_Vertices.find( new_index );
25 if( old_v != this->m_Vertices.end( ) && new_v == this->m_Vertices.end( ) )
28 this->m_Vertices[ new_index ] = old_v->second;
29 this->m_Vertices.erase( old_index );
32 auto mIt = this->m_Matrix.begin( );
33 auto found_row = this->m_Matrix.end( );
34 for( ; mIt != this->m_Matrix.end( ); ++mIt )
36 if( mIt->first == old_index )
39 auto rIt = mIt->second.begin( );
40 for( ; rIt != mIt->second.end( ); ++rIt )
42 if( mIt->first == old_index )
43 this->m_Matrix[ new_index ][ rIt->first ] = rIt->second;
44 else if( rIt->first == old_index )
45 this->m_Matrix[ mIt->first ][ new_index ] = rIt->second;
52 if( found_row != this->m_Matrix.end( ) )
53 this->m_Matrix.erase( found_row );
55 mIt = this->m_Matrix.begin( );
56 for( ; mIt != this->m_Matrix.end( ); ++mIt )
58 auto rIt = mIt->second.begin( );
59 while( rIt != mIt->second.end( ) )
61 if( rIt->first == old_index )
63 mIt->second.erase( rIt );
64 rIt = mIt->second.begin( );
78 // -------------------------------------------------------------------------
79 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
80 void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
81 RemoveVertex( const TIndex& index )
83 auto i = this->m_Vertices.find( index );
84 if( i != this->m_Vertices.end( ) )
87 this->m_Vertices.erase( i );
89 // Delete edges starting from given vertex
90 auto mIt = this->m_Matrix.find( index );
91 if( mIt != this->m_Matrix.end( ) )
92 this->m_Matrix.erase( mIt );
94 // Delete edges arriving to given vertex
95 mIt = this->m_Matrix.begin( );
96 for( ; mIt != this->m_Matrix.end( ); ++mIt )
98 auto rIt = mIt->second.begin( );
99 while( rIt != mIt->second.end( ) )
101 if( rIt->first == index )
103 mIt->second.erase( rIt );
104 rIt = mIt->second.begin( );
116 // -------------------------------------------------------------------------
117 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
119 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
121 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
122 GetEdges( const TIndex& orig, const TIndex& dest )
124 static TEdges null_edges;
125 auto o = this->m_Matrix.find( orig );
126 if( o != this->m_Matrix.find( orig ) )
128 auto d = o->second.find( dest );
129 if( d == o->second.end( ) )
132 return( null_edges );
140 return( null_edges );
145 // -------------------------------------------------------------------------
146 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
148 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
150 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
151 GetEdges( const TIndex& orig, const TIndex& dest ) const
153 static const TEdges null_edges;
154 auto o = this->m_Matrix.find( orig );
155 if( o != this->m_Matrix.find( orig ) )
157 auto d = o->second.find( dest );
158 if( d == o->second.end( ) )
159 return( null_edges );
164 return( null_edges );
167 // -------------------------------------------------------------------------
168 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
169 bool fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
170 HasEdge( const TIndex& orig, const TIndex& dest ) const
172 auto mIt = this->m_Matrix.find( orig );
173 if( mIt != this->m_Matrix.end( ) )
174 return( mIt->second.find( dest ) != mIt->second.end( ) );
179 // -------------------------------------------------------------------------
180 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
181 void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
182 RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
184 auto m = this->m_Matrix.find( orig );
185 if( m != this->m_Matrix.end( ) )
187 auto r = m->second.find( dest );
188 if( r != m->second.end( ) )
190 auto e = r->second.end( );
192 auto i = r->second.begin( );
193 i != r->second.end( ) && e == r->second.end( );
198 if( e != r->second.end( ) )
200 r->second.erase( e );
201 if( r->second.size( ) == 0 )
203 m->second.erase( r );
204 if( m->second.size( ) == 0 )
205 this->m_Matrix.erase( m );
216 // -------------------------------------------------------------------------
217 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
218 void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
219 RemoveEdges( const TIndex& orig, const TIndex& dest )
221 auto m = this->m_Matrix.find( orig );
222 if( m != this->m_Matrix.end( ) )
224 auto r = m->second.find( dest );
225 if( r != m->second.end( ) )
227 m->second.erase( r );
228 if( m->second.size( ) == 0 )
229 this->m_Matrix.erase( m );
237 // -------------------------------------------------------------------------
238 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
239 std::set< _TIndex, _TIndexCompare >
240 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
243 std::set< _TIndex, _TIndexCompare > sinks;
245 auto vIt = this->m_Vertices.begin( );
246 for( ; vIt != this->m_Vertices.end( ); ++vIt )
247 sinks.insert( vIt->first );
248 auto mIt = this->m_Matrix.begin( );
249 for( ; mIt != this->m_Matrix.end( ); ++mIt )
250 sinks.erase( mIt->first );
255 // -------------------------------------------------------------------------
256 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
257 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
263 // -------------------------------------------------------------------------
264 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
265 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
270 #endif // __fpa__Base__Graph__hxx__