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'
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.
- X : A type that is a model of CGraphVisitor
- x, y : object of type X
Valid expressions and semantics
|Name ||Expression ||Type requirements ||Return type ||Precondition ||Semantics ||Post condition ||Complexity |
|Get visited graph ||x.graph() |
|Return a const reference to the visited graph ||O(1) |
|Get current node ||x.current() |
|! 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() |
|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() == |
|Get set of marked vertices ||x.markedVertices() |
|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() |
|Returns the current set of visited vertices (equal to markedVertices() whenever x.finished() ). ||linear time in the number of marked vertices. |
- Template Parameters
Definition at line 110 of file CGraphVisitor.h.