Aim: Defines the concept of a visitor onto a graph, that is an object that traverses vertices of the graph according to some order. The user can either use the visitor as is, or even constrain the traversal with a given predicate. More...

#include <DGtal/graph/CGraphVisitor.h>

Inheritance diagram for DGtal::concepts::CGraphVisitor< T >:

[legend]

Public Types
typedef T::Graph	Graph

typedef T::Vertex	Vertex

typedef T::Size	Size

typedef T::Data	Data

typedef T::MarkSet	MarkSet

typedef T::Node	Node

typedef CVertexPredicateArchetype< Vertex >	VertexPredicate

Public Member Functions
	BOOST_CONCEPT_ASSERT ((CUndirectedSimpleLocalGraph< Graph >))

	BOOST_STATIC_ASSERT ((ConceptUtils::SameType< Vertex, typename Graph::Vertex >::value))

	BOOST_STATIC_ASSERT ((ConceptUtils::SameType< Size, typename Graph::Size >::value))

	BOOST_CONCEPT_ASSERT ((boost::SimpleAssociativeContainer< MarkSet >))

	BOOST_CONCEPT_ASSERT ((boost::UniqueAssociativeContainer< MarkSet >))

	BOOST_STATIC_ASSERT ((ConceptUtils::SameType< Vertex, typename MarkSet::key_type >::value))

	BOOST_CONCEPT_ASSERT ((boost::DefaultConstructible< Data >))

	BOOST_CONCEPT_ASSERT ((boost::Assignable< Data >))

	BOOST_CONCEPT_ASSERT ((boost::CopyConstructible< Data >))

	BOOST_STATIC_ASSERT ((boost::is_convertible< Node, std::pair< Vertex, Data > >::value))

	BOOST_CONCEPT_USAGE (CGraphVisitor)

void	checkConstConstraints () const

Private Attributes
T	myX

Graph	myGraph

Node	myNode

bool	myBool

VertexPredicate	myVPred

MarkSet	myMarkSet

Detailed Description

template<typename T>
struct DGtal::concepts::CGraphVisitor< T >

Description of concept 'CGraphVisitor'

Refinement of

boost::CopyConstructible

Associated types

Graph: the type of the graph that the visitor visits, must be a model of CUndirectedSimpleLocalGraph.
Vertex: the type for of each vertex, must be Graph::Vertex.
Size: the type used for counting vertices in the graph, must be Graph::Size.
MarkSet: the type used for representing a set of marked vertices, a model of boost::SimpleAssociativeContainer and boost::UniqueAssociativeContainer, whose key type / value type is Vertex.
Data: the type is associated to the current node and may be used for several purposes (like measuring the distance between the current element and the starting point/set), a model of boost::DefaultConstructible, boost::Assignable, boost::CopyConstructible.
Node: either the pair<Vertex,Data> or a type convertible to the pair<Vertex,Data>, where Vertex is the current node, Data is the attached data.

Notation

X : A type that is a model of CGraphVisitor
x, y : object of type X

Definitions

Valid expressions and semantics

Name	Expression	Type requirements	Return type	Precondition	Semantics	Post condition	Complexity
Get visited graph	x.graph()		`Graph`		Return a const reference to the visited graph		O(1)
Get current node	x.current()		`Node`	! x.finished()	Return the current visited vertex and its distance		O(1)
Expand to next vertex	x.expand()			! x.finished()	Goes to the next vertex, while taking into account the current vertex for determining the future visited vertices.		amortized logarithmic time
Expand to next vertex	x.expand(p)	p is a model of CVertexPredicate		! x.finished()	Goes to the next vertex, while taking into account the current vertex for determining the future visited vertices (which must satisfy predicate p).		amortized logarithmic time
Jump to next vertex	x.ignore()			! x.finished()	Goes to the next vertex but ignores the current vertex when determining the future visited vertices.		amortized logarithmic time
Termination test	x.finished()		`bool`		Return true if and only if the visitor has traversed all autorized vertices.		O(1)
Force termination	x.terminate()				Force a premature termination of the traversal.	x.finished() == `true`
Get set of marked vertices	x.markedVertices()		`MarkSet`		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.		O(1)
Get set of visited vertices	x.visitedVertices()		`MarkSet`		Returns the current set of visited vertices (equal to markedVertices() whenever x.finished() ).		linear time in the number of marked vertices.

