DGtal 1.3.0
Loading...
Searching...
No Matches
DistanceBreadthFirstVisitor.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 DistanceBreadthFirstVisitor.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 2012/11/02
23 *
24 * Implementation of inline methods defined in DistanceBreadthFirstVisitor.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 TVertexFunctor, typename TMarkSet >
43inline
44DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
45~DistanceBreadthFirstVisitor()
46{
47}
48//-----------------------------------------------------------------------------
49template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
50inline
51DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
52DistanceBreadthFirstVisitor( const DistanceBreadthFirstVisitor & other )
53 : myGraph( other.myGraph ), myDistance( other.myDistance ),
54 myMarkedVertices( other.myMarkedVertices ), myQueue( other.myQueue )
55{
56}
57//-----------------------------------------------------------------------------
58template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
59inline
60DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
61DistanceBreadthFirstVisitor( ConstAlias<Graph> g,
62 const VertexFunctor & distance,
63 const Vertex & p )
64 : myGraph( &g ), myDistance( distance )
65{
66 myMarkedVertices.insert( p );
67 myQueue.push( Node( p, myDistance( p ) ) );
68}
69//-----------------------------------------------------------------------------
70template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
71template <typename VertexIterator>
72inline
73DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
74DistanceBreadthFirstVisitor( const Graph & g,
75 const VertexFunctor & distance,
76 VertexIterator b, VertexIterator e )
77 : myGraph( &g ), myDistance( distance )
78{
79 for ( ; b != e; ++b )
80 {
81 myMarkedVertices.insert( *b );
82 myQueue.push( Node( *b, myDistance( *b ) ) );
83 }
84}
85//-----------------------------------------------------------------------------
86template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
87inline
88const typename DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::Graph &
89DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
90graph() const
91{
92 return *myGraph;
93}
94//-----------------------------------------------------------------------------
95template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
96inline
97bool
98DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
99finished() const
100{
101 return myQueue.empty();
102}
103//-----------------------------------------------------------------------------
104template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
105inline
106const typename DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::Node &
107DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
108current() const
109{
110 ASSERT( ! finished() );
111 return myQueue.top();
112}
113//-----------------------------------------------------------------------------
114template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
115template < typename TBackInsertionSequence >
116inline
117void
118DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
119getCurrentLayer( TBackInsertionSequence & layer )
120{
121 BOOST_CONCEPT_ASSERT(( boost::BackInsertionSequence< TBackInsertionSequence > ));
122 ASSERT( ! finished() );
123 layer.clear();
124 Node node = current();
125 do
126 {
127 layer.push_back( current() );
128 myQueue.pop();
129 }
130 while ( ( ! finished() ) && ( node.second == current().second ) );
131 for ( typename TBackInsertionSequence::const_iterator it = layer.begin(),
132 itE = layer.end();
133 it != itE; ++it )
134 {
135 myQueue.push( *it );
136 }
137}
138//-----------------------------------------------------------------------------
139template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
140inline
141void
142DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
143ignore()
144{
145 ASSERT( ! finished() );
146 myQueue.pop();
147}
148//-----------------------------------------------------------------------------
149template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
150inline
151void
152DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
153pushAgain( const Node & node )
154{
155 ASSERT( myMarkedVertices.find( node.first ) != myMarkedVertices.end() );
156 myQueue.push( node );
157}
158//-----------------------------------------------------------------------------
159template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
160inline
161void
162DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
163ignoreLayer()
164{
165 ASSERT( ! finished() );
166 Node node = current();
167 do
168 {
169 ignore();
170 }
171 while ( ! finished() && ( node.second == current().second ) );
172}
173//-----------------------------------------------------------------------------
174template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
175inline
176void
177DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
178expand()
179{
180 ASSERT( ! finished() );
181 Node node = myQueue.top();
182 myQueue.pop();
183 Vertex vtx;
184 VertexList tmp;
185 tmp.reserve( myGraph->bestCapacity() );
186 std::back_insert_iterator<VertexList> write_it = std::back_inserter( tmp );
187 myGraph->writeNeighbors( write_it, node.first );
188 for ( typename VertexList::const_iterator it = tmp.begin(),
189 it_end = tmp.end(); it != it_end; ++it )
190 {
191 vtx = *it;
192 typename MarkSet::const_iterator mark_it = myMarkedVertices.find( vtx );
193 if ( mark_it == myMarkedVertices.end() )
194 {
195 myMarkedVertices.insert( vtx );
196 myQueue.push( Node( vtx, myDistance( vtx ) ) );
197 }
198 }
199}
200//-----------------------------------------------------------------------------
201template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
202inline
203void
204DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
205expandLayer()
206{
207 ASSERT( ! finished() );
208 Node node = current();
209 do
210 {
211 expand();
212 }
213 while ( ! finished() && ( node.second == current().second ) );
214}
215//-----------------------------------------------------------------------------
216template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
217template <typename VertexPredicate>
218inline
219void
220DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
221expand( const VertexPredicate & authorized_vtx )
222{
223 ASSERT( ! finished() );
224 Node node = myQueue.top();
225 myQueue.pop();
226 Vertex vtx;
227 VertexList tmp;
228 tmp.reserve( myGraph->bestCapacity() );
229 std::back_insert_iterator<VertexList> write_it = std::back_inserter( tmp );
230 myGraph->writeNeighbors( write_it, node.first, authorized_vtx );
231 for ( typename VertexList::const_iterator it = tmp.begin(),
232 it_end = tmp.end(); it != it_end; ++it )
233 {
234 vtx = *it;
235 typename MarkSet::const_iterator mark_it = myMarkedVertices.find( vtx );
236 if ( mark_it == myMarkedVertices.end() )
237 {
238 myMarkedVertices.insert( vtx );
239 myQueue.push( Node( vtx, myDistance( vtx ) ) );
240 }
241 }
242}
243//-----------------------------------------------------------------------------
244template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
245template <typename VertexPredicate>
246inline
247void
248DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
249expandLayer( const VertexPredicate & authorized_vtx )
250{
251 ASSERT( ! finished() );
252 Node node = current();
253 do
254 {
255 expand( authorized_vtx );
256 }
257 while ( ! finished() && ( node.second == current().second ) );
258}
259//-----------------------------------------------------------------------------
260template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
261inline
262void
263DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
264terminate()
265{
266 while ( ! finished() )
267 {
268 Node node = myQueue.top();
269 myQueue.pop();
270 typename MarkSet::iterator mark_it = myMarkedVertices.find( node.first );
271 ASSERT( mark_it != myMarkedVertices.end() );
272 myMarkedVertices.erase( mark_it );
273 }
274}
275//-----------------------------------------------------------------------------
276template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
277inline
278const typename DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::MarkSet &
279DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
280markedVertices() const
281{
282 return myMarkedVertices;
283}
284//-----------------------------------------------------------------------------
285template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
286inline
287typename DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::MarkSet
288DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
289visitedVertices() const
290{
291 if ( finished() ) return myMarkedVertices;
292 MarkSet visitedVtx = myMarkedVertices;
293 NodeQueue q = myQueue; // duplicate queue
294 while ( ! q.empty() )
295 {
296 visitedVtx.erase( q.top().first );
297 q.pop();
298 }
299 return visitedVtx;
300}
301//-----------------------------------------------------------------------------
302template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
303inline
304void
305DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
306swap( DistanceBreadthFirstVisitor & other )
307{
308 std::swap( myGraph, other.myGraph );
309 std::swap( myDistance, other.myDistance );
310 myMarkedVertices.swap( other.myMarkedVertices );
311 myQueue.swap( other.myQueue );
312}
313///////////////////////////////////////////////////////////////////////////////
314// Interface - public :
315
316/**
317 * Writes/Displays the object on an output stream.
318 * @param out the output stream where the object is written.
319 */
320template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
321inline
322void
323DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
324selfDisplay ( std::ostream & out ) const
325{
326 out << "[DistanceBreadthFirstVisitor"
327 << " #queue=" << myQueue.size()
328 << " ]";
329}
330
331/**
332 * Checks the validity/consistency of the object.
333 * @return 'true' if the object is valid, 'false' otherwise.
334 */
335template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
336inline
337bool
338DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
339isValid() const
340{
341 return true;
342}
343
344
345
346///////////////////////////////////////////////////////////////////////////////
347// Implementation of inline functions //
348
349template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
350inline
351std::ostream&
352DGtal::operator<< ( std::ostream & out,
353 const DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet> & object )
354{
355 object.selfDisplay( out );
356 return out;
357}
358
359// //
360///////////////////////////////////////////////////////////////////////////////
361
362
Generated on Sun Nov 27 2022 15:15:43 for DGtal by doxygen 1.9.5