lib/cpExtensions/DataStructures/Graph.hxx

   1 #ifndef __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
   2 #define __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
   3
   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 >::
   8 BeginVertices( )
   9 {
  10   return( this->m_Vertices.begin( ) );
  11 }
  12
  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 >::
  17 EndVertices( )
  18 {
  19   return( this->m_Vertices.end( ) );
  20 }
  21
  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
  27 {
  28   return( this->m_Vertices.begin( ) );
  29 }
  30
  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 >::
  35 EndVertices( ) const
  36 {
  37   return( this->m_Vertices.end( ) );
  38 }
  39
  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 >::
  44 BeginEdgesRows( )
  45 {
  46   return( this->m_Matrix.begin( ) );
  47 }
  48
  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 >::
  53 EndEdgetsRows( )
  54 {
  55   return( this->m_Matrix.end( ) );
  56 }
  57
  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
  63 {
  64   return( this->m_Matrix.begin( ) );
  65 }
  66
  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 >::
  71 EndEdgesRows( ) const
  72 {
  73   return( this->m_Matrix.end( ) );
  74 }
  75
  76 // -------------------------------------------------------------------------
  77 template< class V, class C, class I >
  78 void cpExtensions::DataStructures::Graph< V, C, I >::
  79 Clear( )
  80 {
  81   this->m_Vertices.clear( );
  82   this->m_Matrix.clear( );
  83 }
  84
  85 // -------------------------------------------------------------------------
  86 template< class V, class C, class I >
  87 void cpExtensions::DataStructures::Graph< V, C, I >::
  88 ClearEdges( )
  89 {
  90   this->m_Matrix.clear( );
  91 }
  92
  93 // -------------------------------------------------------------------------
  94 template< class V, class C, class I >
  95 bool cpExtensions::DataStructures::Graph< V, C, I >::
  96 HasVertexIndex( const I& index ) const
  97 {
  98   return( this->m_Vertices.find( index ) != this->m_Vertices.end( ) );
  99 }
 100
 101 // -------------------------------------------------------------------------
 102 template< class V, class C, class I >
 103 void cpExtensions::DataStructures::Graph< V, C, I >::
 104 SetVertex( const I& index, V& vertex )
 105 {
 106   this->m_Vertices[ index ] = vertex;
 107 }
 108
 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 )
 113 {
 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( ) )
 117   {
 118     // Replace vertex
 119     this->m_Vertices[ new_index ] = old_v->second;
 120     this->m_Vertices.erase( old_index );
 121
 122     // Duplicate edges
 123     auto mIt = this->m_Matrix.begin( );
 124     auto found_row = this->m_Matrix.end( );
 125     for( ; mIt != this->m_Matrix.end( ); ++mIt )
 126     {
 127       if( mIt->first == old_index )
 128         found_row = mIt;
 129
 130       auto rIt = mIt->second.begin( );
 131       for( ; rIt != mIt->second.end( ); ++rIt )
 132       {
 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;
 137
 138       } // rof
 139
 140     } // rof
 141
 142     // Delete old edges
 143     if( found_row != this->m_Matrix.end( ) )
 144       this->m_Matrix.erase( found_row );
 145
 146     mIt = this->m_Matrix.begin( );
 147     for( ; mIt != this->m_Matrix.end( ); ++mIt )
 148     {
 149       auto rIt = mIt->second.begin( );
 150       while( rIt != mIt->second.end( ) )
 151       {
 152         if( rIt->first == old_index )
 153         {
 154           mIt->second.erase( rIt );
 155           rIt = mIt->second.begin( );
 156         }
 157         else
 158           ++rIt;
 159
 160       } // elihw
 161
 162     } // rof
 163     return( true );
 164   }
 165   else
 166     return( false );
 167 }
 168
 169 // -------------------------------------------------------------------------
 170 template< class V, class C, class I >
 171 void cpExtensions::DataStructures::Graph< V, C, I >::
 172 RemoveVertex( const I& index )
 173 {
 174   auto i = this->m_Vertices.find( index );
 175   if( i != this->m_Vertices.end( ) )
 176   {
 177     // Delete vertex
 178     this->m_Vertices.erase( i );
 179
 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 );
 184
 185     // Delete edges arriving to given vertex
 186     mIt = this->m_Matrix.begin( );
 187     for( ; mIt != this->m_Matrix.end( ); ++mIt )
 188     {
 189       auto rIt = mIt->second.begin( );
 190       while( rIt != mIt->second.end( ) )
 191       {
 192         if( rIt->first == index )
 193         {
 194           mIt->second.erase( rIt );
 195           rIt = mIt->second.begin( );
 196         }
 197         else
 198           ++rIt;
 199
 200       } // elihw
 201
 202     } // rof
 203     return( true );
 204   }
 205   else
 206     return( false );
 207 }
 208
 209 // -------------------------------------------------------------------------
 210 template< class V, class C, class I >
 211 V& cpExtensions::DataStructures::Graph< V, C, I >::
 212 GetVertex( const I& index )
 213 {
 214   return( this->m_Vertices[ index ] );
 215 }
 216
 217 // -------------------------------------------------------------------------
 218 template< class V, class C, class I >
 219 const V& cpExtensions::DataStructures::Graph< V, C, I >::
 220 GetVertex( const I& index ) const
 221 {
 222   return( this->m_Vertices[ index ] );
 223 }
 224
 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
 229 {
 230   auto mIt = this->m_Matrix.find( orig );
 231   if( mIt != this->m_Matrix.end( ) )
 232     return( mIt->second.find( dest ) != mIt->second.end( ) );
 233   else
 234     return( false );
 235 }
 236
 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 )
 241 {
 242   this->m_Matrix[ orig ][ dest ].push_back( cost );
 243 }
 244
 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 )
 249 {
 250   auto m = this->m_Matrix.find( orig );
 251   if( m != this->m_Matrix.end( ) )
 252   {
 253     auto r = m->second.find( dest );
 254     if( r != m->second.end( ) )
 255     {
 256       auto e = std::find( r->second.begin( ), r->second.end( ), cost );
 257       if( e != r->second.end( ) )
 258       {
 259         r->second.erase( e );
 260         if( r->second.size( ) == 0 )
 261         {
 262           m->second.erase( r );
 263           if( m->second.size( ) == 0 )
 264             this->m_Matrix.erase( m );
 265
 266         } // fi
 267
 268       } // fi
 269
 270     } // fi
 271
 272   } // fi
 273 }
 274
 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 )
 279 {
 280   auto m = this->m_Matrix.find( orig );
 281   if( m != this->m_Matrix.end( ) )
 282   {
 283     auto r = m->second.find( dest );
 284     if( r != m->second.end( ) )
 285     {
 286       m->second.erase( r );
 287       if( m->second.size( ) == 0 )
 288         this->m_Matrix.erase( m );
 289
 290     } // fi
 291
 292   } // fi
 293
 294 }
 295
 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 )
 301 {
 302   return( this->m_Matrix[ orig ][ dest ] );
 303 }
 304
 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
 310 {
 311   return( this->m_Matrix[ orig ][ dest ] );
 312 }
 313
 314 // -------------------------------------------------------------------------
 315 template< class V, class C, class I >
 316 std::set< I > cpExtensions::DataStructures::Graph< V, C, I >::
 317 GetSinks( ) const
 318 {
 319   std::set< I > sinks;
 320
 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 );
 327
 328   return( sinks );
 329 }
 330
 331 // -------------------------------------------------------------------------
 332 template< class V, class C, class I >
 333 cpExtensions::DataStructures::Graph< V, C, I >::
 334 Graph( )
 335   : Superclass( )
 336 {
 337 }
 338
 339 // -------------------------------------------------------------------------
 340 template< class V, class C, class I >
 341 cpExtensions::DataStructures::Graph< V, C, I >::
 342 ~Graph( )
 343 {
 344 }
 345
 346 #endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
 347
 348 // eof - $RCSfile$