DGtal  1.3.beta
DistanceBreadthFirstVisitor.h
1 
17 #pragma once
18 
31 #if defined(DistanceBreadthFirstVisitor_RECURSES)
32 #error Recursive header files inclusion detected in DistanceBreadthFirstVisitor.h
33 #else // defined(DistanceBreadthFirstVisitor_RECURSES)
34 
35 #define DistanceBreadthFirstVisitor_RECURSES
36 
37 #if !defined DistanceBreadthFirstVisitor_h
38 
39 #define DistanceBreadthFirstVisitor_h
40 
42 // Inclusions
43 #include <iostream>
44 #include <queue>
45 #include "DGtal/base/Common.h"
46 #include "DGtal/base/ConstAlias.h"
47 #include "DGtal/base/CountedPtr.h"
48 #include "DGtal/graph/CUndirectedSimpleLocalGraph.h"
50 
51 namespace DGtal
52 {
53 
55  // template class DistanceBreadthFirstVisitor
202  template < typename TGraph,
203  typename TVertexFunctor,
204  typename TMarkSet = typename TGraph::VertexSet >
206  {
207  // ----------------------- Associated types ------------------------------
208  public:
210  typedef TGraph Graph;
211  typedef TVertexFunctor VertexFunctor;
212  typedef TMarkSet MarkSet;
213  typedef typename Graph::Size Size;
214  typedef typename Graph::Vertex Vertex;
215  typedef typename VertexFunctor::Value Scalar;
216  typedef Scalar Data;
217 
218  // Cannot check this since some types using it are incomplete.
219  // BOOST_CONCEPT_ASSERT(( CUndirectedSimpleLocalGraph< Graph > ));
220  // BOOST_CONCEPT_ASSERT(( CSet< MarkSet, Vertex > ));
221 
222  // ----------------------- defined types ------------------------------
223  public:
224 
229  struct Node : public std::pair< Vertex, Scalar >
230  {
231  typedef std::pair< Vertex, Scalar > Base;
232  using Base::first;
233  using Base::second;
234 
235  inline Node()
236  : std::pair< Vertex, Scalar >()
237  {}
238  inline Node( const Node & other )
239  : std::pair< Vertex, Scalar >( other )
240  {}
241  inline Node( const Vertex & v, Scalar d )
242  : std::pair< Vertex, Scalar >( v, d )
243  {}
244  inline bool operator<( const Node & other ) const
245  {
246  return other.second < second;
247  }
248  inline bool operator<=( const Node & other ) const
249  {
250  return other.second <= second;
251  }
252  inline bool operator==( const Node & other ) const
253  {
254  return other.second == second;
255  }
256  inline bool operator!=( const Node & other ) const
257  {
258  return other.second != second;
259  }
260  };
261 
263  typedef std::priority_queue< Node > NodeQueue;
265  typedef std::vector< Vertex > VertexList;
266 
267  // ----------------------- Standard services ------------------------------
268  public:
269 
274 
280 
281 
291  const VertexFunctor & distance,
292  const Vertex & p );
293 
307  template <typename VertexIterator>
309  const VertexFunctor & distance,
310  VertexIterator b, VertexIterator e );
311 
312 
316  const Graph & graph() const;
317 
318  // ----------------------- traversal services ------------------------------
319  public:
320 
328  const Node & current() const;
329 
345  template <typename TBackInsertionSequence>
346  void getCurrentLayer( TBackInsertionSequence & layer );
347 
355  void ignore();
356 
365  void ignoreLayer();
366 
372  void expand();
373 
379  void expandLayer();
380 
392  template <typename VertexPredicate>
393  void expand( const VertexPredicate & authorized_vtx );
394 
406  template <typename VertexPredicate>
407  void expandLayer( const VertexPredicate & authorized_vtx );
408 
412  bool finished() const;
413 
421  void terminate();
422 
428  const MarkSet & markedVertices() const;
429 
442  MarkSet visitedVertices() const;
443 
450  void pushAgain( const Node & node );
451 
452 
458  void swap( DistanceBreadthFirstVisitor & other );
459 
460  // ----------------------- Interface --------------------------------------
461  public:
462 
467  void selfDisplay ( std::ostream & out ) const;
468 
473  bool isValid() const;
474 
475  // ------------------------- Protected Datas ------------------------------
476  private:
477  // ------------------------- Private Datas --------------------------------
478  private:
479 
483  const Graph* myGraph;
484 
489 
496 
502 
503  // ------------------------- Hidden services ------------------------------
504  protected:
505 
511 
512  private:
513 
521 
522  // ------------------------- Internals ------------------------------------
523  private:
524 
525  }; // end of class DistanceBreadthFirstVisitor
526 
527 
534  template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
535  std::ostream&
536  operator<< ( std::ostream & out,
538 
539 } // namespace DGtal
540 
541 
543 // Includes inline functions.
544 #include "DGtal/graph/DistanceBreadthFirstVisitor.ih"
545 
546 // //
548 
549 #endif // !defined DistanceBreadthFirstVisitor_h
550 
551 #undef DistanceBreadthFirstVisitor_RECURSES
552 #endif // else defined(DistanceBreadthFirstVisitor_RECURSES)
DGtal::DistanceBreadthFirstVisitor::Data
Scalar Data
Definition: DistanceBreadthFirstVisitor.h:216
DGtal::DistanceBreadthFirstVisitor::current
const Node & current() const
DGtal::DistanceBreadthFirstVisitor::Node::Node
Node(const Node &other)
Definition: DistanceBreadthFirstVisitor.h:238
DGtal::DistanceBreadthFirstVisitor::Scalar
VertexFunctor::Value Scalar
Definition: DistanceBreadthFirstVisitor.h:215
DGtal::ConstAlias
Aim: This class encapsulates its parameter class so that to indicate to the user that the object/poin...
Definition: ConstAlias.h:186
DGtal::DistanceBreadthFirstVisitor::myDistance
VertexFunctor myDistance
Definition: DistanceBreadthFirstVisitor.h:488
DGtal::DistanceBreadthFirstVisitor::visitedVertices
MarkSet visitedVertices() const
DGtal::DistanceBreadthFirstVisitor::NodeQueue
std::priority_queue< Node > NodeQueue
Internal data structure for computing the distance ordering expansion.
Definition: DistanceBreadthFirstVisitor.h:263
DGtal::DistanceBreadthFirstVisitor::finished
bool finished() const
DGtal::DistanceBreadthFirstVisitor::operator=
DistanceBreadthFirstVisitor & operator=(const DistanceBreadthFirstVisitor &other)
DGtal::DistanceBreadthFirstVisitor::expandLayer
void expandLayer()
DGtal::DistanceBreadthFirstVisitor::graph
const Graph & graph() const
DGtal::DistanceBreadthFirstVisitor::Node::operator==
bool operator==(const Node &other) const
Definition: DistanceBreadthFirstVisitor.h:252
DGtal::DistanceBreadthFirstVisitor::terminate
void terminate()
DGtal::DistanceBreadthFirstVisitor::Node::Node
Node(const Vertex &v, Scalar d)
Definition: DistanceBreadthFirstVisitor.h:241
DGtal::DistanceBreadthFirstVisitor::markedVertices
const MarkSet & markedVertices() const
DGtal::DistanceBreadthFirstVisitor::pushAgain
void pushAgain(const Node &node)
DGtal::DistanceBreadthFirstVisitor::Size
Graph::Size Size
Definition: DistanceBreadthFirstVisitor.h:213
Vertex
TriMesh::Vertex Vertex
Definition: testTriangulatedSurface.cpp:57
Size
HalfEdgeDataStructure::Size Size
Definition: testHalfEdgeDataStructure.cpp:50
DGtal::operator<<
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
DGtal::DistanceBreadthFirstVisitor::Vertex
Graph::Vertex Vertex
Definition: DistanceBreadthFirstVisitor.h:214
DGtal::DistanceBreadthFirstVisitor::expand
void expand()
DGtal::DistanceBreadthFirstVisitor::Node
Definition: DistanceBreadthFirstVisitor.h:229
DGtal::DistanceBreadthFirstVisitor::Node::Node
Node()
Definition: DistanceBreadthFirstVisitor.h:235
DGtal::DistanceBreadthFirstVisitor::ignore
void ignore()
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::DistanceBreadthFirstVisitor::Node::Base
std::pair< Vertex, Scalar > Base
Definition: DistanceBreadthFirstVisitor.h:231
DGtal::DistanceBreadthFirstVisitor
Aim: This class is useful to perform an exploration of a graph given a starting point or set (called ...
Definition: DistanceBreadthFirstVisitor.h:205
DGtal::DistanceBreadthFirstVisitor::myGraph
const Graph * myGraph
Definition: DistanceBreadthFirstVisitor.h:483
DGtal::DistanceBreadthFirstVisitor::DistanceBreadthFirstVisitor
DistanceBreadthFirstVisitor()
DGtal::DistanceBreadthFirstVisitor::ignoreLayer
void ignoreLayer()
DGtal::DistanceBreadthFirstVisitor::VertexFunctor
TVertexFunctor VertexFunctor
Definition: DistanceBreadthFirstVisitor.h:211
DGtal::DistanceBreadthFirstVisitor::myMarkedVertices
MarkSet myMarkedVertices
Definition: DistanceBreadthFirstVisitor.h:495
DGtal::DistanceBreadthFirstVisitor::isValid
bool isValid() const
DGtal::DistanceBreadthFirstVisitor::Node::operator<
bool operator<(const Node &other) const
Definition: DistanceBreadthFirstVisitor.h:244
DGtal::DistanceBreadthFirstVisitor::getCurrentLayer
void getCurrentLayer(TBackInsertionSequence &layer)
DGtal::DistanceBreadthFirstVisitor::swap
void swap(DistanceBreadthFirstVisitor &other)
DGtal::DistanceBreadthFirstVisitor::selfDisplay
void selfDisplay(std::ostream &out) const
DGtal::DistanceBreadthFirstVisitor::Node::operator!=
bool operator!=(const Node &other) const
Definition: DistanceBreadthFirstVisitor.h:256
DGtal::DistanceBreadthFirstVisitor::Self
DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet > Self
Definition: DistanceBreadthFirstVisitor.h:209
DGtal::DistanceBreadthFirstVisitor::~DistanceBreadthFirstVisitor
~DistanceBreadthFirstVisitor()
DGtal::DistanceBreadthFirstVisitor::VertexList
std::vector< Vertex > VertexList
Internal data structure for storing vertices.
Definition: DistanceBreadthFirstVisitor.h:265
DGtal::DistanceBreadthFirstVisitor::MarkSet
TMarkSet MarkSet
Definition: DistanceBreadthFirstVisitor.h:212
DGtal::DistanceBreadthFirstVisitor::Node::operator<=
bool operator<=(const Node &other) const
Definition: DistanceBreadthFirstVisitor.h:248
DGtal::DistanceBreadthFirstVisitor::Graph
TGraph Graph
Definition: DistanceBreadthFirstVisitor.h:210
DGtal::DistanceBreadthFirstVisitor::myQueue
NodeQueue myQueue
Definition: DistanceBreadthFirstVisitor.h:501
Value
double Value
Definition: testSimpleRandomAccessRangeFromPoint.cpp:38