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 | |
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 | }; |
58 | |
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; |
63 | |
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 | }; |
69 | |
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 | } |
80 | }; |
81 | |
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); |
90 | } |
91 | |
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 | } |
127 | |
128 | static BlockedColor blocked_true_color() |
129 | { |
130 | return color_traits< BlockedColor >::black(); |
131 | } |
132 | |
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 | } |
142 | |
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 | } |
152 | |
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_) |
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 | |
174 | private: |
175 | //! @internal Return the index of a given vertex. |
176 | VertexIndex index_of(Vertex v) const { return get(vim_, v); } |
177 | |
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(v: u)]; |
183 | return contains(closed_to_u, v); |
184 | } |
185 | |
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(v: u)].push_back(v); |
191 | } |
192 | |
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 | } |
198 | |
199 | //! @internal Block a given vertex. |
200 | void block(Vertex v) { put(blocked_, v, blocked_true_color()); } |
201 | |
202 | //! @internal Unblock a given vertex. |
203 | void unblock(Vertex u) |
204 | { |
205 | typedef typename ClosedMatrix::reference VertexList; |
206 | |
207 | put(blocked_, u, blocked_false_color()); |
208 | VertexList closed_to_u = closed_[index_of(v: u)]; |
209 | |
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(v: w)) |
215 | unblock(u: w); |
216 | } |
217 | BOOST_ASSERT(closed_to_u.empty()); |
218 | } |
219 | |
220 | //! @internal Main procedure as described in the paper. |
221 | bool circuit(Vertex start, Vertex v) |
222 | { |
223 | bool found_circuit = false; |
224 | stack_.push_back(v); |
225 | block(v); |
226 | |
227 | // Cache some values that are used more than once in the function. |
228 | VertexIndex const index_of_start = index_of(v: start); |
229 | AdjacentVertices const adj_vertices |
230 | = GetAdjacentVertices()(v, graph_); |
231 | AdjacencyIterator const w_end = boost::end(adj_vertices); |
232 | |
233 | for (AdjacencyIterator w_it = boost::begin(adj_vertices); |
234 | w_it != w_end; ++w_it) |
235 | { |
236 | Vertex const w = *w_it; |
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. |
240 | if (index_of(v: w) < index_of_start) |
241 | continue; |
242 | |
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(v: w) && circuit(start, v: w)) |
255 | found_circuit = true; |
256 | } |
257 | |
258 | if (found_circuit) |
259 | unblock(u: 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(v: w) < index_of_start) |
268 | continue; |
269 | |
270 | // If `v` is not closed to `w`, we make it so. |
271 | if (!is_closed_to(u: w, v)) |
272 | close_to(u: w, v); |
273 | } |
274 | |
275 | BOOST_ASSERT(v == stack_.back()); |
276 | stack_.pop_back(); |
277 | return found_circuit; |
278 | } |
279 | |
280 | public: |
281 | void operator()(Vertex start) { circuit(start, v: start); } |
282 | |
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 | } |
332 | } |
333 | |
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 | } |
341 | } // end namespace hawick_circuits_detail |
342 | |
343 | //! Enumerate all the elementary circuits in a directed multigraph. |
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 | { |
348 | hawick_circuits_detail::call_hawick_circuits< |
349 | hawick_circuits_detail::get_all_adjacent_vertices >( |
350 | boost::forward< Graph >(graph), boost::forward< Visitor >(visitor), |
351 | boost::forward< VertexIndexMap >(vertex_index_map)); |
352 | } |
353 | |
354 | template < typename Graph, typename Visitor > |
355 | void hawick_circuits(BOOST_FWD_REF(Graph) graph, BOOST_FWD_REF(Visitor) visitor) |
356 | { |
357 | hawick_circuits_detail::call_hawick_circuits< |
358 | hawick_circuits_detail::get_all_adjacent_vertices >( |
359 | boost::forward< Graph >(graph), boost::forward< Visitor >(visitor)); |
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 | */ |
366 | template < typename Graph, typename Visitor, typename VertexIndexMap > |
367 | void hawick_unique_circuits(BOOST_FWD_REF(Graph) graph, |
368 | BOOST_FWD_REF(Visitor) visitor, |
369 | BOOST_FWD_REF(VertexIndexMap) vertex_index_map) |
370 | { |
371 | hawick_circuits_detail::call_hawick_circuits< |
372 | hawick_circuits_detail::get_unique_adjacent_vertices >( |
373 | boost::forward< Graph >(graph), boost::forward< Visitor >(visitor), |
374 | boost::forward< VertexIndexMap >(vertex_index_map)); |
375 | } |
376 | |
377 | template < typename Graph, typename Visitor > |
378 | void hawick_unique_circuits( |
379 | BOOST_FWD_REF(Graph) graph, BOOST_FWD_REF(Visitor) visitor) |
380 | { |
381 | hawick_circuits_detail::call_hawick_circuits< |
382 | hawick_circuits_detail::get_unique_adjacent_vertices >( |
383 | boost::forward< Graph >(graph), boost::forward< Visitor >(visitor)); |
384 | } |
385 | } // end namespace boost |
386 | |
387 | #endif // !BOOST_GRAPH_HAWICK_CIRCUITS_HPP |
388 | |