lib/fpa/Base/Graph.hxx

   1 // =========================================================================
   2 // @author Leonardo Florez Valencia
   3 // @email florez-l@javeriana.edu.co
   4 // =========================================================================
   5
   6 #ifndef __fpa__Base__Graph__hxx__
   7 #define __fpa__Base__Graph__hxx__
   8
   9 // -------------------------------------------------------------------------
  10 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
  11 void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
  12 Clear( )
  13 {
  14   this->m_Vertices.clear( );
  15   this->m_Matrix.clear( );
  16 }
  17
  18 // -------------------------------------------------------------------------
  19 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
  20 bool fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
  21 RenameVertex( const TIndex& old_index, const TIndex& new_index )
  22 {
  23   typename TVertices::iterator old_v = this->m_Vertices.find( old_index );
  24   typename TVertices::iterator new_v = this->m_Vertices.find( new_index );
  25   if( old_v != this->m_Vertices.end( ) && new_v == this->m_Vertices.end( ) )
  26   {
  27     // Replace vertex
  28     this->m_Vertices[ new_index ] = old_v->second;
  29     this->m_Vertices.erase( old_index );
  30
  31     // Duplicate edges
  32     typename TMatrix::iterator mIt = this->m_Matrix.begin( );
  33     typename TMatrix::iterator found_row = this->m_Matrix.end( );
  34     for( ; mIt != this->m_Matrix.end( ); ++mIt )
  35     {
  36       if( mIt->first == old_index )
  37         found_row = mIt;
  38
  39       typename TMatrixRow::iterator rIt = mIt->second.begin( );
  40       for( ; rIt != mIt->second.end( ); ++rIt )
  41       {
  42         if( mIt->first == old_index )
  43           this->m_Matrix[ new_index ][ rIt->first ] = rIt->second;
  44         else if( rIt->first == old_index )
  45           this->m_Matrix[ mIt->first ][ new_index ] = rIt->second;
  46
  47       } // rof
  48
  49     } // rof
  50
  51     // Delete old edges
  52     if( found_row != this->m_Matrix.end( ) )
  53       this->m_Matrix.erase( found_row );
  54
  55     mIt = this->m_Matrix.begin( );
  56     for( ; mIt != this->m_Matrix.end( ); ++mIt )
  57     {
  58       typename TMatrixRow::iterator rIt = mIt->second.begin( );
  59       while( rIt != mIt->second.end( ) )
  60       {
  61         if( rIt->first == old_index )
  62         {
  63           mIt->second.erase( rIt );
  64           rIt = mIt->second.begin( );
  65         }
  66         else
  67           ++rIt;
  68
  69       } // elihw
  70
  71     } // rof
  72     return( true );
  73   }
  74   else
  75     return( false );
  76 }
  77
  78 // -------------------------------------------------------------------------
  79 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
  80 void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
  81 RemoveVertex( const TIndex& index )
  82 {
  83   typename TVertices::iterator i = this->m_Vertices.find( index );
  84   if( i != this->m_Vertices.end( ) )
  85   {
  86     // Delete vertex
  87     this->m_Vertices.erase( i );
  88
  89     // Delete edges starting from given vertex
  90     typename TMatrix::iterator mIt = this->m_Matrix.find( index );
  91     if( mIt != this->m_Matrix.end( ) )
  92       this->m_Matrix.erase( mIt );
  93
  94     // Delete edges arriving to given vertex
  95     mIt = this->m_Matrix.begin( );
  96     for( ; mIt != this->m_Matrix.end( ); ++mIt )
  97     {
  98       typename TMatrixRow::iterator rIt = mIt->second.begin( );
  99       while( rIt != mIt->second.end( ) )
 100       {
 101         if( rIt->first == index )
 102         {
 103           mIt->second.erase( rIt );
 104           rIt = mIt->second.begin( );
 105         }
 106         else
 107           ++rIt;
 108
 109       } // elihw
 110
 111     } // rof
 112
 113   } // fi
 114 }
 115
 116 // -------------------------------------------------------------------------
 117 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 118 typename
 119 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 120 TEdges&
 121 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 122 GetEdges( const TIndex& orig, const TIndex& dest )
 123 {
 124   static TEdges null_edges;
 125   typename TMatrix::iterator o = this->m_Matrix.find( orig );
 126   if( o != this->m_Matrix.find( orig ) )
 127   {
 128     typename TMatrixRow::iterator d = o->second.find( dest );
 129     if( d == o->second.end( ) )
 130     {
 131       null_edges.clear( );
 132       return( null_edges );
 133     }
 134     else
 135       return( d->second );
 136   }
 137   else
 138   {
 139     null_edges.clear( );
 140     return( null_edges );
 141
 142   } // fi
 143 }
 144
 145 // -------------------------------------------------------------------------
 146 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 147 const typename
 148 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 149 TEdges&
 150 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 151 GetEdges( const TIndex& orig, const TIndex& dest ) const
 152 {
 153   static const TEdges null_edges;
 154   typename TMatrix::iterator o = this->m_Matrix.find( orig );
 155   if( o != this->m_Matrix.find( orig ) )
 156   {
 157     typename TMatrixRow::iterator d = o->second.find( dest );
 158     if( d == o->second.end( ) )
 159       return( null_edges );
 160     else
 161       return( d->second );
 162   }
 163   else
 164     return( null_edges );
 165 }
 166
 167 // -------------------------------------------------------------------------
 168 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 169 bool fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 170 HasEdge( const TIndex& orig, const TIndex& dest ) const
 171 {
 172   typename TMatrix::const_iterator mIt = this->m_Matrix.find( orig );
 173   if( mIt != this->m_Matrix.end( ) )
 174     return( mIt->second.find( dest ) != mIt->second.end( ) );
 175   else
 176     return( false );
 177 }
 178
 179 // -------------------------------------------------------------------------
 180 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 181 void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 182 RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
 183 {
 184   typename TMatrix::iterator m = this->m_Matrix.find( orig );
 185   if( m != this->m_Matrix.end( ) )
 186   {
 187     typename TMatrixRow::iterator r = m->second.find( dest );
 188     if( r != m->second.end( ) )
 189     {
 190       typename TEdges::iterator e = r->second.end( );
 191       for(
 192         typename TEdges::iterator i = r->second.begin( );
 193         i != r->second.end( ) && e == r->second.end( );
 194         ++i
 195         )
 196         if( *i == cost )
 197           e = i;
 198       if( e != r->second.end( ) )
 199       {
 200         r->second.erase( e );
 201         if( r->second.size( ) == 0 )
 202         {
 203           m->second.erase( r );
 204           if( m->second.size( ) == 0 )
 205             this->m_Matrix.erase( m );
 206
 207         } // fi
 208
 209       } // fi
 210
 211     } // fi
 212
 213   } // fi
 214 }
 215
 216 // -------------------------------------------------------------------------
 217 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 218 void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 219 RemoveEdges( const TIndex& orig, const TIndex& dest )
 220 {
 221   typename TMatrix::iterator m = this->m_Matrix.find( orig );
 222   if( m != this->m_Matrix.end( ) )
 223   {
 224     typename TMatrixRow::iterator r = m->second.find( dest );
 225     if( r != m->second.end( ) )
 226     {
 227       m->second.erase( r );
 228       if( m->second.size( ) == 0 )
 229         this->m_Matrix.erase( m );
 230
 231     } // fi
 232
 233   } // fi
 234
 235 }
 236
 237 // -------------------------------------------------------------------------
 238 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 239 std::set< _TIndex, _TIndexCompare >
 240 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 241 GetSinks( ) const
 242 {
 243   std::set< _TIndex, _TIndexCompare > sinks;
 244
 245   typename TVertices::iterator vIt = this->m_Vertices.begin( );
 246   for( ; vIt != this->m_Vertices.end( ); ++vIt )
 247     sinks.insert( vIt->first );
 248   typename TMatrix::iterator mIt = this->m_Matrix.begin( );
 249   for( ; mIt != this->m_Matrix.end( ); ++mIt )
 250     sinks.erase( mIt->first );
 251
 252   return( sinks );
 253 }
 254
 255 // -------------------------------------------------------------------------
 256 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 257 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 258 Graph( )
 259   : Superclass( )
 260 {
 261 }
 262
 263 // -------------------------------------------------------------------------
 264 template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
 265 fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
 266 ~Graph( )
 267 {
 268 }
 269
 270 #endif // __fpa__Base__Graph__hxx__
 271
 272 // eof - $RCSfile$