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 V& cpExtensions::DataStructures::Graph< V, C, I >::
 165 GetVertex( const I& index )
 166 {
 167   return( this->m_Vertices[ index ] );
 168 }
 169
 170 // -------------------------------------------------------------------------
 171 template< class V, class C, class I >
 172 const V& cpExtensions::DataStructures::Graph< V, C, I >::
 173 GetVertex( const I& index ) const
 174 {
 175   return( this->m_Vertices[ index ] );
 176 }
 177
 178 // -------------------------------------------------------------------------
 179 template< class V, class C, class I >
 180 void cpExtensions::DataStructures::Graph< V, C, I >::
 181 AddConnection( const I& orig, const I& dest, const C& cost )
 182 {
 183   this->m_Matrix[ orig ][ dest ].push_back( cost );
 184 }
 185
 186 // -------------------------------------------------------------------------
 187 template< class V, class C, class I >
 188 std::set< I > cpExtensions::DataStructures::Graph< V, C, I >::
 189 GetSinks( ) const
 190 {
 191   std::set< I > sinks;
 192
 193   auto vIt = this->m_Vertices.begin( );
 194   for( ; vIt != this->m_Vertices.end( ); ++vIt )
 195     sinks.insert( vIt->first );
 196   auto mIt = this->m_Matrix.begin( );
 197   for( ; mIt != this->m_Matrix.end( ); ++mIt )
 198     sinks.erase( mIt->first );
 199
 200   return( sinks );
 201 }
 202
 203 // -------------------------------------------------------------------------
 204 template< class V, class C, class I >
 205 cpExtensions::DataStructures::Graph< V, C, I >::
 206 Graph( )
 207   : Superclass( )
 208 {
 209 }
 210
 211 // -------------------------------------------------------------------------
 212 template< class V, class C, class I >
 213 cpExtensions::DataStructures::Graph< V, C, I >::
 214 ~Graph( )
 215 {
 216 }
 217
 218 #endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
 219
 220 // eof - $RCSfile$