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>
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::Vertex p( ... );
while ( ! visitor.finished() )
{
std::cout << "Vertex " << node.first
<< " at distance " << node.second << std::endl;
}
Aim: This class is useful to perform a breadth-first exploration of a graph given a starting point or...
std::pair< Vertex, Data > Node
FIXME.
- See also
- testBreadthFirstVisitor.cpp
-
testObject.cpp
- Examples
- examples/tutorial-examples/polyhedralizer.cpp, geometry/surfaces/greedy-plane-segmentation-ex2.cpp, geometry/surfaces/greedy-plane-segmentation.cpp, graph/graphTraversal.cpp, shapes/exampleSurfaceMesh.cpp, topology/volBreadthFirstTraversal.cpp, and tutorial-examples/polyhedralizer.cpp.
Definition at line 94 of file BreadthFirstVisitor.h.
◆ Data
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
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>
◆ MarkSet
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
◆ Node
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
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>
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>
◆ Size
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
◆ Vertex
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
◆ VertexList
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
◆ ~BreadthFirstVisitor()
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
◆ BreadthFirstVisitor() [1/5]
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
Copy constructor.
- Parameters
-
other | the object to clone. |
◆ BreadthFirstVisitor() [2/5]
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
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. |
◆ BreadthFirstVisitor() [3/5]
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
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. |
◆ BreadthFirstVisitor() [4/5]
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
template<typename VertexIterator >
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. |
◆ BreadthFirstVisitor() [5/5]
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
Constructor. Forbidden by default (protected to avoid g++ warnings).
◆ current()
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
◆ expand() [1/2]
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
◆ expand() [2/2]
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
template<typename VertexPredicate >
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()'.
◆ finished()
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
◆ graph()
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
- Returns
- a const reference on the graph that is traversed.
◆ ignore()
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
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()'.
◆ isValid()
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
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>
- 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>
Assignment.
- Parameters
-
- Returns
- a reference on 'this'. Forbidden by default.
◆ selfDisplay()
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
Writes/Displays the object on an output stream.
- Parameters
-
out | the output stream where the object is written. |
◆ terminate()
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
◆ visitedVertices()
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
- 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
◆ myGraph
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
◆ myMarkedVertices
template<typename TGraph , typename TMarkSet = typename TGraph::VertexSet>
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>
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: