lib/cpExtensions/DataStructures/Graph.hxx

   1 #ifndef __cpExtensions__DataStructures__Graph__hxx__
   2 #define __cpExtensions__DataStructures__Graph__hxx__
   3
   4 // -------------------------------------------------------------------------
   5 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
   6 void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
   7 Clear( )
   8 {
   9   this->m_Vertices.clear( );
  10   this->m_Matrix.clear( );
  11 }
  12
  13 // -------------------------------------------------------------------------
  14 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
  15 bool cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
  16 RenameVertex( const TIndex& old_index, const TIndex& 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 _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
  75 void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
  76 RemoveVertex( const TIndex& 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
 108   } // fi
 109 }
 110
 111 // -------------------------------------------------------------------------
 112 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 113 typename
 114 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 115 TEdges&
 116 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 117 GetEdges( const TIndex& orig, const TIndex& dest )
 118 {
 119   static TEdges null_edges;
 120   auto o = this->m_Matrix.find( orig );
 121   if( o != this->m_Matrix.find( orig ) )
 122   {
 123     auto d = o->second.find( dest );
 124     if( d == o->second.end( ) )
 125     {
 126       null_edges.clear( );
 127       return( null_edges );
 128     }
 129     else
 130       return( d->second );
 131   }
 132   else
 133   {
 134     null_edges.clear( );
 135     return( null_edges );
 136
 137   } // fi
 138 }
 139
 140 // -------------------------------------------------------------------------
 141 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 142 const typename
 143 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 144 TEdges&
 145 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 146 GetEdges( const TIndex& orig, const TIndex& dest ) const
 147 {
 148   static const TEdges null_edges;
 149   auto o = this->m_Matrix.find( orig );
 150   if( o != this->m_Matrix.find( orig ) )
 151   {
 152     auto d = o->second.find( dest );
 153     if( d == o->second.end( ) )
 154       return( null_edges );
 155     else
 156       return( d->second );
 157   }
 158   else
 159     return( null_edges );
 160 }
 161
 162 // -------------------------------------------------------------------------
 163 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 164 bool cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 165 HasEdge( const TIndex& orig, const TIndex& dest ) const
 166 {
 167   auto mIt = this->m_Matrix.find( orig );
 168   if( mIt != this->m_Matrix.end( ) )
 169     return( mIt->second.find( dest ) != mIt->second.end( ) );
 170   else
 171     return( false );
 172 }
 173
 174 // -------------------------------------------------------------------------
 175 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 176 void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 177 RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
 178 {
 179   auto m = this->m_Matrix.find( orig );
 180   if( m != this->m_Matrix.end( ) )
 181   {
 182     auto r = m->second.find( dest );
 183     if( r != m->second.end( ) )
 184     {
 185       auto e = r->second.end( );
 186       for(
 187         auto i = r->second.begin( );
 188         i != r->second.end( ) && e == r->second.end( );
 189         ++i
 190         )
 191         if( *i == cost )
 192           e = i;
 193       if( e != r->second.end( ) )
 194       {
 195         r->second.erase( e );
 196         if( r->second.size( ) == 0 )
 197         {
 198           m->second.erase( r );
 199           if( m->second.size( ) == 0 )
 200             this->m_Matrix.erase( m );
 201
 202         } // fi
 203
 204       } // fi
 205
 206     } // fi
 207
 208   } // fi
 209 }
 210
 211 // -------------------------------------------------------------------------
 212 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 213 void cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 214 RemoveEdges( const TIndex& orig, const TIndex& dest )
 215 {
 216   auto m = this->m_Matrix.find( orig );
 217   if( m != this->m_Matrix.end( ) )
 218   {
 219     auto r = m->second.find( dest );
 220     if( r != m->second.end( ) )
 221     {
 222       m->second.erase( r );
 223       if( m->second.size( ) == 0 )
 224         this->m_Matrix.erase( m );
 225
 226     } // fi
 227
 228   } // fi
 229
 230 }
 231
 232 // -------------------------------------------------------------------------
 233 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 234 std::set< _TIndex, _TIndexCompare >
 235 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 236 GetSinks( ) const
 237 {
 238   std::set< _TIndex, _TIndexCompare > sinks;
 239
 240   auto vIt = this->m_Vertices.begin( );
 241   for( ; vIt != this->m_Vertices.end( ); ++vIt )
 242     sinks.insert( vIt->first );
 243   auto mIt = this->m_Matrix.begin( );
 244   for( ; mIt != this->m_Matrix.end( ); ++mIt )
 245     sinks.erase( mIt->first );
 246
 247   return( sinks );
 248 }
 249
 250 // -------------------------------------------------------------------------
 251 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 252 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 253 Graph( )
 254   : Superclass( )
 255 {
 256 }
 257
 258 // -------------------------------------------------------------------------
 259 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 260 cpExtensions::DataStructures::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 261 ~Graph( )
 262 {
 263 }
 264
 265 #endif // __cpExtensions__DataStructures__Graph__hxx__
 266
 267 // eof - $RCSfile$