lib/fpa/DataStructures/Graph.hxx

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