DGtal  0.9.2
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 //-----------------------------------------------------------------------------
42 template < typename TGraph, typename TMarkSet >
43 inline
44 DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::~BreadthFirstVisitor()
45 {
46 }
47 //-----------------------------------------------------------------------------
48 template < typename TGraph, typename TMarkSet >
49 inline
50 DGtal::BreadthFirstVisitor<TGraph,TMarkSet>
51 ::BreadthFirstVisitor( const BreadthFirstVisitor & other )
52  : myGraph( other.myGraph ),
53  myMarkedVertices( other.myMarkedVertices ),
54  myQueue( other.myQueue )
55 {
56 }
57 //-----------------------------------------------------------------------------
58 template < typename TGraph, typename TMarkSet >
59 inline
60 DGtal::BreadthFirstVisitor<TGraph,TMarkSet>
61 ::BreadthFirstVisitor( ConstAlias<Graph> g )
62  : myGraph( g )
63 {
64 }
65 //-----------------------------------------------------------------------------
66 template < typename TGraph, typename TMarkSet >
67 inline
68 DGtal::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 //-----------------------------------------------------------------------------
76 template < typename TGraph, typename TMarkSet >
77 template <typename VertexIterator>
78 inline
79 DGtal::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 //-----------------------------------------------------------------------------
91 template < typename TGraph, typename TMarkSet >
92 inline
93 const typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::Graph &
94 DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::graph() const
95 {
96  return myGraph;
97 }
98 //-----------------------------------------------------------------------------
99 template < typename TGraph, typename TMarkSet >
100 inline
101 bool
102 DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::finished() const
103 {
104  return myQueue.empty();
105 }
106 //-----------------------------------------------------------------------------
107 template < typename TGraph, typename TMarkSet >
108 inline
109 const typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::Node &
110 DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::current() const
111 {
112  ASSERT( ! finished() );
113  return myQueue.front();
114 }
115 //-----------------------------------------------------------------------------
116 template < typename TGraph, typename TMarkSet >
117 inline
118 void
119 DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::ignore()
120 {
121  ASSERT( ! finished() );
122  myQueue.pop();
123 }
124 //-----------------------------------------------------------------------------
125 template < typename TGraph, typename TMarkSet >
126 inline
127 void
128 DGtal::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 //-----------------------------------------------------------------------------
150 template < typename TGraph, typename TMarkSet >
151 template <typename VertexPredicate>
152 inline
153 void
154 DGtal::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 //-----------------------------------------------------------------------------
179 template < typename TGraph, typename TMarkSet >
180 inline
181 void
182 DGtal::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 //-----------------------------------------------------------------------------
194 template < typename TGraph, typename TMarkSet >
195 inline
196 const typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::MarkSet &
197 DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::markedVertices() const
198 {
199  return myMarkedVertices;
200 }
201 //-----------------------------------------------------------------------------
202 template < typename TGraph, typename TMarkSet >
203 inline
204 typename DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::MarkSet
205 DGtal::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  */
242 template < typename TGraph, typename TMarkSet >
243 inline
244 void
245 DGtal::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  */
256 template < typename TGraph, typename TMarkSet >
257 inline
258 bool
259 DGtal::BreadthFirstVisitor<TGraph,TMarkSet>::isValid() const
260 {
261  return true;
262 }
263 
264 
265 
266 ///////////////////////////////////////////////////////////////////////////////
267 // Implementation of inline functions //
268 
269 template < typename TGraph, typename TMarkSet >
270 inline
271 std::ostream&
272 DGtal::operator<< ( std::ostream & out,
273  const BreadthFirstVisitor<TGraph,TMarkSet> & object )
274 {
275  object.selfDisplay( out );
276  return out;
277 }
278 
279 // //
280 ///////////////////////////////////////////////////////////////////////////////
281 
282