DGtal  0.9.3beta
Public Types | Public Member Functions | Private Attributes
DGtal::concepts::CGraphVisitor< T > Struct Template Reference

#include <DGtal/graph/CGraphVisitor.h>

Inheritance diagram for DGtal::concepts::CGraphVisitor< T >:
[legend]
Collaboration 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 :

Notation

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

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

Definition at line 118 of file CGraphVisitor.h.

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

Definition at line 115 of file CGraphVisitor.h.

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

Definition at line 119 of file CGraphVisitor.h.

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

Definition at line 120 of file CGraphVisitor.h.

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

Definition at line 117 of file CGraphVisitor.h.

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

Definition at line 116 of file CGraphVisitor.h.

Definition at line 121 of file CGraphVisitor.h.

Member Function Documentation

template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (CUndirectedSimpleLocalGraph< Graph >)  )
template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (boost::SimpleAssociativeContainer< MarkSet >)  )
template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (boost::UniqueAssociativeContainer< MarkSet >)  )
template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (boost::DefaultConstructible< Data >)  )
template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (boost::Assignable< Data >)  )
template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_ASSERT ( (boost::CopyConstructible< Data >)  )
template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_CONCEPT_USAGE ( CGraphVisitor< T >  )
inline

Definition at line 136 of file CGraphVisitor.h.

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

137  {
138  // check non-const methods.
139  myX.expand();
140  myX.expand( myVPred );
141  myX.ignore();
142  myX.terminate();
143  // check const methods.
145  }
template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_STATIC_ASSERT ( (ConceptUtils::SameType< Vertex, typename Graph::Vertex >::value)  )
template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_STATIC_ASSERT ( (ConceptUtils::SameType< Size, typename Graph::Size >::value)  )
template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_STATIC_ASSERT ( (ConceptUtils::SameType< Vertex, typename MarkSet::key_type >::value)  )
template<typename T >
DGtal::concepts::CGraphVisitor< T >::BOOST_STATIC_ASSERT ( (boost::is_convertible< Node, std::pair< Vertex, Data > >::value)  )
template<typename T >
void DGtal::concepts::CGraphVisitor< T >::checkConstConstraints ( ) const
inline

Field Documentation

template<typename T >
bool DGtal::concepts::CGraphVisitor< T >::myBool
private
template<typename T >
Graph DGtal::concepts::CGraphVisitor< T >::myGraph
private
template<typename T >
MarkSet DGtal::concepts::CGraphVisitor< T >::myMarkSet
private
template<typename T >
Node DGtal::concepts::CGraphVisitor< T >::myNode
private
template<typename T >
VertexPredicate DGtal::concepts::CGraphVisitor< T >::myVPred
private
template<typename T >
T DGtal::concepts::CGraphVisitor< T >::myX
private

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