#include <BreadthFirstVisitor.h>

Collaboration diagram for DGtal::BreadthFirstVisitor< TGraph, TMarkSet >:

Data Structures
struct	ConstIterator
struct	NodeAccessor
struct	VertexAccessor

Public Types
typedef BreadthFirstVisitor < TGraph, TMarkSet >	Self
typedef TGraph	Graph
typedef TMarkSet	MarkSet
typedef Graph::Size	Size
typedef Graph::Vertex	Vertex
typedef std::pair< Vertex, Size >	Node
typedef std::queue< Node >	NodeQueue
typedef std::vector< Vertex >	VertexList
typedef ConstIterator < VertexAccessor >	VertexConstIterator
typedef ConstIterator < NodeAccessor >	NodeConstIterator

Public Member Functions
	~BreadthFirstVisitor ()
	BreadthFirstVisitor (const Graph &graph)
	BreadthFirstVisitor (const Graph &graph, const Vertex &p)
template<typename VertexIterator >
	BreadthFirstVisitor (const Graph &graph, VertexIterator b, VertexIterator e)
const Graph &	graph () const
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
void	selfDisplay (std::ostream &out) const
bool	isValid () const

Protected Member Functions
	BreadthFirstVisitor ()

Private Member Functions
	BreadthFirstVisitor (const BreadthFirstVisitor &other)
BreadthFirstVisitor &	operator= (const BreadthFirstVisitor &other)

Private Attributes
const Graph &	myGraph
MarkSet	myMarkedVertices
NodeQueue	myQueue

Detailed Description

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>
class DGtal::BreadthFirstVisitor< TGraph, TMarkSet >

Aim: This class is useful to perform a breadth-first exploration of a graph given a starting point or set (called initial core).

Description of template class 'BreadthFirstVisitor'

The expander implements a breadth-first algorithm on the graph of adjacencies. It can be used not only to detect connected component but also to identify the layers of the object located at a given distance of a starting set.

The core of the expander is at the beginning the set of points at distance 0. Each layer is at a different distance from the initial core. The expander move layer by layer but the user is free to navigate on each layer.

Template Parameters:

TGraph the type of the graph (models of CUndirectedSimpleLocalGraph).

     Graph g( ... );
     Graph::Vertex p( ... );
     BreadthFirstVisitor< Graph > visitor( g, p );
     while ( ! visitor.finished() )
       {
         BreadthFirstVisitor<Graph>::Node node = visitor.current();
         std::cout << "Vertex " << node.first 
                   << " at distance " << node.second << std::endl;
         visitor.expand();
       }

See also:: testBreadthFirstVisitor.cpp; testObject.cpp

Examples:: geometry/surfaces/greedy-plane-segmentation-ex2.cpp, and geometry/surfaces/greedy-plane-segmentation.cpp.

Definition at line 94 of file BreadthFirstVisitor.h.

Member Typedef Documentation

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

typedef TGraph DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Graph

Definition at line 99 of file BreadthFirstVisitor.h.

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

typedef TMarkSet DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::MarkSet

Definition at line 100 of file BreadthFirstVisitor.h.

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

typedef std::pair< Vertex, Size > DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Node

Type stocking the vertex and its topological distance wrt the initial point or set.

Definition at line 113 of file BreadthFirstVisitor.h.

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

typedef ConstIterator<NodeAccessor> DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::NodeConstIterator

const iterator on pair (Vertex,distance) for visiting a graph by following a breadth first traversal.

Definition at line 240 of file BreadthFirstVisitor.h.

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

typedef std::queue< Node > DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::NodeQueue

Internal data structure for computing the breadth-first expansion.

Definition at line 115 of file BreadthFirstVisitor.h.

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

typedef BreadthFirstVisitor<TGraph,TMarkSet> DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Self

Definition at line 98 of file BreadthFirstVisitor.h.

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

typedef Graph::Size DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Size

Definition at line 101 of file BreadthFirstVisitor.h.

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

typedef Graph::Vertex DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Vertex

Definition at line 102 of file BreadthFirstVisitor.h.

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

typedef ConstIterator<VertexAccessor> DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::VertexConstIterator

const iterator on Vertex for visiting a graph by following a breadth first traversal.

Definition at line 237 of file BreadthFirstVisitor.h.

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

typedef std::vector< Vertex > DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::VertexList

Internal data structure for storing vertices.

Definition at line 117 of file BreadthFirstVisitor.h.

Constructor & Destructor Documentation

template<typename TGraph , typename TMarkSet >

DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::~BreadthFirstVisitor ( )

inline

Destructor.

Definition at line 44 of file BreadthFirstVisitor.ih.

{

}

template<typename TGraph , typename TMarkSet >

DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor ( const Graph & graph )

inline

Constructor from the graph only. The visitor is in the state 'finished()'. Useful to create an equivalent of 'end()' iterator.

Parameters:

graph the graph in which the breadth first traversal takes place.

Definition at line 51 of file BreadthFirstVisitor.ih.

  : myGraph( g )
{
}

template<typename TGraph , typename TMarkSet >

DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor	(	const Graph &	graph,
		const Vertex &	p
	)

inline

Constructor from a point. This point provides the initial core of the visitor.

Parameters:

graph	the graph in which the breadth first traversal takes place.
p	any vertex of the graph.

Definition at line 59 of file BreadthFirstVisitor.ih.

References DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::myMarkedVertices, and DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::myQueue.

  : myGraph( g )
{
  myMarkedVertices.insert( p );
  myQueue.push( std::make_pair( p, 0 ) );
}

template<typename TGraph , typename TMarkSet >

template<typename VertexIterator >

DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor	(	const Graph &	graph,
		VertexIterator	b,
		VertexIterator	e
	)

inline

Constructor from iterators. All vertices visited between the iterators should be distinct two by two. The so specified set of vertices provides the initial core of the breadth first traversal. These vertices will all have a topological distance 0.

Template Parameters:

VertexIterator any type of single pass iterator on vertices.

Parameters:

graph	the graph in which the breadth first traversal takes place.
b	the begin iterator in a container of vertices.
e	the end iterator in a container of vertices.

Definition at line 70 of file BreadthFirstVisitor.ih.

References DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::myMarkedVertices, and DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::myQueue.

  : myGraph( g )
{
  for ( ; b != e; ++b )
    {
      myMarkedVertices.insert( *b );
      myQueue.push( std::make_pair( *b, 0 ) );
    }
}

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor ( )

protected

Constructor. Forbidden by default (protected to avoid g++ warnings).

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor ( const BreadthFirstVisitor< TGraph, TMarkSet > & other )

private

Copy constructor.

Parameters:

other the object to clone. Forbidden by default.

Member Function Documentation

template<typename TGraph , typename TMarkSet >

const DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Node & DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::current ( ) const

inline

Returns:: a const reference on the current visited vertex. The node is a pair <Vertex,Size> where the second term is the topological distance to the start vertex or set.

NB: valid only if not 'finished()'.

Definition at line 100 of file BreadthFirstVisitor.ih.

Referenced by DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::ConstIterator< TAccessor >::operator*(), DGtal::DepthFirstVisitor< TGraph, TMarkSet >::ConstIterator< TAccessor >::operator*(), DGtal::DepthFirstVisitor< TGraph, TMarkSet >::ConstIterator< TAccessor >::operator==(), and DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::ConstIterator< TAccessor >::operator==().

{
  ASSERT( ! finished() );
  return myQueue.front();
}

template<typename TGraph , typename TMarkSet >

void DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::expand ( )

inline

Goes to the next vertex and taked into account the current vertex for determining the future vsited vertices. NB: valid only if not 'finished()'.

Definition at line 118 of file BreadthFirstVisitor.ih.

Referenced by DGtal::Object< TDigitalTopology, TDigitalSet >::computeConnectedness(), DGtal::Object< TDigitalTopology, TDigitalSet >::geodesicNeighborhood(), DGtal::Object< TDigitalTopology, TDigitalSet >::geodesicNeighborhoodInComplement(), DGtal::DepthFirstVisitor< TGraph, TMarkSet >::ConstIterator< TAccessor >::operator++(), DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::ConstIterator< TAccessor >::operator++(), and DGtal::Object< TDigitalTopology, TDigitalSet >::writeComponents().

