DGtal  1.5.beta
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 //-----------------------------------------------------------------------------
42 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
43 inline
44 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
45 ~DistanceBreadthFirstVisitor()
46 {
47 }
48 //-----------------------------------------------------------------------------
49 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
50 inline
51 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
52 DistanceBreadthFirstVisitor( const DistanceBreadthFirstVisitor & other )
53  : myGraph( other.myGraph ), myDistance( other.myDistance ),
54  myMarkedVertices( other.myMarkedVertices ), myQueue( other.myQueue )
55 {
56 }
57 //-----------------------------------------------------------------------------
58 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
59 inline
60 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
61 DistanceBreadthFirstVisitor( 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 //-----------------------------------------------------------------------------
70 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
71 template <typename VertexIterator>
72 inline
73 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
74 DistanceBreadthFirstVisitor( 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 //-----------------------------------------------------------------------------
86 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
87 inline
88 const typename DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::Graph &
89 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
90 graph() const
91 {
92  return *myGraph;
93 }
94 //-----------------------------------------------------------------------------
95 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
96 inline
97 bool
98 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
99 finished() const
100 {
101  return myQueue.empty();
102 }
103 //-----------------------------------------------------------------------------
104 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
105 inline
106 const typename DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::Node &
107 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
108 current() const
109 {
110  ASSERT( ! finished() );
111  return myQueue.top();
112 }
113 //-----------------------------------------------------------------------------
114 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
115 template < typename TBackInsertionSequence >
116 inline
117 void
118 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
119 getCurrentLayer( 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 //-----------------------------------------------------------------------------
139 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
140 inline
141 void
142 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
143 ignore()
144 {
145  ASSERT( ! finished() );
146  myQueue.pop();
147 }
148 //-----------------------------------------------------------------------------
149 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
150 inline
151 void
152 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
153 pushAgain( const Node & node )
154 {
155  ASSERT( myMarkedVertices.find( node.first ) != myMarkedVertices.end() );
156  myQueue.push( node );
157 }
158 //-----------------------------------------------------------------------------
159 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
160 inline
161 void
162 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
163 ignoreLayer()
164 {
165  ASSERT( ! finished() );
166  Node node = current();
167  do
168  {
169  ignore();
170  }
171  while ( ! finished() && ( node.second == current().second ) );
172 }
173 //-----------------------------------------------------------------------------
174 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
175 inline
176 void
177 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
178 expand()
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 //-----------------------------------------------------------------------------
201 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
202 inline
203 void
204 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
205 expandLayer()
206 {
207  ASSERT( ! finished() );
208  Node node = current();
209  do
210  {
211  expand();
212  }
213  while ( ! finished() && ( node.second == current().second ) );
214 }
215 //-----------------------------------------------------------------------------
216 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
217 template <typename VertexPredicate>
218 inline
219 void
220 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
221 expand( 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 //-----------------------------------------------------------------------------
244 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
245 template <typename VertexPredicate>
246 inline
247 void
248 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
249 expandLayer( 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 //-----------------------------------------------------------------------------
260 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
261 inline
262 void
263 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
264 terminate()
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 //-----------------------------------------------------------------------------
276 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
277 inline
278 const typename DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::MarkSet &
279 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
280 markedVertices() const
281 {
282  return myMarkedVertices;
283 }
284 //-----------------------------------------------------------------------------
285 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
286 inline
287 typename DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::MarkSet
288 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
289 visitedVertices() 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 //-----------------------------------------------------------------------------
302 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
303 inline
304 void
305 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
306 swap( 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  */
320 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
321 inline
322 void
323 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
324 selfDisplay ( 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  */
335 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
336 inline
337 bool
338 DGtal::DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet>::
339 isValid() const
340 {
341  return true;
342 }
343 
344 
345 
346 ///////////////////////////////////////////////////////////////////////////////
347 // Implementation of inline functions //
348 
349 template < typename TGraph, typename TVertexFunctor, typename TMarkSet >
350 inline
351 std::ostream&
352 DGtal::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