DGtal  1.5.beta
BreadthFirstVisitor.h
1 
17 #pragma once
18 
31 #if defined(BreadthFirstVisitor_RECURSES)
32 #error Recursive header files inclusion detected in BreadthFirstVisitor.h
33 #else // defined(BreadthFirstVisitor_RECURSES)
35 #define BreadthFirstVisitor_RECURSES
36 
37 #if !defined BreadthFirstVisitor_h
39 #define BreadthFirstVisitor_h
40 
42 // Inclusions
43 #include <iostream>
44 #include <queue>
45 #include "DGtal/base/Common.h"
46 #include "DGtal/base/CountedPtr.h"
47 #include "DGtal/base/ConstAlias.h"
48 #include "DGtal/kernel/sets/DigitalSetSelector.h"
49 #include "DGtal/kernel/sets/DigitalSetDomain.h"
50 #include "DGtal/topology/DomainAdjacency.h"
51 #include "DGtal/graph/CUndirectedSimpleLocalGraph.h"
53 
54 namespace DGtal
55 {
56 
58  // template class BreadthFirstVisitor
92  template < typename TGraph,
93  typename TMarkSet = typename TGraph::VertexSet >
95  {
96  // ----------------------- Associated types ------------------------------
97  public:
99  typedef TGraph Graph;
100  typedef TMarkSet MarkSet;
101  typedef typename Graph::Size Size;
102  typedef typename Graph::Vertex Vertex;
103  typedef Size Data;
104 
105  // Cannot check this since some types using it are incomplete.
107  // BOOST_CONCEPT_ASSERT(( concepts::CUndirectedSimpleLocalGraph< Graph > ));
108  // BOOST_CONCEPT_ASSERT(( CSet< MarkSet, Vertex > ));
109 
110  // ----------------------- defined types ------------------------------
111  public:
112 
115  typedef std::pair< Vertex, Data > Node;
117  typedef std::queue< Node > NodeQueue;
119  typedef std::vector< Vertex > VertexList;
120 
121 
122  // ----------------------- Standard services ------------------------------
123  public:
124 
129 
135 
143 
152 
165  template <typename VertexIterator>
167  VertexIterator b, VertexIterator e );
168 
169 
173  const Graph & graph() const;
174 
175  // ----------------------- traversal services ------------------------------
176  public:
177 
185  const Node & current() const;
186 
194  void ignore();
195 
201  void expand();
202 
214  template <typename VertexPredicate>
215  void expand( const VertexPredicate & authorized_vtx );
216 
220  bool finished() const;
221 
229  void terminate();
230 
236  const MarkSet & markedVertices() const;
237 
251 
252 
253  // ----------------------- Interface --------------------------------------
254  public:
255 
260  void selfDisplay ( std::ostream & out ) const;
261 
266  bool isValid() const;
267 
268  // ------------------------- Protected Datas ------------------------------
269  private:
270  // ------------------------- Private Datas --------------------------------
271  private:
272 
276  const Graph & myGraph;
277 
284 
290 
291  // ------------------------- Hidden services ------------------------------
292  protected:
293 
299 
300  private:
301 
309 
310  // ------------------------- Internals ------------------------------------
311  private:
312 
313  }; // end of class BreadthFirstVisitor
314 
315 
322  template <typename TGraph, typename TMarkSet >
323  std::ostream&
324  operator<< ( std::ostream & out,
326 
327 } // namespace DGtal
328 
329 
331 // Includes inline functions.
332 #include "DGtal/graph/BreadthFirstVisitor.ih"
333 
334 // //
336 
337 #endif // !defined BreadthFirstVisitor_h
338 
339 #undef BreadthFirstVisitor_RECURSES
340 #endif // else defined(BreadthFirstVisitor_RECURSES)
Aim: This class is useful to perform a breadth-first exploration of a graph given a starting point or...
std::queue< Node > NodeQueue
Internal data structure for computing the breadth-first expansion.
BreadthFirstVisitor(ConstAlias< Graph > graph, const Vertex &p)
BreadthFirstVisitor(const BreadthFirstVisitor &other)
const MarkSet & markedVertices() const
void selfDisplay(std::ostream &out) const
Size Data
Data attached to each Vertex is the topological distance to the seed.
void expand(const VertexPredicate &authorized_vtx)
const Node & current() const
const Graph & graph() const
BreadthFirstVisitor< TGraph, TMarkSet > Self
BreadthFirstVisitor & operator=(const BreadthFirstVisitor &other)
std::vector< Vertex > VertexList
Internal data structure for storing vertices.
MarkSet visitedVertices() const
BreadthFirstVisitor(ConstAlias< Graph > graph)
std::pair< Vertex, Data > Node
FIXME.
BreadthFirstVisitor(ConstAlias< Graph > graph, VertexIterator b, VertexIterator e)
Aim: This class encapsulates its parameter class so that to indicate to the user that the object/poin...
Definition: ConstAlias.h:187
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