DGtal  1.5.beta
DGtal::BreadthFirstVisitor< TGraph, TMarkSet > Class Template Reference

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

#include <DGtal/graph/BreadthFirstVisitor.h>

Public Types

typedef BreadthFirstVisitor< TGraph, TMarkSet > Self
 
typedef TGraph Graph
 
typedef TMarkSet MarkSet
 
typedef Graph::Size Size
 
typedef Graph::Vertex Vertex
 
typedef Size Data
 Data attached to each Vertex is the topological distance to the seed. More...
 
typedef std::pair< Vertex, DataNode
 FIXME. More...
 
typedef std::queue< NodeNodeQueue
 Internal data structure for computing the breadth-first expansion. More...
 
typedef std::vector< VertexVertexList
 Internal data structure for storing vertices. More...
 

Public Member Functions

 ~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 Graphgraph () const
 
const Nodecurrent () const
 
void ignore ()
 
void expand ()
 
template<typename VertexPredicate >
void expand (const VertexPredicate &authorized_vtx)
 
bool finished () const
 
void terminate ()
 
const MarkSetmarkedVertices () const
 
MarkSet visitedVertices () const
 
void selfDisplay (std::ostream &out) const
 
bool isValid () const
 

Protected Member Functions

 BreadthFirstVisitor ()
 

Private Member Functions

BreadthFirstVisitoroperator= (const BreadthFirstVisitor &other)
 

Private Attributes

const GraphmyGraph
 
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
TGraphthe 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();
}
std::pair< Vertex, Data > Node
FIXME.
TriMesh::Vertex Vertex
See also
testBreadthFirstVisitor.cpp
testObject.cpp

Definition at line 94 of file BreadthFirstVisitor.h.

Member Typedef Documentation

◆ Data

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
typedef Size DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Data

Data attached to each Vertex is the topological distance to the seed.

Definition at line 103 of file BreadthFirstVisitor.h.

◆ Graph

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

Definition at line 99 of file BreadthFirstVisitor.h.

◆ MarkSet

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

Definition at line 100 of file BreadthFirstVisitor.h.

◆ Node

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
typedef std::pair< Vertex, Data > DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Node

FIXME.

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

Definition at line 115 of file BreadthFirstVisitor.h.

◆ NodeQueue

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 117 of file BreadthFirstVisitor.h.

◆ Self

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.

◆ Size

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
typedef Graph::Size DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Size

Definition at line 101 of file BreadthFirstVisitor.h.

◆ Vertex

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
typedef Graph::Vertex DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::Vertex

Definition at line 102 of file BreadthFirstVisitor.h.

◆ VertexList

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 119 of file BreadthFirstVisitor.h.

Constructor & Destructor Documentation

◆ ~BreadthFirstVisitor()

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::~BreadthFirstVisitor ( )

Destructor.

◆ BreadthFirstVisitor() [1/5]

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor ( const BreadthFirstVisitor< TGraph, TMarkSet > &  other)

Copy constructor.

Parameters
otherthe object to clone.

◆ BreadthFirstVisitor() [2/5]

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor ( ConstAlias< Graph graph)

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

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

◆ BreadthFirstVisitor() [3/5]

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor ( ConstAlias< Graph graph,
const Vertex p 
)

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

Parameters
graphthe graph in which the breadth first traversal takes place.
pany vertex of the graph.

◆ BreadthFirstVisitor() [4/5]

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
template<typename VertexIterator >
DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor ( ConstAlias< Graph graph,
VertexIterator  b,
VertexIterator  e 
)

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
VertexIteratorany type of single pass iterator on vertices.
Parameters
graphthe graph in which the breadth first traversal takes place.
bthe begin iterator in a container of vertices.
ethe end iterator in a container of vertices.

◆ BreadthFirstVisitor() [5/5]

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::BreadthFirstVisitor ( )
protected

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

Member Function Documentation

◆ current()

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
const Node& DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::current ( ) const
Returns
a const reference on the current visited vertex. The node is a pair <Vertex,Data> where the second term is the topological distance to the start vertex or set.

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

Referenced by main(), SCENARIO(), testBreadthFirstPropagation(), testDepthFirstPropagation(), testDigitalSurface(), and testDistancePropagation().

◆ expand() [1/2]

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
void DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::expand ( )

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

Referenced by main(), SCENARIO(), testBreadthFirstPropagation(), testDepthFirstPropagation(), testDigitalSurface(), and testDistancePropagation().

◆ expand() [2/2]

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

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

Template Parameters
VertexPredicatea type that satisfies CPredicate on Vertex.
Parameters
authorized_vtxthe predicate that should satisfy the visited vertices.

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

◆ finished()

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
bool DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::finished ( ) const
Returns
'true' if all possible elements have been visited.

Referenced by main(), SCENARIO(), testBreadthFirstPropagation(), testDepthFirstPropagation(), testDigitalSurface(), and testDistancePropagation().

◆ graph()

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
const Graph& DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::graph ( ) const
Returns
a const reference on the graph that is traversed.

◆ ignore()

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
void DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::ignore ( )

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()'.

Referenced by main().

◆ isValid()

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
bool DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::isValid ( ) const

Checks the validity/consistency of the object.

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

◆ markedVertices()

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
const MarkSet& DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::markedVertices ( ) const
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.

Referenced by testDigitalSurface().

◆ operator=()

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
BreadthFirstVisitor& DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::operator= ( const BreadthFirstVisitor< TGraph, TMarkSet > &  other)
private

Assignment.

Parameters
otherthe object to copy.
Returns
a reference on 'this'. Forbidden by default.

◆ selfDisplay()

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

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.

◆ terminate()

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
void DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::terminate ( )

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.

◆ visitedVertices()

template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
MarkSet DGtal::BreadthFirstVisitor< TGraph, TMarkSet >::visitedVertices ( ) const
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

Field Documentation

◆ myGraph

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 276 of file BreadthFirstVisitor.h.

◆ myMarkedVertices

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 283 of file BreadthFirstVisitor.h.

◆ myQueue

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 289 of file BreadthFirstVisitor.h.


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