DGtal 1.4.2
Loading...
Searching...
No Matches
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
54namespace 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...
BreadthFirstVisitor< TGraph, TMarkSet > Self
BreadthFirstVisitor & operator=(const BreadthFirstVisitor &other)
BreadthFirstVisitor(ConstAlias< Graph > graph, const Vertex &p)
BreadthFirstVisitor(const BreadthFirstVisitor &other)
const Node & current() const
void selfDisplay(std::ostream &out) const
std::vector< Vertex > VertexList
Internal data structure for storing vertices.
void expand(const VertexPredicate &authorized_vtx)
std::pair< Vertex, Data > Node
FIXME.
const MarkSet & markedVertices() const
const Graph & graph() const
MarkSet visitedVertices() const
BreadthFirstVisitor(ConstAlias< Graph > graph)
Size Data
Data attached to each Vertex is the topological distance to the seed.
std::queue< Node > NodeQueue
Internal data structure for computing the breadth-first expansion.
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 ClosedIntegerHalfPlane< TSpace > &object)