DGtal  0.9.3beta
Data Structures | Public Types | Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes
DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet > Class Template Reference

#include <DGtal/graph/DistanceBreadthFirstVisitor.h>

Collaboration diagram for DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >:
[legend]

Data Structures

struct  Node
 

Public Types

typedef DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet > Self
 
typedef TGraph Graph
 
typedef TVertexFunctor VertexFunctor
 
typedef TMarkSet MarkSet
 
typedef Graph::Size Size
 
typedef Graph::Vertex Vertex
 
typedef VertexFunctor::Value Scalar
 
typedef Scalar Data
 
typedef std::priority_queue< NodeNodeQueue
 
typedef std::vector< VertexVertexList
 

Public Member Functions

 ~DistanceBreadthFirstVisitor ()
 
 DistanceBreadthFirstVisitor (const DistanceBreadthFirstVisitor &other)
 
 DistanceBreadthFirstVisitor (ConstAlias< Graph > graph, const VertexFunctor &distance, const Vertex &p)
 
template<typename VertexIterator >
 DistanceBreadthFirstVisitor (const Graph &graph, const VertexFunctor &distance, VertexIterator b, VertexIterator e)
 
const Graphgraph () const
 
const Nodecurrent () const
 
template<typename TBackInsertionSequence >
void getCurrentLayer (TBackInsertionSequence &layer)
 
void ignore ()
 
void ignoreLayer ()
 
void expand ()
 
void expandLayer ()
 
template<typename VertexPredicate >
void expand (const VertexPredicate &authorized_vtx)
 
template<typename VertexPredicate >
void expandLayer (const VertexPredicate &authorized_vtx)
 
bool finished () const
 
void terminate ()
 
const MarkSetmarkedVertices () const
 
MarkSet visitedVertices () const
 
void pushAgain (const Node &node)
 
void swap (DistanceBreadthFirstVisitor &other)
 
void selfDisplay (std::ostream &out) const
 
bool isValid () const
 

Protected Member Functions

 DistanceBreadthFirstVisitor ()
 

Private Member Functions

DistanceBreadthFirstVisitoroperator= (const DistanceBreadthFirstVisitor &other)
 

Private Attributes

const GraphmyGraph
 
VertexFunctor myDistance
 
MarkSet myMarkedVertices
 
NodeQueue myQueue
 

Detailed Description

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

Aim: This class is useful to perform an exploration of a graph given a starting point or set (called initial core) and a distance criterion.

Description of template class 'DistanceBreadthFirstVisitor'

The visitor implements a modified breadth-first algorithm on the graph of adjacencies that is based on a priority queue, the priority of which is given by the distance object (and not by the topological distance as in classical breadth-first traversal). 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 visitor is by definition at the beginning the set of points at the lowest distances. A layer is a set of vertices at the same distance. The visitor can visit one vertex at a time or one layer at a time. Each layer is at a different distance from the initial core, layers having increasing distances.

The object guarantees that vertices are visited in a non-decreasing ordering with respect to the distance object, as long as the breadth-first traversal order can be consistent with the given distance ordering.

Template Parameters
TGraphthe type of the graph, a model of CUndirectedSimpleLocalGraph. It must have an inner type Vertex.
TVertexFunctorthe type of distance object: any mapping from a Vertex toward a scalar value. Requires an inner type Value which is the returned scalar value and an operator()( Vertex ) returning a Value. The neighboring relations of the graph should be consistent with the distance function, in the sense that the closest points to the current set of already visited vertices should be found in the neighbors.
TMarkSetthe type that is used to store marked vertices. Should be a set of Vertex, hence a model of CSet.
#include "DGtal/geometry/volumes/distance/ExactPredicateLpSeparableMetric.h"
...
Graph g( ... );
Graph::Vertex p( ... );
typedef CanonicSCellEmbedder<KSpace> VertexEmbedder;
typedef VertexEmbedder::Value RealPoint;
typedef RealPoint::Coordinate Scalar;
typedef ExactPredicateLpSeparableMetric<Space,2> Distance; // Euclidean distance
typedef std::binder1st< Distance > EDToPoint; // Fix one point
typedef Composer<VertexEmbedder, EDToPoint, Scalar> VertexFunctor;
// Compose the vertex embedding with the distance computation.
typedef DistanceBreadthFirstVisitor< Graph, VertexFunctor > Visitor;
VertexEmbedder embedder( g.space() ); //We assume the graph to be a DigitalSurface
ED distance;
EDToPoint distanceToPoint = std::bind1st( distance, embedder( p ) );
VertexFunctor vfunctor( embedder, distanceToPoint );
DistanceBreadthFirstVisitor< Graph, VertexFunctor > visitor( g, vfunctor, p );
while ( ! visitor.finished() )
{
DistanceBreadthFirstVisitor<Graph>::Node node = visitor.current();
std::cout << "Vertex " << node.first
<< " at distance " << node.second << std::endl;
visitor.expand();
}

