DGtal  1.3.beta
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 
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 
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)
DGtal::DepthFirstVisitor::MarkSet
TMarkSet MarkSet
Definition: DepthFirstVisitor.h:101
DGtal::DepthFirstVisitor::selfDisplay
void selfDisplay(std::ostream &out) const
DGtal::ConstAlias
Aim: This class encapsulates its parameter class so that to indicate to the user that the object/poin...
Definition: ConstAlias.h:186
DGtal::DepthFirstVisitor::Data
Size Data
Data attached to each Vertex is the depth distance to the seed.
Definition: DepthFirstVisitor.h:104
DGtal::DepthFirstVisitor::Self
DepthFirstVisitor< TGraph, TMarkSet > Self
Definition: DepthFirstVisitor.h:99
DGtal::DepthFirstVisitor::myMarkedVertices
MarkSet myMarkedVertices
Definition: DepthFirstVisitor.h:283
DGtal::DepthFirstVisitor::DepthFirstVisitor
DepthFirstVisitor()
DGtal::DepthFirstVisitor::VertexList
std::vector< Vertex > VertexList
Internal data structure for storing vertices.
Definition: DepthFirstVisitor.h:119
DGtal::DepthFirstVisitor::expand
void expand()
DGtal::DepthFirstVisitor::Node
std::pair< Vertex, Data > Node
Definition: DepthFirstVisitor.h:115
DGtal::DepthFirstVisitor::markedVertices
const MarkSet & markedVertices() const
DGtal::DepthFirstVisitor::graph
const Graph & graph() const
Vertex
TriMesh::Vertex Vertex
Definition: testTriangulatedSurface.cpp:57
Size
HalfEdgeDataStructure::Size Size
Definition: testHalfEdgeDataStructure.cpp:50
DGtal::operator<<
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
DGtal::DepthFirstVisitor::operator=
DepthFirstVisitor & operator=(const DepthFirstVisitor &other)
DGtal::DepthFirstVisitor::Size
Graph::Size Size
Definition: DepthFirstVisitor.h:102
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::DepthFirstVisitor::isValid
bool isValid() const
DGtal::DepthFirstVisitor::NodeQueue
std::stack< Node > NodeQueue
Internal data structure for computing the depth-first expansion.
Definition: DepthFirstVisitor.h:117
DGtal::DepthFirstVisitor::visitedVertices
MarkSet visitedVertices() const
DGtal::DepthFirstVisitor::myGraph
const Graph & myGraph
Definition: DepthFirstVisitor.h:276
DGtal::DepthFirstVisitor::Graph
TGraph Graph
Definition: DepthFirstVisitor.h:100
DGtal::DepthFirstVisitor::terminate
void terminate()
DGtal::DepthFirstVisitor
Aim: This class is useful to perform a depth-first exploration of a graph given a starting point or s...
Definition: DepthFirstVisitor.h:95
DGtal::DepthFirstVisitor::finished
bool finished() const
DGtal::DepthFirstVisitor::~DepthFirstVisitor
~DepthFirstVisitor()
DGtal::DepthFirstVisitor::myQueue
NodeQueue myQueue
Definition: DepthFirstVisitor.h:289
DGtal::DepthFirstVisitor::Vertex
Graph::Vertex Vertex
Definition: DepthFirstVisitor.h:103
DGtal::DepthFirstVisitor::current
const Node & current() const
DGtal::DepthFirstVisitor::ignore
void ignore()