Invariants

Models

BreadthFirstVisitor, DepthFirstVisitor, DistanceVisitor

Notes

Template Parameters

T	the type that should be a model of CGraphVisitor.

Definition at line 110 of file CGraphVisitor.h.

Member Typedef Documentation

◆ Data

template<typename T >

typedef T::Data DGtal::concepts::CGraphVisitor< T >::Data

Definition at line 118 of file CGraphVisitor.h.

◆ Graph

template<typename T >

typedef T::Graph DGtal::concepts::CGraphVisitor< T >::Graph

Definition at line 115 of file CGraphVisitor.h.

◆ MarkSet

template<typename T >

typedef T::MarkSet DGtal::concepts::CGraphVisitor< T >::MarkSet

Definition at line 119 of file CGraphVisitor.h.

◆ Node

template<typename T >

typedef T::Node DGtal::concepts::CGraphVisitor< T >::Node

Definition at line 120 of file CGraphVisitor.h.

◆ Size

template<typename T >

typedef T::Size DGtal::concepts::CGraphVisitor< T >::Size

Definition at line 117 of file CGraphVisitor.h.

◆ Vertex

template<typename T >

typedef T::Vertex DGtal::concepts::CGraphVisitor< T >::Vertex

Definition at line 116 of file CGraphVisitor.h.

◆ VertexPredicate

template<typename T >

typedef CVertexPredicateArchetype<Vertex> DGtal::concepts::CGraphVisitor< T >::VertexPredicate

Definition at line 121 of file CGraphVisitor.h.

Member Function Documentation

◆ BOOST_CONCEPT_ASSERT() [1/6]

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (boost::Assignable< Data >) )

◆ BOOST_CONCEPT_ASSERT() [2/6]

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (boost::CopyConstructible< Data >) )

◆ BOOST_CONCEPT_ASSERT() [3/6]

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (boost::DefaultConstructible< Data >) )

◆ BOOST_CONCEPT_ASSERT() [4/6]

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (boost::SimpleAssociativeContainer< MarkSet >) )

◆ BOOST_CONCEPT_ASSERT() [5/6]

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (boost::UniqueAssociativeContainer< MarkSet >) )

◆ BOOST_CONCEPT_ASSERT() [6/6]

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (CUndirectedSimpleLocalGraph< Graph >) )

◆ BOOST_CONCEPT_USAGE()

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_USAGE ( CGraphVisitor< T > )

inline

Definition at line 136 of file CGraphVisitor.h.

   {
     // check non-const methods.
     myX.expand();
     myX.expand( myVPred );
     myX.ignore();
     myX.terminate();
     // check const methods.
     checkConstConstraints();
   }

References DGtal::concepts::CGraphVisitor< T >::checkConstConstraints(), DGtal::concepts::CGraphVisitor< T >::myVPred, and DGtal::concepts::CGraphVisitor< T >::myX.

◆ BOOST_STATIC_ASSERT() [1/4]

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_STATIC_ASSERT ( (boost::is_convertible< Node, std::pair< Vertex, Data > >::value) )

◆ BOOST_STATIC_ASSERT() [2/4]

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_STATIC_ASSERT ( (ConceptUtils::SameType< Size, typename Graph::Size >::value) )

◆ BOOST_STATIC_ASSERT() [3/4]

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_STATIC_ASSERT ( (ConceptUtils::SameType< Vertex, typename Graph::Vertex >::value) )

◆ BOOST_STATIC_ASSERT() [4/4]

template<typename T >

DGtal::concepts::CGraphVisitor< T >::BOOST_STATIC_ASSERT ( (ConceptUtils::SameType< Vertex, typename MarkSet::key_type >::value) )

◆ checkConstConstraints()

template<typename T >

void DGtal::concepts::CGraphVisitor< T >::checkConstConstraints ( ) const

inline

Definition at line 146 of file CGraphVisitor.h.

   {
     ConceptUtils::sameType( myGraph, myX.graph() );
     ConceptUtils::sameType( myNode, myX.current() );
     ConceptUtils::sameType( myBool, myX.finished() );
     ConceptUtils::sameType( myMarkSet, myX.markedVertices() );
     ConceptUtils::sameType( myMarkSet, myX.visitedVertices() );
   }