{
  ASSERT( ! finished() );
  Node node = myQueue.front();
  Size 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 >

void DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::expand ( const VertexPredicate & authorized_vtx )

inline

Goes to the next vertex and taked into account the current vertex for determining the future visited vertices.

Template Parameters:

VertexPredicate a type that satisfies CPredicate on Vertex.

Parameters:

authorized_vtx the predicate that should satisfy the visited vertices.

NB: valid only if not 'finished()'.

Definition at line 145 of file BreadthFirstVisitor.ih.

{
  ASSERT( ! finished() );
  Node node = myQueue.front();
  Size 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 >

bool DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::finished ( ) const

inline

Returns:: 'true' if all possible elements have been visited.

Definition at line 92 of file BreadthFirstVisitor.ih.

Referenced by DGtal::Object< TDigitalTopology, TDigitalSet >::computeConnectedness(), DGtal::DepthFirstVisitor< TGraph, TMarkSet >::ConstIterator< TAccessor >::operator==(), DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::ConstIterator< TAccessor >::operator==(), and DGtal::Object< TDigitalTopology, TDigitalSet >::writeComponents().

{
  return myQueue.empty();
}

template<typename TGraph , typename TMarkSet >

const DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Graph & DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::graph ( ) const

inline

Returns:: a const reference on the graph that is traversed.

Definition at line 84 of file BreadthFirstVisitor.ih.

{
  return myGraph;
}

template<typename TGraph , typename TMarkSet >

void DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::ignore ( )

inline

Goes to the next vertex but ignores the current vertex for determining the future visited vertices. Otherwise said, no future visited vertex will have this vertex as a father.

NB: valid only if not 'finished()'.

Definition at line 109 of file BreadthFirstVisitor.ih.

{
  ASSERT( ! finished() );
  myQueue.pop();
}

template<typename TGraph , typename TMarkSet >

bool DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::isValid ( ) const

inline

Checks the validity/consistency of the object.

Returns:: 'true' if the object is valid, 'false' otherwise.

Definition at line 249 of file BreadthFirstVisitor.ih.

{
  return true;
}

template<typename TGraph , typename TMarkSet >

const DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::MarkSet & DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::markedVertices ( ) const

inline

Returns:: a const reference to the current set of marked vertices. It includes the visited vertices and the vertices neighbors to the current layer of vertices. NB: O(1) operation.

Definition at line 187 of file BreadthFirstVisitor.ih.

Referenced by DGtal::Object< TDigitalTopology, TDigitalSet >::writeComponents().

{
  return myMarkedVertices;
}

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

BreadthFirstVisitor& DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::operator= ( const BreadthFirstVisitor< TGraph, TMarkSet > & other )

private

Assignment.

Parameters:

other the object to copy.

Returns:: a reference on 'this'. Forbidden by default.

template<typename TGraph , typename TMarkSet >

void DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::selfDisplay ( std::ostream & out ) const

inline

Writes/Displays the object on an output stream.

Parameters:

out	the output stream where the object is written.

Definition at line 235 of file BreadthFirstVisitor.ih.

{
  out << "[BreadthFirstVisitor"
      << " #queue=" << myQueue.size()
      << " ]";
}

template<typename TGraph , typename TMarkSet >

void DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::terminate ( )

inline

Force termination of the breadth first traversal. 'finished()' returns 'true' afterwards and 'current()', 'expand()', 'ignore()' have no more meaning. Furthermore, 'markedVertices()' and 'visitedVertices()' both represents the set of visited vertices.

Definition at line 172 of file BreadthFirstVisitor.ih.

{
  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 >

DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::MarkSet DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::visitedVertices ( ) const

inline

Returns:: the current set of visited vertices (a subset of marked vertices; excludes the marked vertices yet to be visited). Note that if 'finished()' is true, then 'markedVertices()' is equal to 'visitedVertices()' and should thus be preferred.

NB: computational cost is a copy of the set of marked vertices then as many deletion as the number of marked vertices yet to be visited.

See also:: markedVertices

Definition at line 195 of file BreadthFirstVisitor.ih.

Referenced by DGtal::Object< TDigitalTopology, TDigitalSet >::computeConnectedness().

{
  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;
}

Field Documentation

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

const Graph& DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::myGraph

private

The graph where the traversal takes place.

Definition at line 390 of file BreadthFirstVisitor.h.

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

MarkSet DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::myMarkedVertices

private

Set representing the marked vertices: the ones that have been visited and the one that are going to be visited soon (at distance + 1).

Definition at line 397 of file BreadthFirstVisitor.h.

Referenced by DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor().

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>

NodeQueue DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::myQueue

private

Queue storing the vertices that are the next visited ones in the breadth-first traversal of the graph.

Definition at line 403 of file BreadthFirstVisitor.h.

Referenced by DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor().

The documentation for this class was generated from the following files:

Data Structures

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet> class DGtal::BreadthFirstVisitor< TGraph, TMarkSet >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation

template<typename TGraph, typename TMarkSet = typename TGraph::VertexSet>
class DGtal::BreadthFirstVisitor< TGraph, TMarkSet >