DGtal 1.3.0
Loading...
Searching...
No Matches
BreadthFirstVisitor.ih
1/**
2 * This program is free software: you can redistribute it and/or modify
3 * it under the terms of the GNU Lesser General Public License as
4 * published by the Free Software Foundation, either version 3 of the
5 * License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program. If not, see <http://www.gnu.org/licenses/>.
14 *
15 **/
16
17/**
18 * @file BreadthFirstVisitor.ih
19 * @author Jacques-Olivier Lachaud (\c jacques-olivier.lachaud@univ-savoie.fr )
20 * Laboratory of Mathematics (CNRS, UMR 5807), University of Savoie, France
21 *
22 * @date 2011/11/15
23 *
24 * Implementation of inline methods defined in BreadthFirstVisitor.h
25 *
26 * This file is part of the DGtal library.
27 */
28
29
30//////////////////////////////////////////////////////////////////////////////
31#include <cstdlib>
32//////////////////////////////////////////////////////////////////////////////
33
34///////////////////////////////////////////////////////////////////////////////
35// IMPLEMENTATION of inline methods.
36///////////////////////////////////////////////////////////////////////////////
37
38///////////////////////////////////////////////////////////////////////////////
39// ----------------------- Standard services ------------------------------
40
41//-----------------------------------------------------------------------------
42template < typename TGraph, typename TMarkSet >
43inline
44DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::~BreadthFirstVisitor()
45{
46}
47//-----------------------------------------------------------------------------
48template < typename TGraph, typename TMarkSet >
49inline
50DGtal::BreadthFirstVisitor<TGraph,TMarkSet>
51::BreadthFirstVisitor( const BreadthFirstVisitor & other )
52 : myGraph( other.myGraph ),
53 myMarkedVertices( other.myMarkedVertices ),
54 myQueue( other.myQueue )
55{
56}
57//-----------------------------------------------------------------------------
58template < typename TGraph, typename TMarkSet >
59inline
60DGtal::BreadthFirstVisitor<TGraph,TMarkSet>
61::BreadthFirstVisitor( ConstAlias<Graph> g )
62 : myGraph( g )
63{
64}
65//-----------------------------------------------------------------------------
66template < typename TGraph, typename TMarkSet >
67inline
68DGtal::BreadthFirstVisitor<TGraph,TMarkSet>
69::BreadthFirstVisitor( ConstAlias<Graph> g, const Vertex & p )
70 : myGraph( g )
71{
72 myMarkedVertices.insert( p );
73 myQueue.push( std::make_pair( p, 0 ) );
74}
75//-----------------------------------------------------------------------------
76template < typename TGraph, typename TMarkSet >
77template <typename VertexIterator>
78inline
79DGtal::BreadthFirstVisitor<TGraph,TMarkSet>
80::BreadthFirstVisitor( ConstAlias<Graph> g,
81 VertexIterator b, VertexIterator e )
82 : myGraph( g )
83{
84 for ( ; b != e; ++b )
85 {
86 myMarkedVertices.insert( *b );
87 myQueue.push( std::make_pair( *b, 0 ) );
88 }
89}
90//-----------------------------------------------------------------------------
91template < typename TGraph, typename TMarkSet >
92inline
93const typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::Graph &
94DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::graph() const
95{
96 return myGraph;
97}
98//-----------------------------------------------------------------------------
99template < typename TGraph, typename TMarkSet >
100inline
101bool
102DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::finished() const
103{
104 return myQueue.empty();
105}
106//-----------------------------------------------------------------------------
107template < typename TGraph, typename TMarkSet >
108inline
109const typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::Node &
110DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::current() const
111{
112 ASSERT( ! finished() );
113 return myQueue.front();
114}
115//-----------------------------------------------------------------------------
116template < typename TGraph, typename TMarkSet >
117inline
118void
119DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::ignore()
120{
121 ASSERT( ! finished() );
122 myQueue.pop();
123}
124//-----------------------------------------------------------------------------
125template < typename TGraph, typename TMarkSet >
126inline
127void
128DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::expand()
129{
130 ASSERT( ! finished() );
131 Node node = myQueue.front();
132 Data d = node.second + 1;
133 myQueue.pop();
134 VertexList tmp;
135 tmp.reserve( myGraph.bestCapacity() );
136 std::back_insert_iterator<VertexList> write_it = std::back_inserter( tmp );
137 myGraph.writeNeighbors( write_it, node.first );
138 for ( typename VertexList::const_iterator it = tmp.begin(),
139 it_end = tmp.end(); it != it_end; ++it )
140 {
141 typename MarkSet::const_iterator mark_it = myMarkedVertices.find( *it );
142 if ( mark_it == myMarkedVertices.end() )
143 {
144 myMarkedVertices.insert( *it );
145 myQueue.push( std::make_pair( *it, d ) );
146 }
147 }
148}
149//-----------------------------------------------------------------------------
150template < typename TGraph, typename TMarkSet >
151template <typename VertexPredicate>
152inline
153void
154DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::expand
155( const VertexPredicate & authorized_vtx )
156{
157 ASSERT( ! finished() );
158 Node node = myQueue.front();
159 Data d = node.second + 1;
160 myQueue.pop();
161 VertexList tmp;
162 tmp.reserve( myGraph.bestCapacity() );
163 std::back_insert_iterator<VertexList> write_it = std::back_inserter( tmp );
164 myGraph.writeNeighbors( write_it,
165 node.first,
166 authorized_vtx );
167 for ( typename VertexList::const_iterator it = tmp.begin(),
168 it_end = tmp.end(); it != it_end; ++it )
169 {
170 typename MarkSet::const_iterator mark_it = myMarkedVertices.find( *it );
171 if ( mark_it == myMarkedVertices.end() )
172 {
173 myMarkedVertices.insert( *it );
174 myQueue.push( std::make_pair( *it, d ) );
175 }
176 }
177}
178//-----------------------------------------------------------------------------
179template < typename TGraph, typename TMarkSet >
180inline
181void
182DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::terminate()
183{
184 while ( ! finished() )
185 {
186 Node node = myQueue.front();
187 myQueue.pop();
188 typename MarkSet::iterator mark_it = myMarkedVertices.find( node.first );
189 ASSERT( mark_it != myMarkedVertices.end() );
190 myMarkedVertices.erase( mark_it );
191 }
192}
193//-----------------------------------------------------------------------------
194template < typename TGraph, typename TMarkSet >
195inline
196const typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::MarkSet &
197DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::markedVertices() const
198{
199 return myMarkedVertices;
200}
201//-----------------------------------------------------------------------------
202template < typename TGraph, typename TMarkSet >
203inline
204typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::MarkSet
205DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::visitedVertices() const
206{
207 if ( finished() ) return myMarkedVertices;
208 MarkSet visitedVtx = myMarkedVertices;
209 NodeQueue copyQ( myQueue );
210 while ( ! copyQ.empty() )
211 {
212 Node node = copyQ.front();
213 copyQ.pop();
214 typename MarkSet::iterator mark_it = visitedVtx.find( node.first );
215 ASSERT( mark_it != visitedVtx.end() );
216 visitedVtx.erase( mark_it );
217 }
218 return visitedVtx;
219 // JOL: 2012/11/21: Cannot do this since method is const.
220 //
221 // Roll completely the queue so as to remove these vertices from the
222 // set of visited vertices.
223 // Node start = myQueue.front();
224 // do {
225 // Node node = myQueue.front();
226 // myQueue.pop();
227 // typename MarkSet::iterator mark_it = visitedVtx.find( node.first );
228 // ASSERT( mark_it != visitedVtx.end() );
229 // visitedVtx.erase( mark_it );
230 // myQueue.push( node );
231 // } while ( myQueue.front().first != start.first );
232 // return visitedVtx;
233}
234
235///////////////////////////////////////////////////////////////////////////////
236// Interface - public :
237
238/**
239 * Writes/Displays the object on an output stream.
240 * @param out the output stream where the object is written.
241 */
242template < typename TGraph, typename TMarkSet >
243inline
244void
245DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::selfDisplay ( std::ostream & out ) const
246{
247 out << "[BreadthFirstVisitor"
248 << " #queue=" << myQueue.size()
249 << " ]";
250}
251
252/**
253 * Checks the validity/consistency of the object.
254 * @return 'true' if the object is valid, 'false' otherwise.
255 */
256template < typename TGraph, typename TMarkSet >
257inline
258bool
259DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::isValid() const
260{
261 return true;
262}
263
264
265
266///////////////////////////////////////////////////////////////////////////////
267// Implementation of inline functions //
268
269template < typename TGraph, typename TMarkSet >
270inline
271std::ostream&
272DGtal::operator<< ( std::ostream & out,
273 const BreadthFirstVisitor<TGraph,TMarkSet> & object )
274{
275 object.selfDisplay( out );
276 return out;
277}
278
279// //
280///////////////////////////////////////////////////////////////////////////////
281
282
Generated on Sun Nov 27 2022 15:15:43 for DGtal by doxygen 1.9.5