DGtal  1.5.beta
DGtal::concepts::CGraphVisitor< T > Struct Template Reference

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

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

myX
 
Graph myGraph
 
Node myNode
 
bool myBool
 
VertexPredicate myVPred
 
MarkSet myMarkSet
 

Detailed Description

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

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.

Description of concept 'CGraphVisitor'

Refinement of

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

Notes

Template Parameters
Tthe 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

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.

137  {
138  // check non-const methods.
139  myX.expand();
140  myX.expand( myVPred );
141  myX.ignore();
142  myX.terminate();
143  // check const methods.
145  }

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

Field Documentation

◆ myBool

template<typename T >
bool DGtal::concepts::CGraphVisitor< T >::myBool
private

◆ myGraph

template<typename T >
Graph DGtal::concepts::CGraphVisitor< T >::myGraph
private

◆ myMarkSet

template<typename T >
MarkSet DGtal::concepts::CGraphVisitor< T >::myMarkSet
private

◆ myNode

template<typename T >
Node DGtal::concepts::CGraphVisitor< T >::myNode
private

◆ myVPred

template<typename T >
VertexPredicate DGtal::concepts::CGraphVisitor< T >::myVPred
private

◆ myX


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