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 void cpExtensions::DataStructures::Graph< V, C, I >::
   7 Clear( )
   8 {
   9   this->m_Vertices.clear( );
  10   this->m_Matrix.clear( );
  11 }
  12
  13 // -------------------------------------------------------------------------
  14 template< class V, class C, class I >
  15 bool cpExtensions::DataStructures::Graph< V, C, I >::
  16 RenameVertex( const I& old_index, const I& new_index )
  17 {
  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( ) )
  21   {
  22     // Replace vertex
  23     this->m_Vertices[ new_index ] = old_v->second;
  24     this->m_Vertices.erase( old_index );
  25
  26     // Duplicate edges
  27     auto mIt = this->m_Matrix.begin( );
  28     auto found_row = this->m_Matrix.end( );
  29     for( ; mIt != this->m_Matrix.end( ); ++mIt )
  30     {
  31       if( mIt->first == old_index )
  32         found_row = mIt;
  33
  34       auto rIt = mIt->second.begin( );
  35       for( ; rIt != mIt->second.end( ); ++rIt )
  36       {
  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;
  41
  42       } // rof
  43
  44     } // rof
  45
  46     // Delete old edges
  47     if( found_row != this->m_Matrix.end( ) )
  48       this->m_Matrix.erase( found_row );
  49
  50     mIt = this->m_Matrix.begin( );
  51     for( ; mIt != this->m_Matrix.end( ); ++mIt )
  52     {
  53       auto rIt = mIt->second.begin( );
  54       while( rIt != mIt->second.end( ) )
  55       {
  56         if( rIt->first == old_index )
  57         {
  58           mIt->second.erase( rIt );
  59           rIt = mIt->second.begin( );
  60         }
  61         else
  62           ++rIt;
  63
  64       } // elihw
  65
  66     } // rof
  67     return( true );
  68   }
  69   else
  70     return( false );
  71 }
  72
  73 // -------------------------------------------------------------------------
  74 template< class V, class C, class I >
  75 void cpExtensions::DataStructures::Graph< V, C, I >::
  76 RemoveVertex( const I& index )
  77 {
  78   auto i = this->m_Vertices.find( index );
  79   if( i != this->m_Vertices.end( ) )
  80   {
  81     // Delete vertex
  82     this->m_Vertices.erase( i );
  83
  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 );
  88
  89     // Delete edges arriving to given vertex
  90     mIt = this->m_Matrix.begin( );
  91     for( ; mIt != this->m_Matrix.end( ); ++mIt )
  92     {
  93       auto rIt = mIt->second.begin( );
  94       while( rIt != mIt->second.end( ) )
  95       {
  96         if( rIt->first == index )
  97         {
  98           mIt->second.erase( rIt );
  99           rIt = mIt->second.begin( );
 100         }
 101         else
 102           ++rIt;
 103
 104       } // elihw
 105
 106     } // rof
 107     return( true );
 108   }
 109   else
 110     return( false );
 111 }
 112
 113 // -------------------------------------------------------------------------
 114 template< class V, class C, class I >
 115 bool cpExtensions::DataStructures::Graph< V, C, I >::
 116 HasEdge( const I& orig, const I& dest ) const
 117 {
 118   auto mIt = this->m_Matrix.find( orig );
 119   if( mIt != this->m_Matrix.end( ) )
 120     return( mIt->second.find( dest ) != mIt->second.end( ) );
 121   else
 122     return( false );
 123 }
 124
 125 // -------------------------------------------------------------------------
 126 template< class V, class C, class I >
 127 void cpExtensions::DataStructures::Graph< V, C, I >::
 128 RemoveEdge( const I& orig, const I& dest, const C& cost )
 129 {
 130   auto m = this->m_Matrix.find( orig );
 131   if( m != this->m_Matrix.end( ) )
 132   {
 133     auto r = m->second.find( dest );
 134     if( r != m->second.end( ) )
 135     {
 136       auto e = std::find( r->second.begin( ), r->second.end( ), cost );
 137       if( e != r->second.end( ) )
 138       {
 139         r->second.erase( e );
 140         if( r->second.size( ) == 0 )
 141         {
 142           m->second.erase( r );
 143           if( m->second.size( ) == 0 )
 144             this->m_Matrix.erase( m );
 145
 146         } // fi
 147
 148       } // fi
 149
 150     } // fi
 151
 152   } // fi
 153 }
 154
 155 // -------------------------------------------------------------------------
 156 template< class V, class C, class I >
 157 void cpExtensions::DataStructures::Graph< V, C, I >::
 158 RemoveEdges( const I& orig, const I& dest )
 159 {
 160   auto m = this->m_Matrix.find( orig );
 161   if( m != this->m_Matrix.end( ) )
 162   {
 163     auto r = m->second.find( dest );
 164     if( r != m->second.end( ) )
 165     {
 166       m->second.erase( r );
 167       if( m->second.size( ) == 0 )
 168         this->m_Matrix.erase( m );
 169
 170     } // fi
 171
 172   } // fi
 173
 174 }
 175
 176 // -------------------------------------------------------------------------
 177 template< class V, class C, class I >
 178 std::set< I > cpExtensions::DataStructures::Graph< V, C, I >::
 179 GetSinks( ) const
 180 {
 181   std::set< I > sinks;
 182
 183   auto vIt = this->m_Vertices.begin( );
 184   for( ; vIt != this->m_Vertices.end( ); ++vIt )
 185     sinks.insert( vIt->first );
 186   auto mIt = this->m_Matrix.begin( );
 187   for( ; mIt != this->m_Matrix.end( ); ++mIt )
 188     sinks.erase( mIt->first );
 189
 190   return( sinks );
 191 }
 192
 193 // -------------------------------------------------------------------------
 194 template< class V, class C, class I >
 195 cpExtensions::DataStructures::Graph< V, C, I >::
 196 Graph( )
 197   : Superclass( )
 198 {
 199 }
 200
 201 // -------------------------------------------------------------------------
 202 template< class V, class C, class I >
 203 cpExtensions::DataStructures::Graph< V, C, I >::
 204 ~Graph( )
 205 {
 206 }
 207
 208 #endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
 209
 210 // eof - $RCSfile$