]>
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 | ||
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(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(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(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(w)) | |
206 | unblock(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(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(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(w) && circuit(start, w)) | |
243 | found_circuit = true; | |
244 | } | |
245 | ||
246 | if (found_circuit) | |
247 | unblock(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(w) < index_of_start) | |
257 | continue; | |
258 | ||
259 | // If `v` is not closed to `w`, we make it so. | |
260 | if (!is_closed_to(w, v)) | |
261 | close_to(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, 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 |