DGtal 1.3.0
Loading...
Searching...
No Matches
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//-----------------------------------------------------------------------------
44template < typename TGraph, typename TMarkSet >
45inline
46DGtal::DepthFirstVisitor<TGraph,TMarkSet>::~DepthFirstVisitor()
47{
48}
49//-----------------------------------------------------------------------------
50template < typename TGraph, typename TMarkSet >
51inline
52DGtal::DepthFirstVisitor<TGraph,TMarkSet>
53::DepthFirstVisitor( const DepthFirstVisitor & other )
54 : myGraph( other.myGraph ),
55 myMarkedVertices( other.myMarkedVertices ),
56 myQueue( other.myQueue )
57{
58}
59//-----------------------------------------------------------------------------
60template < typename TGraph, typename TMarkSet >
61inline
62DGtal::DepthFirstVisitor<TGraph,TMarkSet>
63::DepthFirstVisitor( ConstAlias<Graph> g )
64 : myGraph( g )
65{
66}
67//-----------------------------------------------------------------------------
68template < typename TGraph, typename TMarkSet >
69inline
70DGtal::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//-----------------------------------------------------------------------------
78template < typename TGraph, typename TMarkSet >
79template <typename VertexIterator>
80inline
81DGtal::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//-----------------------------------------------------------------------------
93template < typename TGraph, typename TMarkSet >
94inline
95const typename DGtal::DepthFirstVisitor<TGraph,TMarkSet>::Graph &
96DGtal::DepthFirstVisitor<TGraph,TMarkSet>::graph() const
97{
98 return myGraph;
99}
100//-----------------------------------------------------------------------------
101template < typename TGraph, typename TMarkSet >
102inline
103bool
104DGtal::DepthFirstVisitor<TGraph,TMarkSet>::finished() const
105{
106 return myQueue.empty();
107}
108//-----------------------------------------------------------------------------
109template < typename TGraph, typename TMarkSet >
110inline
111const typename DGtal::DepthFirstVisitor<TGraph,TMarkSet>::Node &
112DGtal::DepthFirstVisitor<TGraph,TMarkSet>::current() const
113{
114 ASSERT( ! finished() );
115 return myQueue.top();
116}
117//-----------------------------------------------------------------------------
118template < typename TGraph, typename TMarkSet >
119inline
120void
121DGtal::DepthFirstVisitor<TGraph,TMarkSet>::ignore()
122{
123 ASSERT( ! finished() );
124 myQueue.pop();
125}
126//-----------------------------------------------------------------------------
127template < typename TGraph, typename TMarkSet >
128inline
129void
130DGtal::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//-----------------------------------------------------------------------------
152template < typename TGraph, typename TMarkSet >
153template <typename VertexPredicate>
154inline
155void
156DGtal::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//-----------------------------------------------------------------------------
181template < typename TGraph, typename TMarkSet >
182inline
183void
184DGtal::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//-----------------------------------------------------------------------------
196template < typename TGraph, typename TMarkSet >
197inline
198const typename DGtal::DepthFirstVisitor<TGraph,TMarkSet>::MarkSet &
199DGtal::DepthFirstVisitor<TGraph,TMarkSet>::markedVertices() const
200{
201 return myMarkedVertices;
202}
203//-----------------------------------------------------------------------------
204template < typename TGraph, typename TMarkSet >
205inline
206typename DGtal::DepthFirstVisitor<TGraph,TMarkSet>::MarkSet
207DGtal::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 */
230template < typename TGraph, typename TMarkSet >
231inline
232void
233DGtal::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 */
244template < typename TGraph, typename TMarkSet >
245inline
246bool
247DGtal::DepthFirstVisitor<TGraph,TMarkSet>::isValid() const
248{
249 return true;
250}
251
252
253
254///////////////////////////////////////////////////////////////////////////////
255// Implementation of inline functions //
256
257template < typename TGraph, typename TMarkSet >
258inline
259std::ostream&
260DGtal::operator<< ( std::ostream & out,
261 const DepthFirstVisitor<TGraph,TMarkSet> & object )
262{
263 object.selfDisplay( out );
264 return out;
265}
266
267// //
268///////////////////////////////////////////////////////////////////////////////
269
270
Generated on Sun Nov 27 2022 15:15:43 for DGtal by doxygen 1.9.5