DGtal  1.4.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)
35 #define DistanceBreadthFirstVisitor_RECURSES
36 
37 #if !defined DistanceBreadthFirstVisitor_h
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() = default;
236  inline Node( const Vertex & v, Scalar d )
237  : std::pair< Vertex, Scalar >( v, d )
238  {}
239  inline bool operator<( const Node & other ) const
240  {
241  return other.second < second;
242  }
243  inline bool operator<=( const Node & other ) const
244  {
245  return other.second <= second;
246  }
247  inline bool operator==( const Node & other ) const
248  {
249  return other.second == second;
250  }
251  inline bool operator!=( const Node & other ) const
252  {
253  return other.second != second;
254  }
255  };
256 
258  typedef std::priority_queue< Node > NodeQueue;
260  typedef std::vector< Vertex > VertexList;
261 
262  // ----------------------- Standard services ------------------------------
263  public:
264 
269 
275 
276 
286  const VertexFunctor & distance,
287  const Vertex & p );
288 
302  template <typename VertexIterator>
304  const VertexFunctor & distance,
305  VertexIterator b, VertexIterator e );
306 
307 
311  const Graph & graph() const;
312 
313  // ----------------------- traversal services ------------------------------
314  public:
315 
323  const Node & current() const;
324 
340  template <typename TBackInsertionSequence>
341  void getCurrentLayer( TBackInsertionSequence & layer );
342 
350  void ignore();
351 
360  void ignoreLayer();
361 
367  void expand();
368 
374  void expandLayer();
375 
387  template <typename VertexPredicate>
388  void expand( const VertexPredicate & authorized_vtx );
389 
401  template <typename VertexPredicate>
402  void expandLayer( const VertexPredicate & authorized_vtx );
403 
407  bool finished() const;
408 
416  void terminate();
417 
423  const MarkSet & markedVertices() const;
424 
438 
445  void pushAgain( const Node & node );
446 
447 
454 
455  // ----------------------- Interface --------------------------------------
456  public:
457 
462  void selfDisplay ( std::ostream & out ) const;
463 
468  bool isValid() const;
469 
470  // ------------------------- Protected Datas ------------------------------
471  private:
472  // ------------------------- Private Datas --------------------------------
473  private:
474 
478  const Graph* myGraph;
479 
484 
491 
497 
498  // ------------------------- Hidden services ------------------------------
499  protected:
500 
506 
507  private:
508 
516 
517  // ------------------------- Internals ------------------------------------
518  private:
519 
520  }; // end of class DistanceBreadthFirstVisitor
521 
522 
529  template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
530  std::ostream&
531  operator<< ( std::ostream & out,
533 
534 } // namespace DGtal
535 
536 
538 // Includes inline functions.
539 #include "DGtal/graph/DistanceBreadthFirstVisitor.ih"
540 
541 // //
543 
544 #endif // !defined DistanceBreadthFirstVisitor_h
545 
546 #undef DistanceBreadthFirstVisitor_RECURSES
547 #endif // else defined(DistanceBreadthFirstVisitor_RECURSES)
Aim: This class encapsulates its parameter class so that to indicate to the user that the object/poin...
Definition: ConstAlias.h:187
Aim: This class is useful to perform an exploration of a graph given a starting point or set (called ...
DistanceBreadthFirstVisitor & operator=(const DistanceBreadthFirstVisitor &other)
DistanceBreadthFirstVisitor(ConstAlias< Graph > graph, const VertexFunctor &distance, const Vertex &p)
DistanceBreadthFirstVisitor(const DistanceBreadthFirstVisitor &other)
void pushAgain(const Node &node)
DistanceBreadthFirstVisitor(const Graph &graph, const VertexFunctor &distance, VertexIterator b, VertexIterator e)
void getCurrentLayer(TBackInsertionSequence &layer)
void expandLayer(const VertexPredicate &authorized_vtx)
std::vector< Vertex > VertexList
Internal data structure for storing vertices.
void selfDisplay(std::ostream &out) const
std::priority_queue< Node > NodeQueue
Internal data structure for computing the distance ordering expansion.
const MarkSet & markedVertices() const
void swap(DistanceBreadthFirstVisitor &other)
DistanceBreadthFirstVisitor< TGraph, TVertexFunctor, TMarkSet > Self
void expand(const VertexPredicate &authorized_vtx)
DGtal is the top-level namespace which contains all DGtal functions and types.
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
HalfEdgeDataStructure::Size Size
TriMesh::Vertex Vertex