You may also visit vertices layer by layer, meaning that you wish to consider all the vertices at the same distance at the same time. You should use then DistanceBreadthFirstVisitor::getCurrentLayer, DistanceBreadthFirstVisitor::expandLayer, and DistanceBreadthFirstVisitor::ignoreLayer.

std::list<Node> layer;
std::vector<Node> lateLayer;
while ( ! visitor.finished() )
{
// Get all vertices at same distance from starting vertex.
visitor.getCurrentLayer( layer );
// Do something with the layer ...
for ( typename std::vector<Node>::const_iterator it = layer.begin(),
itE = layer.end(); it != itE; ++it )
{ //...
}
visitor.expandLayer();
}

If the bread-first queueing system is not compatible with the distance function, then it has two consequences:

std::list<Node> layer;
std::vector<Node> lateLayer;
while ( ! visitor.finished() )
{
// Get all vertices at same distance from starting vertex.
visitor.getCurrentLayer( layer );
// Do something with the layer ...
for ( typename std::vector<Node>::const_iterator it = layer.begin(),
itE = layer.end(); it != itE; ++it )
{ //...
}
// Visit the nodes one at a time to expand or ignore depending
// on your application. Be careful, the nodes may not be in the
// same order and some other nodes could pop out in-between.
while ( ! layer.empty() )
{
Node n = visitor.current();
std::list<Node>::iterator it = layer.begin();
std::list<Node>::iterator itE = layer.end();
while ( ( it != itE ) && ( (it).first != n.first ) ) ++it;
if ( it == itE )
{ // Node that is not in the expected order.
lateLayer.push_back( n );
myVisitor.ignore();
}
else
{ // Process node n, decide to expand or ignore it.
if ( aBool ) visitor.expand();
else visitor.ignore();
// Erase it.
layer.erase( it );
}
}
// Push back "late" vertices in the visitor.
for ( typename std::vector<Node>::const_iterator
it = lateLayer.begin(),
itE = lateLayer.end(); it != itE; ++it )
{
visitor.pushAgain( *it );
}
lateLayer.clear();
}
See also
testDistancePropagation.cpp
testObject.cpp
Examples:
graph/volDistanceTraversal.cpp.

Definition at line 205 of file DistanceBreadthFirstVisitor.h.

Member Typedef Documentation

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
typedef Scalar DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::Data

Definition at line 216 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
typedef TGraph DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::Graph

Definition at line 210 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
typedef TMarkSet DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::MarkSet

Definition at line 212 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
typedef std::priority_queue< Node > DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::NodeQueue

Internal data structure for computing the distance ordering expansion.

Definition at line 263 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
typedef VertexFunctor::Value DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::Scalar

Definition at line 215 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
typedef DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet> DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::Self

Definition at line 209 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
typedef Graph::Size DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::Size

Definition at line 213 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
typedef Graph::Vertex DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::Vertex

Definition at line 214 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
typedef TVertexFunctor DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::VertexFunctor

Definition at line 211 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
typedef std::vector< Vertex > DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::VertexList

Internal data structure for storing vertices.

Definition at line 265 of file DistanceBreadthFirstVisitor.h.

Constructor & Destructor Documentation

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::~DistanceBreadthFirstVisitor ( )

Destructor.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::DistanceBreadthFirstVisitor ( const DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet > &  other)

Copy constructor.

Parameters
otherthe object to clone.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::DistanceBreadthFirstVisitor ( ConstAlias< Graph graph,
const VertexFunctor distance,
const Vertex p 
)

Constructor from a point and a vertex functor object. This point provides the initial core of the visitor.

Parameters
graphthe graph in which the distance ordering traversal takes place (aliased).
distancethe distance object, a functor Vertex -> Scalar (cloned).
pany vertex of the graph.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
template<typename VertexIterator >
DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::DistanceBreadthFirstVisitor ( const Graph graph,
const VertexFunctor distance,
VertexIterator  b,
VertexIterator  e 
)

