BreadthFirstVisitor.ih

/**
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as
 *  published by the Free Software Foundation, either version 3 of the
 *  License, or  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 **/
 
/**
 * @file BreadthFirstVisitor.ih
 * @author Jacques-Olivier Lachaud (\c jacques-olivier.lachaud@univ-savoie.fr )
 * Laboratory of Mathematics (CNRS, UMR 5807), University of Savoie, France
 *
 * @date 2011/11/15
 *
 * Implementation of inline methods defined in BreadthFirstVisitor.h
 *
 * This file is part of the DGtal library.
 */
 
 
//////////////////////////////////////////////////////////////////////////////
#include <cstdlib>
//////////////////////////////////////////////////////////////////////////////
 
///////////////////////////////////////////////////////////////////////////////
// IMPLEMENTATION of inline methods.
///////////////////////////////////////////////////////////////////////////////
 
///////////////////////////////////////////////////////////////////////////////
// ----------------------- Standard services ------------------------------
 
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::~BreadthFirstVisitor()
{
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>
::BreadthFirstVisitor( const BreadthFirstVisitor & other )
  : myGraph( other.myGraph ), 
    myMarkedVertices( other.myMarkedVertices ),
    myQueue( other.myQueue )
{
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>
::BreadthFirstVisitor( ConstAlias<Graph> g )
  : myGraph( g )
{
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>
::BreadthFirstVisitor( ConstAlias<Graph> g, const Vertex & p )
  : myGraph( g )
{
  myMarkedVertices.insert( p );
  myQueue.push( std::make_pair( p, 0 ) );
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
template <typename VertexIterator>
inline
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>
::BreadthFirstVisitor( ConstAlias<Graph> g,
                       VertexIterator b, VertexIterator e )
  : myGraph( g )
{
  for ( ; b != e; ++b )
    {
      myMarkedVertices.insert( *b );
      myQueue.push( std::make_pair( *b, 0 ) );
    }
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
const typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::Graph & 
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::graph() const
{
  return myGraph;
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
bool
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::finished() const
{
  return myQueue.empty();
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
const typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::Node & 
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::current() const
{
  ASSERT( ! finished() );
  return myQueue.front();
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
void
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::ignore()
{
  ASSERT( ! finished() );
  myQueue.pop();
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
void
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::expand()
{
  ASSERT( ! finished() );
  Node node = myQueue.front();
  Data d = node.second + 1; 
  myQueue.pop();
  VertexList tmp;
  tmp.reserve( myGraph.bestCapacity() );
  std::back_insert_iterator<VertexList> write_it = std::back_inserter( tmp );
  myGraph.writeNeighbors( write_it, node.first );
  for ( typename VertexList::const_iterator it = tmp.begin(), 
          it_end = tmp.end(); it != it_end; ++it )
    {
      typename MarkSet::const_iterator mark_it = myMarkedVertices.find( *it );
      if ( mark_it == myMarkedVertices.end() )
        {
          myMarkedVertices.insert( *it );
          myQueue.push( std::make_pair( *it, d ) );
        }
    }
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
template <typename VertexPredicate>
inline
void
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::expand
( const VertexPredicate & authorized_vtx )
{
  ASSERT( ! finished() );
  Node node = myQueue.front();
  Data d = node.second + 1; 
  myQueue.pop();
  VertexList tmp;
  tmp.reserve( myGraph.bestCapacity() );
  std::back_insert_iterator<VertexList> write_it = std::back_inserter( tmp );
  myGraph.writeNeighbors( write_it,
                          node.first,
                          authorized_vtx );
  for ( typename VertexList::const_iterator it = tmp.begin(), 
          it_end = tmp.end(); it != it_end; ++it )
    {
      typename MarkSet::const_iterator mark_it = myMarkedVertices.find( *it );
      if ( mark_it == myMarkedVertices.end() )
        {
          myMarkedVertices.insert( *it );
          myQueue.push( std::make_pair( *it, d ) );
        }
    }
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
void
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::terminate()
{
  while ( ! finished() )
    {
      Node node = myQueue.front();
      myQueue.pop();
      typename MarkSet::iterator mark_it = myMarkedVertices.find( node.first );
      ASSERT( mark_it != myMarkedVertices.end() );
      myMarkedVertices.erase( mark_it );
    }
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
const typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::MarkSet & 
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::markedVertices() const
{
  return myMarkedVertices;
}
//-----------------------------------------------------------------------------
template < typename TGraph, typename TMarkSet >
inline
typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::MarkSet
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::visitedVertices() const
{
  if ( finished() ) return myMarkedVertices;
  MarkSet visitedVtx = myMarkedVertices;
  NodeQueue copyQ( myQueue );
  while ( ! copyQ.empty() )
    {
      Node node = copyQ.front();
      copyQ.pop();
      typename MarkSet::iterator mark_it = visitedVtx.find( node.first );
      ASSERT( mark_it != visitedVtx.end() );
      visitedVtx.erase( mark_it );
    }
  return visitedVtx;
  // JOL: 2012/11/21: Cannot do this since method is const.  
  //
  // Roll completely the queue so as to remove these vertices from the
  // set of visited vertices.
  // Node start = myQueue.front();
  // do {
  //   Node node = myQueue.front();
  //   myQueue.pop();
  //   typename MarkSet::iterator mark_it = visitedVtx.find( node.first );
  //   ASSERT( mark_it != visitedVtx.end() );
  //   visitedVtx.erase( mark_it );
  //   myQueue.push( node );
  // } while ( myQueue.front().first != start.first );
  // return visitedVtx;
}
 
///////////////////////////////////////////////////////////////////////////////
// Interface - public :
 
/**
 * Writes/Displays the object on an output stream.
 * @param out the output stream where the object is written.
 */
template < typename TGraph, typename TMarkSet >
inline
void
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::selfDisplay ( std::ostream & out ) const
{
  out << "[BreadthFirstVisitor"
      << " #queue=" << myQueue.size()
      << " ]";
}
 
/**
 * Checks the validity/consistency of the object.
 * @return 'true' if the object is valid, 'false' otherwise.
 */
template < typename TGraph, typename TMarkSet >
inline
bool
DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::isValid() const
{
  return true;
}
 
 
 
///////////////////////////////////////////////////////////////////////////////
// Implementation of inline functions                                        //
 
template < typename TGraph, typename TMarkSet >
inline
std::ostream&
DGtal::operator<< ( std::ostream & out, 
                    const BreadthFirstVisitor<TGraph,TMarkSet> & object )
{
  object.selfDisplay( out );
  return out;
}
 
//                                                                           //
///////////////////////////////////////////////////////////////////////////////