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

#include <DGtal/graph/DepthFirstVisitor.h>

Public Types
typedef DepthFirstVisitor< 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 depth distance to the seed. More...

typedef std::pair< Vertex, Data >	Node

typedef std::stack< Node >	NodeQueue
	Internal data structure for computing the depth-first expansion. More...

typedef std::vector< Vertex >	VertexList
	Internal data structure for storing vertices. More...

Public Member Functions
	~DepthFirstVisitor ()

	DepthFirstVisitor (const DepthFirstVisitor &other)

	DepthFirstVisitor (ConstAlias< Graph > graph)

	DepthFirstVisitor (ConstAlias< Graph > graph, const Vertex &p)

template<typename VertexIterator >
	DepthFirstVisitor (ConstAlias< 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
	DepthFirstVisitor ()

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

Private Attributes
const Graph &	myGraph

MarkSet	myMarkedVertices

NodeQueue	myQueue

Detailed Description

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

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

Description of template class 'DepthFirstVisitor'

The expander implements a depth-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. In this visitor, the distance attached to visited nodes correspond to the depth of the node in the breadth-first traveral.

Template Parameters

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

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

See also: testDepthFirstVisitor.cpp

Examples: geometry/tools/exampleAlphaShape.cpp, graph/graphTraversal.cpp, and tutorial-examples/AreaSurfaceEstimation-final.cpp.

Definition at line 95 of file DepthFirstVisitor.h.

Member Typedef Documentation

◆ Data

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

typedef Size DGtal::DepthFirstVisitor< TGraph, TMarkSet >::Data

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

Definition at line 104 of file DepthFirstVisitor.h.

◆ Graph

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

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

Definition at line 100 of file DepthFirstVisitor.h.

◆ MarkSet

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

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

Definition at line 101 of file DepthFirstVisitor.h.

◆ Node

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

typedef std::pair< Vertex, Data > DGtal::DepthFirstVisitor< TGraph, TMarkSet >::Node

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

Definition at line 115 of file DepthFirstVisitor.h.

◆ NodeQueue

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

typedef std::stack< Node > DGtal::DepthFirstVisitor< TGraph, TMarkSet >::NodeQueue

Internal data structure for computing the depth-first expansion.

Definition at line 117 of file DepthFirstVisitor.h.

◆ Self

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

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

Definition at line 99 of file DepthFirstVisitor.h.

◆ Size

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

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

Definition at line 102 of file DepthFirstVisitor.h.

◆ Vertex

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

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

Definition at line 103 of file DepthFirstVisitor.h.

◆ VertexList

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

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

Internal data structure for storing vertices.

Definition at line 119 of file DepthFirstVisitor.h.

Constructor & Destructor Documentation

◆ ~DepthFirstVisitor()

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

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

Destructor.

◆ DepthFirstVisitor() [1/5]

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

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

Copy constructor.

Parameters

other the object to clone.

◆ DepthFirstVisitor() [2/5]

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

DGtal::DepthFirstVisitor< TGraph, TMarkSet >::DepthFirstVisitor ( ConstAlias< Graph > graph )

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 depth first traversal takes place.

◆ DepthFirstVisitor() [3/5]

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

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

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

Parameters

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

◆ DepthFirstVisitor() [4/5]

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

template<typename VertexIterator >

DGtal::DepthFirstVisitor< TGraph, TMarkSet >::DepthFirstVisitor	(	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 depth first traversal. These vertices will all have a topological depth. 0.

Template Parameters

VertexIterator any type of single pass iterator on vertices.

Parameters

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

◆ DepthFirstVisitor() [5/5]

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

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

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::DepthFirstVisitor< 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 testDepthFirstPropagation().

◆ expand() [1/2]

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

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

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

Referenced by testDepthFirstPropagation().

◆ expand() [2/2]

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

template<typename VertexPredicate >

void DGtal::DepthFirstVisitor< 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

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>

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

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

Referenced by testDepthFirstPropagation().

◆ graph()

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

const Graph & DGtal::DepthFirstVisitor< 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::DepthFirstVisitor< 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()'.

◆ isValid()

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

bool DGtal::DepthFirstVisitor< 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::DepthFirstVisitor< 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.

◆ operator=()

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

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

private

Assignment.

Parameters

other the object to copy.

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

◆ selfDisplay()

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

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

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>

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

Force termination of the depth 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::DepthFirstVisitor< 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::DepthFirstVisitor< TGraph, TMarkSet >::myGraph

private

The graph where the traversal takes place.

Definition at line 276 of file DepthFirstVisitor.h.

◆ myMarkedVertices

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

MarkSet DGtal::DepthFirstVisitor< 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 DepthFirstVisitor.h.

◆ myQueue

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

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

private

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

Definition at line 289 of file DepthFirstVisitor.h.

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

DepthFirstVisitor.h

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Data

◆ Graph

◆ MarkSet

◆ Node

◆ NodeQueue

◆ Self

◆ Size

◆ Vertex

◆ VertexList

Constructor & Destructor Documentation

◆ ~DepthFirstVisitor()

◆ DepthFirstVisitor() [1/5]

◆ DepthFirstVisitor() [2/5]

◆ DepthFirstVisitor() [3/5]

◆ DepthFirstVisitor() [4/5]

◆ DepthFirstVisitor() [5/5]

Member Function Documentation

◆ current()

◆ expand() [1/2]

◆ expand() [2/2]

◆ finished()

◆ graph()

◆ ignore()

◆ isValid()

◆ markedVertices()

◆ operator=()

◆ selfDisplay()

◆ terminate()

◆ visitedVertices()

Field Documentation

◆ myGraph

◆ myMarkedVertices

◆ myQueue