Constructor from a graph, a vertex functor and two iterators specifying a range. All vertices visited between the iterators should be distinct two by two. The so specified set of vertices provides the initial core of the distance ordering traversal.

Template Parameters
VertexIteratorany type of single pass iterator on vertices.
Parameters
graphthe graph in which the distance ordering traversal takes place (aliased).
distancethe distance object, a functor Vertex -> Scalar (cloned).
bthe begin iterator in a container of vertices.
ethe end iterator in a container of vertices.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::DistanceBreadthFirstVisitor ( )
protected

Constructor. Forbidden by default (protected to avoid g++ warnings).

Member Function Documentation

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
const Node& DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::current ( ) const
Returns
a const reference on the current visited vertex. The node is a pair <Vertex,Scalar> where the second term is the distance to the initial vertex or set.

NB: valid only if not 'finished()'.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::expand ( )

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

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
template<typename VertexPredicate >
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::expand ( const VertexPredicate &  authorized_vtx)

Goes to the next vertex and take into account the current vertex for determining the future visited vertices.

Template Parameters
VertexPredicatea type that satisfies CPredicate on Vertex.
Parameters
authorized_vtxthe predicate that should satisfy the visited vertices.

NB: valid only if not 'finished()'.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::expandLayer ( )

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

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
template<typename VertexPredicate >
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::expandLayer ( const VertexPredicate &  authorized_vtx)

Goes to the next layer and take into account the current layer for determining the future vsited vertices.

Template Parameters
VertexPredicatea type that satisfies CPredicate on Vertex.
Parameters
authorized_vtxthe predicate that should satisfy the visited vertices.

NB: valid only if not 'finished()'.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
bool DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::finished ( ) const
Returns
'true' if all possible elements have been visited.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
template<typename TBackInsertionSequence >
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::getCurrentLayer ( TBackInsertionSequence &  layer)

Returns all nodes at same current distance in the given container layer. The node is a pair <Vertex,Scalar> where the second term is the distance to the initial vertex or set.

Template Parameters
TBackInsertionSequencea container of Node that is any model of boost::BackInsertionSequence.
Parameters
[out]layera container object that will contain all the nodes at the same current distance.

NB: Complexity is in O(k log n ), where k is the size of the layer and n the number of elements currently in the priority queue (some O(k)).

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
const Graph& DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::graph ( ) const
Returns
a const reference on the graph that is traversed.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, 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()'.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::ignoreLayer ( )

Goes to the next layer but ignores the current layer for determining the future visited vertices. Otherwise said, no future visited vertex will have any vertex of this layer as a father.

NB: valid only if not 'finished()'.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
bool DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::isValid ( ) const

Checks the validity/consistency of the object.

Returns
'true' if the object is valid, 'false' otherwise.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
const MarkSet& DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, 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.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
DistanceBreadthFirstVisitor& DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::operator= ( const DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet > &  other)
private

Assignment.

Parameters
otherthe object to copy.
Returns
a reference on 'this'. Forbidden by default.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::pushAgain ( const Node node)

Push backs some node in the queue. The node should have been ignored previously at some point. Useful when the distance is not truely a distance function.

Parameters
nodea pair Vertex, distance.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::selfDisplay ( std::ostream &  out) const

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::swap ( DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet > &  other)

Exchange 'this' object with 'other'. O(1) operations since containers are swapped (if the VertexFunctor is assignable in O(1)).

Parameters
otherthe other instance.
template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
void DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::terminate ( )

Force termination of the distance ordering traversal. 'finished()' returns 'true' afterwards and 'current()', 'expand()', 'ignore()' have no more meaning. Furthermore, 'markedVertices()' and 'visitedVertices()' both represents the set of visited vertices.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
MarkSet DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, 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

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
VertexFunctor DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::myDistance
private

The distance object, a functor Vertex -> Scalar.

Definition at line 488 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
const Graph* DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::myGraph
private

The graph where the traversal takes place.

Definition at line 483 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
MarkSet DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::myMarkedVertices
private

Set representing the marked vertices: the ones that have been visited and the ones that are going to be visited soon (at closest distance).

Definition at line 495 of file DistanceBreadthFirstVisitor.h.

template<typename TGraph, typename TVertexFunctor, typename TMarkSet = typename TGraph::VertexSet>
NodeQueue DGtal::DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet >::myQueue
private

Queue storing the vertices that are the next visited ones in the distance ordering traversal of the graph.

Definition at line 501 of file DistanceBreadthFirstVisitor.h.


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