DGtal  0.9.2
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>
308  DistanceBreadthFirstVisitor( const Graph & graph,
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 
488  VertexFunctor myDistance;
489 
496 
501  NodeQueue myQueue;
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)
Aim: This class is useful to perform an exploration of a graph given a starting point or set (called ...
Aim: This class encapsulates its parameter class so that to indicate to the user that the object/poin...
Definition: ConstAlias.h:186
void pushAgain(const Node &node)
STL namespace.
const Graph & graph() const
void selfDisplay(std::ostream &out) const
std::vector< Vertex > VertexList
Internal data structure for storing vertices.
const Node & current() const
std::ostream & operator<<(std::ostream &out, const ClosedIntegerHalfPlane< TSpace > &object)
DGtal is the top-level namespace which contains all DGtal functions and types.
void getCurrentLayer(TBackInsertionSequence &layer)
DistanceBreadthFirstVisitor & operator=(const DistanceBreadthFirstVisitor &other)
DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet > Self
std::priority_queue< Node > NodeQueue
Internal data structure for computing the distance ordering expansion.
const MarkSet & markedVertices() const
void swap(DistanceBreadthFirstVisitor &other)