DGtal  1.5.beta
DepthFirstVisitor.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 DepthFirstVisitor.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  * @author David Coeurjolly (\c david.coeurjolly@liris.cnrs.fr )
22  * Laboratoire d'InfoRmatique en Image et Systèmes d'information - LIRIS (CNRS, UMR 5205), CNRS, France
23  *
24  * @date 2011/11/15
25  *
26  * Implementation of inline methods defined in DepthFirstVisitor.h
27  *
28  * This file is part of the DGtal library.
29  */
30 
31 
32 //////////////////////////////////////////////////////////////////////////////
33 #include <cstdlib>
34 //////////////////////////////////////////////////////////////////////////////
35 
36 ///////////////////////////////////////////////////////////////////////////////
37 // IMPLEMENTATION of inline methods.
38 ///////////////////////////////////////////////////////////////////////////////
39 
40 ///////////////////////////////////////////////////////////////////////////////
41 // ----------------------- Standard services ------------------------------
42 
43 //-----------------------------------------------------------------------------
44 template < typename TGraph, typename TMarkSet >
45 inline
46 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::~DepthFirstVisitor()
47 {
48 }
49 //-----------------------------------------------------------------------------
50 template < typename TGraph, typename TMarkSet >
51 inline
52 DGtal::DepthFirstVisitor<TGraph,TMarkSet>
53 ::DepthFirstVisitor( const DepthFirstVisitor & other )
54  : myGraph( other.myGraph ),
55  myMarkedVertices( other.myMarkedVertices ),
56  myQueue( other.myQueue )
57 {
58 }
59 //-----------------------------------------------------------------------------
60 template < typename TGraph, typename TMarkSet >
61 inline
62 DGtal::DepthFirstVisitor<TGraph,TMarkSet>
63 ::DepthFirstVisitor( ConstAlias<Graph> g )
64  : myGraph( g )
65 {
66 }
67 //-----------------------------------------------------------------------------
68 template < typename TGraph, typename TMarkSet >
69 inline
70 DGtal::DepthFirstVisitor<TGraph,TMarkSet>
71 ::DepthFirstVisitor( ConstAlias<Graph> g, const Vertex & p )
72  : myGraph( g )
73 {
74  myMarkedVertices.insert( p );
75  myQueue.push( std::make_pair( p, 0 ) );
76 }
77 //-----------------------------------------------------------------------------
78 template < typename TGraph, typename TMarkSet >
79 template <typename VertexIterator>
80 inline
81 DGtal::DepthFirstVisitor<TGraph,TMarkSet>
82 ::DepthFirstVisitor( ConstAlias<Graph> g,
83  VertexIterator b, VertexIterator e )
84  : myGraph( g )
85 {
86  for ( ; b != e; ++b )
87  {
88  myMarkedVertices.insert( *b );
89  myQueue.push( std::make_pair( *b, 0 ) );
90  }
91 }
92 //-----------------------------------------------------------------------------
93 template < typename TGraph, typename TMarkSet >
94 inline
95 const typename DGtal::DepthFirstVisitor<TGraph,TMarkSet>::Graph &
96 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::graph() const
97 {
98  return myGraph;
99 }
100 //-----------------------------------------------------------------------------
101 template < typename TGraph, typename TMarkSet >
102 inline
103 bool
104 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::finished() const
105 {
106  return myQueue.empty();
107 }
108 //-----------------------------------------------------------------------------
109 template < typename TGraph, typename TMarkSet >
110 inline
111 const typename DGtal::DepthFirstVisitor<TGraph,TMarkSet>::Node &
112 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::current() const
113 {
114  ASSERT( ! finished() );
115  return myQueue.top();
116 }
117 //-----------------------------------------------------------------------------
118 template < typename TGraph, typename TMarkSet >
119 inline
120 void
121 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::ignore()
122 {
123  ASSERT( ! finished() );
124  myQueue.pop();
125 }
126 //-----------------------------------------------------------------------------
127 template < typename TGraph, typename TMarkSet >
128 inline
129 void
130 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::expand()
131 {
132  ASSERT( ! finished() );
133  Node node = myQueue.top();
134  Data d = node.second + 1;
135  myQueue.pop();
136  VertexList tmp;
137  tmp.reserve( myGraph.bestCapacity() );
138  std::back_insert_iterator<VertexList> write_it = std::back_inserter( tmp );
139  myGraph.writeNeighbors( write_it, node.first );
140  for ( typename VertexList::const_iterator it = tmp.begin(),
141  it_end = tmp.end(); it != it_end; ++it )
142  {
143  typename MarkSet::const_iterator mark_it = myMarkedVertices.find( *it );
144  if ( mark_it == myMarkedVertices.end() )
145  {
146  myMarkedVertices.insert( *it );
147  myQueue.push( std::make_pair( *it, d ) );
148  }
149  }
150 }
151 //-----------------------------------------------------------------------------
152 template < typename TGraph, typename TMarkSet >
153 template <typename VertexPredicate>
154 inline
155 void
156 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::expand
157 ( const VertexPredicate & authorized_vtx )
158 {
159  ASSERT( ! finished() );
160  Node node = myQueue.top();
161  Data d = node.second + 1;
162  myQueue.pop();
163  VertexList tmp;
164  tmp.reserve( myGraph.bestCapacity() );
165  std::back_insert_iterator<VertexList> write_it = std::back_inserter( tmp );
166  myGraph.writeNeighbors( write_it,
167  node.first,
168  authorized_vtx );
169  for ( typename VertexList::const_iterator it = tmp.begin(),
170  it_end = tmp.end(); it != it_end; ++it )
171  {
172  typename MarkSet::const_iterator mark_it = myMarkedVertices.find( *it );
173  if ( mark_it == myMarkedVertices.end() )
174  {
175  myMarkedVertices.insert( *it );
176  myQueue.push( std::make_pair( *it, d ) );
177  }
178  }
179 }
180 //-----------------------------------------------------------------------------
181 template < typename TGraph, typename TMarkSet >
182 inline
183 void
184 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::terminate()
185 {
186  while ( ! finished() )
187  {
188  Node node = myQueue.top();
189  myQueue.pop();
190  typename MarkSet::iterator mark_it = myMarkedVertices.find( node.first );
191  ASSERT( mark_it != myMarkedVertices.end() );
192  myMarkedVertices.erase( mark_it );
193  }
194 }
195 //-----------------------------------------------------------------------------
196 template < typename TGraph, typename TMarkSet >
197 inline
198 const typename DGtal::DepthFirstVisitor<TGraph,TMarkSet>::MarkSet &
199 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::markedVertices() const
200 {
201  return myMarkedVertices;
202 }
203 //-----------------------------------------------------------------------------
204 template < typename TGraph, typename TMarkSet >
205 inline
206 typename DGtal::DepthFirstVisitor<TGraph,TMarkSet>::MarkSet
207 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::visitedVertices() const
208 {
209  if ( finished() ) return myMarkedVertices;
210  MarkSet visitedVtx = myMarkedVertices;
211  NodeQueue copyQ( myQueue );
212  while ( ! copyQ.empty() )
213  {
214  Node node = copyQ.top();
215  copyQ.pop();
216  typename MarkSet::iterator mark_it = visitedVtx.find( node.first );
217  ASSERT( mark_it != visitedVtx.end() );
218  visitedVtx.erase( mark_it );
219  }
220  return visitedVtx;
221 }
222 
223 ///////////////////////////////////////////////////////////////////////////////
224 // Interface - public :
225 
226 /**
227  * Writes/Displays the object on an output stream.
228  * @param out the output stream where the object is written.
229  */
230 template < typename TGraph, typename TMarkSet >
231 inline
232 void
233 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::selfDisplay ( std::ostream & out ) const
234 {
235  out << "[DepthFirstVisitor"
236  << " #queue=" << myQueue.size()
237  << " ]";
238 }
239 
240 /**
241  * Checks the validity/consistency of the object.
242  * @return 'true' if the object is valid, 'false' otherwise.
243  */
244 template < typename TGraph, typename TMarkSet >
245 inline
246 bool
247 DGtal::DepthFirstVisitor<TGraph,TMarkSet>::isValid() const
248 {
249  return true;
250 }
251 
252 
253 
254 ///////////////////////////////////////////////////////////////////////////////
255 // Implementation of inline functions //
256 
257 template < typename TGraph, typename TMarkSet >
258 inline
259 std::ostream&
260 DGtal::operator<< ( std::ostream & out,
261  const DepthFirstVisitor<TGraph,TMarkSet> & object )
262 {
263  object.selfDisplay( out );
264  return out;
265 }
266 
267 // //
268 ///////////////////////////////////////////////////////////////////////////////
269 
270