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