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 bool cpExtensions::DataStructures::Graph< V, C, I >::
  88 HasVertexIndex( const I& index ) const
  89 {
  90   return( this->m_Vertices.find( index ) != this->m_Vertices.end( ) );
  91 }
  92
  93 // -------------------------------------------------------------------------
  94 template< class V, class C, class I >
  95 void cpExtensions::DataStructures::Graph< V, C, I >::
  96 SetVertex( const I& index, V& vertex )
  97 {
  98   this->m_Vertices[ index ] = vertex;
  99 }
 100
 101 // -------------------------------------------------------------------------
 102 template< class V, class C, class I >
 103 bool cpExtensions::DataStructures::Graph< V, C, I >::
 104 RenameVertex( const I& old_index, const I& new_index )
 105 {
 106   auto old_v = this->m_Vertices.find( old_index );
 107   auto new_v = this->m_Vertices.find( new_index );
 108   if( old_v != this->m_Vertices.end( ) && new_v == this->m_Vertices.end( ) )
 109   {
 110     // Replace vertex
 111     typename TVertices::value_type new_entry( new_index, old_v->second );
 112     new_v = this->m_Vertices.insert( new_entry ).first;
 113     this->m_Vertices.erase( old_index );
 114
 115     // Duplicate edges
 116     auto mIt = this->m_Matrix.begin( );
 117     auto found_row = this->m_Matrix.end( );
 118     for( ; mIt != this->m_Matrix.end( ); ++mIt )
 119     {
 120       if( mIt->first == old_index )
 121         found_row = mIt;
 122
 123       auto rIt = mIt->second.begin( );
 124       for( ; rIt != mIt->second.end( ); ++rIt )
 125       {
 126         if( mIt->first == old_index )
 127           this->m_Matrix[ new_index ][ rIt->first ] = rIt->second;
 128         else if( rIt->first == old_index )
 129           this->m_Matrix[ mIt->first ][ new_index ] = rIt->second;
 130
 131       } // rof
 132
 133     } // rof
 134
 135     // Delete old edges
 136     if( found_row != this->m_Matrix.end( ) )
 137       this->m_Matrix.erase( found_row );
 138
 139     mIt = this->m_Matrix.begin( );
 140     for( ; mIt != this->m_Matrix.end( ); ++mIt )
 141     {
 142       auto rIt = mIt->second.begin( );
 143       while( rIt != mIt->second.end( ) )
 144       {
 145         if( rIt->first == old_index )
 146         {
 147           mIt->second.erase( rIt );
 148           rIt = mIt->second.begin( );
 149         }
 150         else
 151           ++rIt;
 152
 153       } // elihw
 154
 155     } // rof
 156     return( true );
 157   }
 158   else
 159     return( false );
 160 }
 161
 162 // -------------------------------------------------------------------------
 163 template< class V, class C, class I >
 164 void cpExtensions::DataStructures::Graph< V, C, I >::
 165 RemoveVertex( const I& index )
 166 {
 167   auto i = this->m_Vertices.find( index );
 168   if( i != this->m_Vertices.end( ) )
 169   {
 170     // Delete vertex
 171     this->m_Vertices.erase( i );
 172
 173     // Delete edges starting from given vertex
 174     auto mIt = this->m_Matrix.find( index );
 175     if( mIt != this->m_Matrix.end( ) )
 176       this->m_Matrix.erase( mIt );
 177
 178     // Delete edges arriving to given vertex
 179     mIt = this->m_Matrix.begin( );
 180     for( ; mIt != this->m_Matrix.end( ); ++mIt )
 181     {
 182       auto rIt = mIt->second.begin( );
 183       while( rIt != mIt->second.end( ) )
 184       {
 185         if( rIt->first == index )
 186         {
 187           mIt->second.erase( rIt );
 188           rIt = mIt->second.begin( );
 189         }
 190         else
 191           ++rIt;
 192
 193       } // elihw
 194
 195     } // rof
 196     return( true );
 197   }
 198   else
 199     return( false );
 200 }
 201
 202 // -------------------------------------------------------------------------
 203 template< class V, class C, class I >
 204 V& cpExtensions::DataStructures::Graph< V, C, I >::
 205 GetVertex( const I& index )
 206 {
 207   return( this->m_Vertices[ index ] );
 208 }
 209
 210 // -------------------------------------------------------------------------
 211 template< class V, class C, class I >
 212 const V& cpExtensions::DataStructures::Graph< V, C, I >::
 213 GetVertex( const I& index ) const
 214 {
 215   return( this->m_Vertices[ index ] );
 216 }
 217
 218 // -------------------------------------------------------------------------
 219 template< class V, class C, class I >
 220 void cpExtensions::DataStructures::Graph< V, C, I >::
 221 AddConnection( const I& orig, const I& dest, const C& cost )
 222 {
 223   this->m_Matrix[ orig ][ dest ].push_back( cost );
 224 }
 225
 226 // -------------------------------------------------------------------------
 227 template< class V, class C, class I >
 228 void cpExtensions::DataStructures::Graph< V, C, I >::
 229 RemoveConnection( const I& orig, const I& dest, const C& cost )
 230 {
 231   auto m = this->m_Matrix.find( orig );
 232   if( m != this->m_Matrix.end( ) )
 233   {
 234     auto r = m->second.find( dest );
 235     if( r != m->second.end( ) )
 236     {
 237       auto e = std::find( r->second.begin( ), r->second.end( ), cost );
 238       if( e != r->second.end( ) )
 239       {
 240         r->second.erase( e );
 241         if( r->second.size( ) == 0 )
 242         {
 243           m->second.erase( r );
 244           if( m->second.size( ) == 0 )
 245             this->m_Matrix.erase( m );
 246
 247         } // fi
 248
 249       } // fi
 250
 251     } // fi
 252
 253   } // fi
 254 }
 255
 256 // -------------------------------------------------------------------------
 257 template< class V, class C, class I >
 258 std::set< I > cpExtensions::DataStructures::Graph< V, C, I >::
 259 GetSinks( ) const
 260 {
 261   std::set< I > sinks;
 262
 263   auto vIt = this->m_Vertices.begin( );
 264   for( ; vIt != this->m_Vertices.end( ); ++vIt )
 265     sinks.insert( vIt->first );
 266   auto mIt = this->m_Matrix.begin( );
 267   for( ; mIt != this->m_Matrix.end( ); ++mIt )
 268     sinks.erase( mIt->first );
 269
 270   return( sinks );
 271 }
 272
 273 // -------------------------------------------------------------------------
 274 template< class V, class C, class I >
 275 cpExtensions::DataStructures::Graph< V, C, I >::
 276 Graph( )
 277   : Superclass( )
 278 {
 279 }
 280
 281 // -------------------------------------------------------------------------
 282 template< class V, class C, class I >
 283 cpExtensions::DataStructures::Graph< V, C, I >::
 284 ~Graph( )
 285 {
 286 }
 287
 288 #endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
 289
 290 // eof - $RCSfile$