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 Node & other ) = default;
237  inline Node( const Vertex & v, Scalar d )
238  : std::pair< Vertex, Scalar >( v, d )
239  {}
240  inline bool operator<( const Node & other ) const
241  {
242  return other.second < second;
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  };
257 
259  typedef std::priority_queue< Node > NodeQueue;
261  typedef std::vector< Vertex > VertexList;
262 
263  // ----------------------- Standard services ------------------------------
264  public:
265 
270 
276 
277 
287  const VertexFunctor & distance,
288  const Vertex & p );
289 
303  template <typename VertexIterator>
305  const VertexFunctor & distance,
306  VertexIterator b, VertexIterator e );
307 
308 
312  const Graph & graph() const;
313 
314  // ----------------------- traversal services ------------------------------
315  public:
316 
324  const Node & current() const;
325 
341  template <typename TBackInsertionSequence>
342  void getCurrentLayer( TBackInsertionSequence & layer );
343 
351  void ignore();
352 
361  void ignoreLayer();
362 
368  void expand();
369 
375  void expandLayer();
376 
388  template <typename VertexPredicate>
389  void expand( const VertexPredicate & authorized_vtx );
390 
402  template <typename VertexPredicate>
403  void expandLayer( const VertexPredicate & authorized_vtx );
404 
408  bool finished() const;
409 
417  void terminate();
418 
424  const MarkSet & markedVertices() const;
425 
439 
446  void pushAgain( const Node & node );
447 
448 
455 
456  // ----------------------- Interface --------------------------------------
457  public:
458 
463  void selfDisplay ( std::ostream & out ) const;
464 
469  bool isValid() const;
470 
471  // ------------------------- Protected Datas ------------------------------
472  private:
473  // ------------------------- Private Datas --------------------------------
474  private:
475 
479  const Graph* myGraph;
480 
485 
492 
498 
499  // ------------------------- Hidden services ------------------------------
500  protected:
501 
507 
508  private:
509 
517 
518  // ------------------------- Internals ------------------------------------
519  private:
520 
521  }; // end of class DistanceBreadthFirstVisitor
522 
523 
530  template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
531  std::ostream&
532  operator<< ( std::ostream & out,
534 
535 } // namespace DGtal
536 
537 
539 // Includes inline functions.
540 #include "DGtal/graph/DistanceBreadthFirstVisitor.ih"
541 
542 // //
544 
545 #endif // !defined DistanceBreadthFirstVisitor_h
546 
547 #undef DistanceBreadthFirstVisitor_RECURSES
548 #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)
Node(const Node &other)=default
HalfEdgeDataStructure::Size Size
TriMesh::Vertex Vertex