]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright Louis Dionne 2013 |
2 | ||
3 | // Use, modification and distribution is subject to the Boost Software | |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy | |
5 | // at http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | #ifndef BOOST_GRAPH_HAWICK_CIRCUITS_HPP | |
8 | #define BOOST_GRAPH_HAWICK_CIRCUITS_HPP | |
9 | ||
10 | #include <algorithm> | |
11 | #include <boost/assert.hpp> | |
12 | #include <boost/foreach.hpp> | |
13 | #include <boost/graph/graph_traits.hpp> | |
14 | #include <boost/graph/one_bit_color_map.hpp> | |
15 | #include <boost/graph/properties.hpp> | |
16 | #include <boost/move/utility.hpp> | |
17 | #include <boost/property_map/property_map.hpp> | |
18 | #include <boost/range/begin.hpp> | |
19 | #include <boost/range/end.hpp> | |
20 | #include <boost/range/iterator.hpp> | |
21 | #include <boost/tuple/tuple.hpp> // for boost::tie | |
22 | #include <boost/type_traits/remove_reference.hpp> | |
23 | #include <boost/utility/result_of.hpp> | |
24 | #include <set> | |
25 | #include <utility> // for std::pair | |
26 | #include <vector> | |
27 | ||
f67539c2 TL |
28 | namespace boost |
29 | { | |
30 | namespace hawick_circuits_detail | |
31 | { | |
32 | //! @internal Functor returning all the vertices adjacent to a vertex. | |
33 | struct get_all_adjacent_vertices | |
34 | { | |
35 | template < typename Sig > struct result; | |
36 | ||
37 | template < typename This, typename Vertex, typename Graph > | |
38 | struct result< This(Vertex, Graph) > | |
39 | { | |
40 | private: | |
41 | typedef typename remove_reference< Graph >::type RawGraph; | |
42 | typedef graph_traits< RawGraph > Traits; | |
43 | typedef typename Traits::adjacency_iterator AdjacencyIterator; | |
44 | ||
45 | public: | |
46 | typedef std::pair< AdjacencyIterator, AdjacencyIterator > type; | |
47 | }; | |
48 | ||
49 | template < typename Vertex, typename Graph > | |
50 | typename result< get_all_adjacent_vertices( | |
51 | BOOST_FWD_REF(Vertex), BOOST_FWD_REF(Graph)) >::type | |
52 | operator()(BOOST_FWD_REF(Vertex) v, BOOST_FWD_REF(Graph) g) const | |
53 | { | |
54 | return adjacent_vertices( | |
55 | boost::forward< Vertex >(v), boost::forward< Graph >(g)); | |
56 | } | |
57 | }; | |
7c673cae | 58 | |
f67539c2 TL |
59 | //! @internal Functor returning a set of the vertices adjacent to a vertex. |
60 | struct get_unique_adjacent_vertices | |
61 | { | |
62 | template < typename Sig > struct result; | |
7c673cae | 63 | |
f67539c2 TL |
64 | template < typename This, typename Vertex, typename Graph > |
65 | struct result< This(Vertex, Graph) > | |
66 | { | |
67 | typedef std::set< typename remove_reference< Vertex >::type > type; | |
68 | }; | |
7c673cae | 69 | |
f67539c2 TL |
70 | template < typename Vertex, typename Graph > |
71 | typename result< get_unique_adjacent_vertices( | |
72 | Vertex, Graph const&) >::type | |
73 | operator()(Vertex v, Graph const& g) const | |
74 | { | |
75 | typedef typename result< get_unique_adjacent_vertices( | |
76 | Vertex, Graph const&) >::type Set; | |
77 | return Set( | |
78 | adjacent_vertices(v, g).first, adjacent_vertices(v, g).second); | |
79 | } | |
7c673cae FG |
80 | }; |
81 | ||
f67539c2 TL |
82 | //! @internal |
83 | //! Return whether a container contains a given value. | |
84 | //! This is not meant as a general purpose membership testing function; it | |
85 | //! would have to be more clever about possible optimizations. | |
86 | template < typename Container, typename Value > | |
87 | bool contains(Container const& c, Value const& v) | |
88 | { | |
89 | return std::find(boost::begin(c), boost::end(c), v) != boost::end(c); | |
7c673cae | 90 | } |
7c673cae | 91 | |
f67539c2 TL |
92 | /*! |
93 | * @internal | |
94 | * Algorithm finding all the cycles starting from a given vertex. | |
95 | * | |
96 | * The search is only done in the subgraph induced by the starting vertex | |
97 | * and the vertices with an index higher than the starting vertex. | |
98 | */ | |
99 | template < typename Graph, typename Visitor, typename VertexIndexMap, | |
100 | typename Stack, typename ClosedMatrix, typename GetAdjacentVertices > | |
101 | struct hawick_circuits_from | |
102 | { | |
103 | private: | |
104 | typedef graph_traits< Graph > Traits; | |
105 | typedef typename Traits::vertex_descriptor Vertex; | |
106 | typedef typename Traits::edge_descriptor Edge; | |
107 | typedef typename Traits::vertices_size_type VerticesSize; | |
108 | typedef | |
109 | typename property_traits< VertexIndexMap >::value_type VertexIndex; | |
110 | ||
111 | typedef typename result_of< GetAdjacentVertices( | |
112 | Vertex, Graph const&) >::type AdjacentVertices; | |
113 | typedef typename range_iterator< AdjacentVertices const >::type | |
114 | AdjacencyIterator; | |
115 | ||
116 | // The one_bit_color_map starts all white, i.e. not blocked. | |
117 | // Since we make that assumption (I looked at the implementation, but | |
118 | // I can't find anything that documents this behavior), we're gonna | |
119 | // assert it in the constructor. | |
120 | typedef one_bit_color_map< VertexIndexMap > BlockedMap; | |
121 | typedef typename property_traits< BlockedMap >::value_type BlockedColor; | |
122 | ||
123 | static BlockedColor blocked_false_color() | |
124 | { | |
125 | return color_traits< BlockedColor >::white(); | |
126 | } | |
7c673cae | 127 | |
f67539c2 TL |
128 | static BlockedColor blocked_true_color() |
129 | { | |
130 | return color_traits< BlockedColor >::black(); | |
131 | } | |
7c673cae | 132 | |
f67539c2 TL |
133 | // This is used by the constructor to secure the assumption |
134 | // documented above. | |
135 | bool blocked_map_starts_all_unblocked() const | |
136 | { | |
137 | BOOST_FOREACH (Vertex v, vertices(graph_)) | |
138 | if (is_blocked(v)) | |
139 | return false; | |
140 | return true; | |
141 | } | |
7c673cae | 142 | |
f67539c2 TL |
143 | // This is only used in the constructor to make sure the optimization of |
144 | // sharing data structures between iterations does not break the code. | |
145 | bool all_closed_rows_are_empty() const | |
146 | { | |
147 | BOOST_FOREACH (typename ClosedMatrix::reference row, closed_) | |
148 | if (!row.empty()) | |
149 | return false; | |
150 | return true; | |
151 | } | |
7c673cae | 152 | |
f67539c2 TL |
153 | public: |
154 | hawick_circuits_from(Graph const& graph, Visitor& visitor, | |
155 | VertexIndexMap const& vim, Stack& stack, ClosedMatrix& closed, | |
156 | VerticesSize n_vertices) | |
157 | : graph_(graph) | |
158 | , visitor_(visitor) | |
159 | , vim_(vim) | |
160 | , stack_(stack) | |
161 | , closed_(closed) | |
162 | , blocked_(n_vertices, vim_) | |
7c673cae FG |
163 | { |
164 | BOOST_ASSERT(blocked_map_starts_all_unblocked()); | |
165 | ||
166 | // Since sharing the data structures between iterations is | |
167 | // just an optimization, it must always be equivalent to | |
168 | // constructing new ones in this constructor. | |
169 | BOOST_ASSERT(stack_.empty()); | |
170 | BOOST_ASSERT(closed_.size() == n_vertices); | |
171 | BOOST_ASSERT(all_closed_rows_are_empty()); | |
172 | } | |
173 | ||
f67539c2 TL |
174 | private: |
175 | //! @internal Return the index of a given vertex. | |
176 | VertexIndex index_of(Vertex v) const { return get(vim_, v); } | |
7c673cae | 177 | |
f67539c2 TL |
178 | //! @internal Return whether a vertex `v` is closed to a vertex `u`. |
179 | bool is_closed_to(Vertex u, Vertex v) const | |
180 | { | |
181 | typedef typename ClosedMatrix::const_reference VertexList; | |
182 | VertexList closed_to_u = closed_[index_of(u)]; | |
183 | return contains(closed_to_u, v); | |
184 | } | |
7c673cae | 185 | |
f67539c2 TL |
186 | //! @internal Close a vertex `v` to a vertex `u`. |
187 | void close_to(Vertex u, Vertex v) | |
188 | { | |
189 | BOOST_ASSERT(!is_closed_to(u, v)); | |
190 | closed_[index_of(u)].push_back(v); | |
191 | } | |
7c673cae | 192 | |
f67539c2 TL |
193 | //! @internal Return whether a given vertex is blocked. |
194 | bool is_blocked(Vertex v) const | |
195 | { | |
196 | return get(blocked_, v) == blocked_true_color(); | |
197 | } | |
7c673cae | 198 | |
f67539c2 TL |
199 | //! @internal Block a given vertex. |
200 | void block(Vertex v) { put(blocked_, v, blocked_true_color()); } | |
7c673cae | 201 | |
f67539c2 TL |
202 | //! @internal Unblock a given vertex. |
203 | void unblock(Vertex u) | |
204 | { | |
205 | typedef typename ClosedMatrix::reference VertexList; | |
7c673cae | 206 | |
f67539c2 TL |
207 | put(blocked_, u, blocked_false_color()); |
208 | VertexList closed_to_u = closed_[index_of(u)]; | |
7c673cae | 209 | |
f67539c2 TL |
210 | while (!closed_to_u.empty()) |
211 | { | |
212 | Vertex const w = closed_to_u.back(); | |
213 | closed_to_u.pop_back(); | |
214 | if (is_blocked(w)) | |
215 | unblock(w); | |
216 | } | |
217 | BOOST_ASSERT(closed_to_u.empty()); | |
7c673cae | 218 | } |
7c673cae | 219 | |
f67539c2 TL |
220 | //! @internal Main procedure as described in the paper. |
221 | bool circuit(Vertex start, Vertex v) | |
7c673cae | 222 | { |
f67539c2 TL |
223 | bool found_circuit = false; |
224 | stack_.push_back(v); | |
225 | block(v); | |
7c673cae | 226 | |
f67539c2 TL |
227 | // Cache some values that are used more than once in the function. |
228 | VertexIndex const index_of_start = index_of(start); | |
229 | AdjacentVertices const adj_vertices | |
230 | = GetAdjacentVertices()(v, graph_); | |
231 | AdjacencyIterator const w_end = boost::end(adj_vertices); | |
7c673cae | 232 | |
7c673cae | 233 | for (AdjacencyIterator w_it = boost::begin(adj_vertices); |
f67539c2 | 234 | w_it != w_end; ++w_it) |
7c673cae FG |
235 | { |
236 | Vertex const w = *w_it; | |
f67539c2 TL |
237 | // Since we're only looking in the subgraph induced by `start` |
238 | // and the vertices with an index higher than `start`, we skip | |
239 | // any vertex that does not satisfy that. | |
7c673cae FG |
240 | if (index_of(w) < index_of_start) |
241 | continue; | |
242 | ||
f67539c2 TL |
243 | // If the last vertex is equal to `start`, we have a circuit. |
244 | else if (w == start) | |
245 | { | |
246 | // const_cast to ensure the visitor does not modify the | |
247 | // stack | |
248 | visitor_.cycle(const_cast< Stack const& >(stack_), graph_); | |
249 | found_circuit = true; | |
250 | } | |
251 | ||
252 | // If `w` is not blocked, we continue searching further down the | |
253 | // same path for a cycle with `w` in it. | |
254 | else if (!is_blocked(w) && circuit(start, w)) | |
255 | found_circuit = true; | |
7c673cae FG |
256 | } |
257 | ||
f67539c2 TL |
258 | if (found_circuit) |
259 | unblock(v); | |
260 | else | |
261 | for (AdjacencyIterator w_it = boost::begin(adj_vertices); | |
262 | w_it != w_end; ++w_it) | |
263 | { | |
264 | Vertex const w = *w_it; | |
265 | // Like above, we skip vertices that are not in the subgraph | |
266 | // we're considering. | |
267 | if (index_of(w) < index_of_start) | |
268 | continue; | |
269 | ||
270 | // If `v` is not closed to `w`, we make it so. | |
271 | if (!is_closed_to(w, v)) | |
272 | close_to(w, v); | |
273 | } | |
274 | ||
275 | BOOST_ASSERT(v == stack_.back()); | |
276 | stack_.pop_back(); | |
277 | return found_circuit; | |
278 | } | |
7c673cae | 279 | |
f67539c2 TL |
280 | public: |
281 | void operator()(Vertex start) { circuit(start, start); } | |
7c673cae | 282 | |
f67539c2 TL |
283 | private: |
284 | Graph const& graph_; | |
285 | Visitor& visitor_; | |
286 | VertexIndexMap const& vim_; | |
287 | Stack& stack_; | |
288 | ClosedMatrix& closed_; | |
289 | BlockedMap blocked_; | |
290 | }; | |
291 | ||
292 | template < typename GetAdjacentVertices, typename Graph, typename Visitor, | |
293 | typename VertexIndexMap > | |
294 | void call_hawick_circuits(Graph const& graph, | |
295 | Visitor /* by value */ visitor, VertexIndexMap const& vertex_index_map) | |
296 | { | |
297 | typedef graph_traits< Graph > Traits; | |
298 | typedef typename Traits::vertex_descriptor Vertex; | |
299 | typedef typename Traits::vertices_size_type VerticesSize; | |
300 | typedef typename Traits::vertex_iterator VertexIterator; | |
301 | ||
302 | typedef std::vector< Vertex > Stack; | |
303 | typedef std::vector< std::vector< Vertex > > ClosedMatrix; | |
304 | ||
305 | typedef hawick_circuits_from< Graph, Visitor, VertexIndexMap, Stack, | |
306 | ClosedMatrix, GetAdjacentVertices > | |
307 | SubAlgorithm; | |
308 | ||
309 | VerticesSize const n_vertices = num_vertices(graph); | |
310 | Stack stack; | |
311 | stack.reserve(n_vertices); | |
312 | ClosedMatrix closed(n_vertices); | |
313 | ||
314 | VertexIterator start, last; | |
315 | for (boost::tie(start, last) = vertices(graph); start != last; ++start) | |
316 | { | |
317 | // Note1: The sub algorithm may NOT be reused once it has been | |
318 | // called. | |
319 | ||
320 | // Note2: We reuse the Stack and the ClosedMatrix (after clearing | |
321 | // them) in each iteration to avoid redundant destruction and | |
322 | // construction. It would be strictly equivalent to have these as | |
323 | // member variables of the sub algorithm. | |
324 | SubAlgorithm sub_algo( | |
325 | graph, visitor, vertex_index_map, stack, closed, n_vertices); | |
326 | sub_algo(*start); | |
327 | stack.clear(); | |
328 | typename ClosedMatrix::iterator row, last_row = closed.end(); | |
329 | for (row = closed.begin(); row != last_row; ++row) | |
330 | row->clear(); | |
331 | } | |
7c673cae | 332 | } |
7c673cae | 333 | |
f67539c2 TL |
334 | template < typename GetAdjacentVertices, typename Graph, typename Visitor > |
335 | void call_hawick_circuits( | |
336 | Graph const& graph, BOOST_FWD_REF(Visitor) visitor) | |
337 | { | |
338 | call_hawick_circuits< GetAdjacentVertices >(graph, | |
339 | boost::forward< Visitor >(visitor), get(vertex_index, graph)); | |
340 | } | |
7c673cae FG |
341 | } // end namespace hawick_circuits_detail |
342 | ||
343 | //! Enumerate all the elementary circuits in a directed multigraph. | |
f67539c2 TL |
344 | template < typename Graph, typename Visitor, typename VertexIndexMap > |
345 | void hawick_circuits(BOOST_FWD_REF(Graph) graph, BOOST_FWD_REF(Visitor) visitor, | |
346 | BOOST_FWD_REF(VertexIndexMap) vertex_index_map) | |
347 | { | |
7c673cae | 348 | hawick_circuits_detail::call_hawick_circuits< |
f67539c2 TL |
349 | hawick_circuits_detail::get_all_adjacent_vertices >( |
350 | boost::forward< Graph >(graph), boost::forward< Visitor >(visitor), | |
351 | boost::forward< VertexIndexMap >(vertex_index_map)); | |
7c673cae FG |
352 | } |
353 | ||
f67539c2 TL |
354 | template < typename Graph, typename Visitor > |
355 | void hawick_circuits(BOOST_FWD_REF(Graph) graph, BOOST_FWD_REF(Visitor) visitor) | |
356 | { | |
7c673cae | 357 | hawick_circuits_detail::call_hawick_circuits< |
f67539c2 TL |
358 | hawick_circuits_detail::get_all_adjacent_vertices >( |
359 | boost::forward< Graph >(graph), boost::forward< Visitor >(visitor)); | |
7c673cae FG |
360 | } |
361 | ||
362 | /*! | |
363 | * Same as `boost::hawick_circuits`, but duplicate circuits caused by parallel | |
364 | * edges will not be considered. Each circuit will be considered only once. | |
365 | */ | |
f67539c2 | 366 | template < typename Graph, typename Visitor, typename VertexIndexMap > |
7c673cae | 367 | void hawick_unique_circuits(BOOST_FWD_REF(Graph) graph, |
f67539c2 TL |
368 | BOOST_FWD_REF(Visitor) visitor, |
369 | BOOST_FWD_REF(VertexIndexMap) vertex_index_map) | |
370 | { | |
7c673cae | 371 | hawick_circuits_detail::call_hawick_circuits< |
f67539c2 TL |
372 | hawick_circuits_detail::get_unique_adjacent_vertices >( |
373 | boost::forward< Graph >(graph), boost::forward< Visitor >(visitor), | |
374 | boost::forward< VertexIndexMap >(vertex_index_map)); | |
7c673cae FG |
375 | } |
376 | ||
f67539c2 TL |
377 | template < typename Graph, typename Visitor > |
378 | void hawick_unique_circuits( | |
379 | BOOST_FWD_REF(Graph) graph, BOOST_FWD_REF(Visitor) visitor) | |
380 | { | |
7c673cae | 381 | hawick_circuits_detail::call_hawick_circuits< |
f67539c2 TL |
382 | hawick_circuits_detail::get_unique_adjacent_vertices >( |
383 | boost::forward< Graph >(graph), boost::forward< Visitor >(visitor)); | |
7c673cae FG |
384 | } |
385 | } // end namespace boost | |
386 | ||
387 | #endif // !BOOST_GRAPH_HAWICK_CIRCUITS_HPP |