#ifndef __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
#define __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__

// -------------------------------------------------------------------------
template< class V, class C, class I >
void cpExtensions::DataStructures::Graph< V, C, I >::
Clear( )
{
  this->m_Vertices.clear( );
  this->m_Matrix.clear( );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
bool cpExtensions::DataStructures::Graph< V, C, I >::
RenameVertex( const I& old_index, const I& new_index )
{
  auto old_v = this->m_Vertices.find( old_index );
  auto new_v = this->m_Vertices.find( new_index );
  if( old_v != this->m_Vertices.end( ) && new_v == this->m_Vertices.end( ) )
  {
    // Replace vertex
    this->m_Vertices[ new_index ] = old_v->second;
    this->m_Vertices.erase( old_index );

    // Duplicate edges
    auto mIt = this->m_Matrix.begin( );
    auto found_row = this->m_Matrix.end( );
    for( ; mIt != this->m_Matrix.end( ); ++mIt )
    {
      if( mIt->first == old_index )
        found_row = mIt;

      auto rIt = mIt->second.begin( );
      for( ; rIt != mIt->second.end( ); ++rIt )
      {
        if( mIt->first == old_index )
          this->m_Matrix[ new_index ][ rIt->first ] = rIt->second;
        else if( rIt->first == old_index )
          this->m_Matrix[ mIt->first ][ new_index ] = rIt->second;

      } // rof

    } // rof

    // Delete old edges
    if( found_row != this->m_Matrix.end( ) )
      this->m_Matrix.erase( found_row );

    mIt = this->m_Matrix.begin( );
    for( ; mIt != this->m_Matrix.end( ); ++mIt )
    {
      auto rIt = mIt->second.begin( );
      while( rIt != mIt->second.end( ) )
      {
        if( rIt->first == old_index )
        {
          mIt->second.erase( rIt );
          rIt = mIt->second.begin( );
        }
        else
          ++rIt;

      } // elihw

    } // rof
    return( true );
  }
  else
    return( false );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
void cpExtensions::DataStructures::Graph< V, C, I >::
RemoveVertex( const I& index )
{
  auto i = this->m_Vertices.find( index );
  if( i != this->m_Vertices.end( ) )
  {
    // Delete vertex
    this->m_Vertices.erase( i );

    // Delete edges starting from given vertex
    auto mIt = this->m_Matrix.find( index );
    if( mIt != this->m_Matrix.end( ) )
      this->m_Matrix.erase( mIt );

    // Delete edges arriving to given vertex
    mIt = this->m_Matrix.begin( );
    for( ; mIt != this->m_Matrix.end( ); ++mIt )
    {
      auto rIt = mIt->second.begin( );
      while( rIt != mIt->second.end( ) )
      {
        if( rIt->first == index )
        {
          mIt->second.erase( rIt );
          rIt = mIt->second.begin( );
        }
        else
          ++rIt;

      } // elihw

    } // rof
    return( true );
  }
  else
    return( false );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
bool cpExtensions::DataStructures::Graph< V, C, I >::
HasEdge( const I& orig, const I& dest ) const
{
  auto mIt = this->m_Matrix.find( orig );
  if( mIt != this->m_Matrix.end( ) )
    return( mIt->second.find( dest ) != mIt->second.end( ) );
  else
    return( false );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
void cpExtensions::DataStructures::Graph< V, C, I >::
RemoveEdge( const I& orig, const I& dest, const C& cost )
{
  auto m = this->m_Matrix.find( orig );
  if( m != this->m_Matrix.end( ) )
  {
    auto r = m->second.find( dest );
    if( r != m->second.end( ) )
    {
      auto e = std::find( r->second.begin( ), r->second.end( ), cost );
      if( e != r->second.end( ) )
      {
        r->second.erase( e );
        if( r->second.size( ) == 0 )
        {
          m->second.erase( r );
          if( m->second.size( ) == 0 )
            this->m_Matrix.erase( m );

        } // fi

      } // fi

    } // fi

  } // fi
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
void cpExtensions::DataStructures::Graph< V, C, I >::
RemoveEdges( const I& orig, const I& dest )
{
  auto m = this->m_Matrix.find( orig );
  if( m != this->m_Matrix.end( ) )
  {
    auto r = m->second.find( dest );
    if( r != m->second.end( ) )
    {
      m->second.erase( r );
      if( m->second.size( ) == 0 )
        this->m_Matrix.erase( m );

    } // fi

  } // fi

}

// -------------------------------------------------------------------------
template< class V, class C, class I >
std::set< I > cpExtensions::DataStructures::Graph< V, C, I >::
GetSinks( ) const
{
  std::set< I > sinks;

  auto vIt = this->m_Vertices.begin( );
  for( ; vIt != this->m_Vertices.end( ); ++vIt )
    sinks.insert( vIt->first );
  auto mIt = this->m_Matrix.begin( );
  for( ; mIt != this->m_Matrix.end( ); ++mIt )
    sinks.erase( mIt->first );

  return( sinks );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
cpExtensions::DataStructures::Graph< V, C, I >::
Graph( )
  : Superclass( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
cpExtensions::DataStructures::Graph< V, C, I >::
~Graph( )
{
}

#endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__

// eof - $RCSfile$