BreadthFirstVisitor.h

 
#pragma once
 
#if defined(BreadthFirstVisitor_RECURSES)
#error Recursive header files inclusion detected in BreadthFirstVisitor.h
#else // defined(BreadthFirstVisitor_RECURSES)
#define BreadthFirstVisitor_RECURSES
 
#if !defined BreadthFirstVisitor_h
#define BreadthFirstVisitor_h
 
// Inclusions
#include <iostream>
#include <queue>
#include "DGtal/base/Common.h"
#include "DGtal/base/CountedPtr.h"
#include "DGtal/base/ConstAlias.h"
#include "DGtal/kernel/sets/DigitalSetSelector.h"
#include "DGtal/kernel/sets/DigitalSetDomain.h"
#include "DGtal/topology/DomainAdjacency.h"
#include "DGtal/graph/CUndirectedSimpleLocalGraph.h"
 
namespace DGtal
{
 
  // template class BreadthFirstVisitor
  template < typename TGraph, 
             typename TMarkSet = typename TGraph::VertexSet >
  class BreadthFirstVisitor
  {
    // ----------------------- Associated types ------------------------------
  public:
    typedef BreadthFirstVisitor<TGraph,TMarkSet> Self;
    typedef TGraph Graph;
    typedef TMarkSet MarkSet;
    typedef typename Graph::Size Size;
    typedef typename Graph::Vertex Vertex;
    typedef Size Data; 
 
    // Cannot check this since some types using it are incomplete.
    // BOOST_CONCEPT_ASSERT(( concepts::CUndirectedSimpleLocalGraph< Graph > ));
    // BOOST_CONCEPT_ASSERT(( CSet< MarkSet, Vertex > ));
 
    // ----------------------- defined types ------------------------------
  public:
 
    typedef std::pair< Vertex, Data > Node;
    typedef std::queue< Node > NodeQueue;
    typedef std::vector< Vertex > VertexList;
 
 
    // ----------------------- Standard services ------------------------------
  public:
 
    ~BreadthFirstVisitor();
 
    BreadthFirstVisitor ( const BreadthFirstVisitor & other );
 
    BreadthFirstVisitor( ConstAlias<Graph> graph );
 
    BreadthFirstVisitor( ConstAlias<Graph> graph, const Vertex & p );
 
    template <typename VertexIterator>
    BreadthFirstVisitor( ConstAlias<Graph> graph, 
                         VertexIterator b, VertexIterator e );
 
 
    const Graph & graph() const;
 
    // ----------------------- traversal services ------------------------------
  public:
 
    const Node & current() const; 
 
    void ignore();
 
    void expand();
 
    template <typename VertexPredicate>
    void expand( const VertexPredicate & authorized_vtx );
    
    bool finished() const;
 
    void terminate();
 
    const MarkSet & markedVertices() const;
 
    MarkSet visitedVertices() const;
 
 
    // ----------------------- Interface --------------------------------------
  public:
 
    void selfDisplay ( std::ostream & out ) const;
 
    bool isValid() const;
 
    // ------------------------- Protected Datas ------------------------------
  private:
    // ------------------------- Private Datas --------------------------------
  private:
 
    const Graph & myGraph;
 
    MarkSet myMarkedVertices;
 
    NodeQueue myQueue;
 
    // ------------------------- Hidden services ------------------------------
  protected:
 
    BreadthFirstVisitor();
 
  private:
 
    BreadthFirstVisitor & operator= ( const BreadthFirstVisitor & other );
 
    // ------------------------- Internals ------------------------------------
  private:
 
  }; // end of class BreadthFirstVisitor
 
 
  template <typename TGraph, typename TMarkSet >
  std::ostream&
  operator<< ( std::ostream & out, 
               const BreadthFirstVisitor<TGraph, TMarkSet > & object );
 
} // namespace DGtal
 
 
// Includes inline functions.
#include "DGtal/graph/BreadthFirstVisitor.ih"
 
//                                                                           //
 
#endif // !defined BreadthFirstVisitor_h
 
#undef BreadthFirstVisitor_RECURSES
#endif // else defined(BreadthFirstVisitor_RECURSES)