DGtal  0.9.2
DepthFirstVisitor.h
1 
17 #pragma once
18 
33 #if defined(DepthFirstVisitor_RECURSES)
34 #error Recursive header files inclusion detected in DepthFirstVisitor.h
35 #else // defined(DepthFirstVisitor_RECURSES)
36 
37 #define DepthFirstVisitor_RECURSES
38 
39 #if !defined DepthFirstVisitor_h
40 
41 #define DepthFirstVisitor_h
42 
44 // Inclusions
45 #include <iostream>
46 #include <stack>
47 #include "DGtal/base/Common.h"
48 #include "DGtal/base/CountedPtr.h"
49 #include "DGtal/base/ConstAlias.h"
50 #include "DGtal/kernel/sets/DigitalSetSelector.h"
51 #include "DGtal/kernel/sets/DigitalSetDomain.h"
52 #include "DGtal/topology/DomainAdjacency.h"
53 #include "DGtal/graph/CUndirectedSimpleLocalGraph.h"
55 
56 namespace DGtal
57 {
58 
60  // template class DepthFirstVisitor
93  template < typename TGraph,
94  typename TMarkSet = typename TGraph::VertexSet >
96  {
97  // ----------------------- Associated types ------------------------------
98  public:
100  typedef TGraph Graph;
101  typedef TMarkSet MarkSet;
102  typedef typename Graph::Size Size;
103  typedef typename Graph::Vertex Vertex;
104  typedef Size Data;
105 
106  //BOOST_CONCEPT_ASSERT(( CUndirectedSimpleLocalGraph< Graph > ));
107  // Cannot check this since some types using it are incomplete.
108  //BOOST_CONCEPT_ASSERT(( CSet< MarkSet, Vertex > ));
109 
110  // ----------------------- defined types ------------------------------
111  public:
112 
115  typedef std::pair< Vertex, Data > Node;
117  typedef std::stack< Node > NodeQueue;
119  typedef std::vector< Vertex > VertexList;
120 
121 
122  // ----------------------- Standard services ------------------------------
123  public:
124 
129 
134  DepthFirstVisitor ( const DepthFirstVisitor & other );
135 
143 
151  DepthFirstVisitor( ConstAlias<Graph> graph, const Vertex & p );
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 
250  MarkSet visitedVertices() const;
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 
289  NodeQueue myQueue;
290 
291  // ------------------------- Hidden services ------------------------------
292  protected:
293 
299 
300  private:
301 
309 
310  // ------------------------- Internals ------------------------------------
311  private:
312 
313  }; // end of class DepthFirstVisitor
314 
315 
322  template <typename TGraph, typename TMarkSet >
323  std::ostream&
324  operator<< ( std::ostream & out,
325  const DepthFirstVisitor<TGraph, TMarkSet > & object );
326 
327 } // namespace DGtal
328 
329 
331 // Includes inline functions.
332 #include "DGtal/graph/DepthFirstVisitor.ih"
333 
334 // //
336 
337 #endif // !defined DepthFirstVisitor_h
338 
339 #undef DepthFirstVisitor_RECURSES
340 #endif // else defined(DepthFirstVisitor_RECURSES)
std::pair< Vertex, Data > Node
Aim: This class encapsulates its parameter class so that to indicate to the user that the object/poin...
Definition: ConstAlias.h:186
Aim: This class is useful to perform a depth-first exploration of a graph given a starting point or s...
DepthFirstVisitor & operator=(const DepthFirstVisitor &other)
void selfDisplay(std::ostream &out) const
MarkSet visitedVertices() const
std::ostream & operator<<(std::ostream &out, const ClosedIntegerHalfPlane< TSpace > &object)
DGtal is the top-level namespace which contains all DGtal functions and types.
const Graph & graph() const
std::stack< Node > NodeQueue
Internal data structure for computing the depth-first expansion.
const MarkSet & markedVertices() const
Size Data
Data attached to each Vertex is the depth distance to the seed.
DepthFirstVisitor< TGraph, TMarkSet > Self
std::vector< Vertex > VertexList
Internal data structure for storing vertices.
const Node & current() const