1 | // (C) Copyright 2007-2009 Andrew Sutton |
2 | // |
3 | // Use, modification and distribution are subject to the |
4 | // Boost Software License, Version 1.0 (See accompanying file |
5 | // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) |
6 | |
7 | #ifndef BOOST_GRAPH_CYCLE_HPP |
8 | #define BOOST_GRAPH_CYCLE_HPP |
9 | |
10 | #include <vector> |
11 | |
12 | #include <boost/config.hpp> |
13 | #include <boost/graph/graph_concepts.hpp> |
14 | #include <boost/graph/graph_traits.hpp> |
15 | #include <boost/graph/properties.hpp> |
16 | #include <boost/concept/assert.hpp> |
17 | |
18 | #include <boost/concept/detail/concept_def.hpp> |
19 | namespace boost { |
20 | namespace concepts { |
21 | BOOST_concept(CycleVisitor,(Visitor)(Path)(Graph)) |
22 | { |
23 | BOOST_CONCEPT_USAGE(CycleVisitor) |
24 | { |
25 | vis.cycle(p, g); |
26 | } |
27 | private: |
28 | Visitor vis; |
29 | Graph g; |
30 | Path p; |
31 | }; |
32 | } /* namespace concepts */ |
33 | using concepts::CycleVisitorConcept; |
34 | } /* namespace boost */ |
35 | #include <boost/concept/detail/concept_undef.hpp> |
36 | |
37 | |
38 | namespace boost |
39 | { |
40 | |
41 | // The implementation of this algorithm is a reproduction of the Teirnan |
42 | // approach for directed graphs: bibtex follows |
43 | // |
44 | // @article{362819, |
45 | // author = {James C. Tiernan}, |
46 | // title = {An efficient search algorithm to find the elementary circuits of a graph}, |
47 | // journal = {Commun. ACM}, |
48 | // volume = {13}, |
49 | // number = {12}, |
50 | // year = {1970}, |
51 | // issn = {0001-0782}, |
52 | // pages = {722--726}, |
53 | // doi = {http://doi.acm.org/10.1145/362814.362819}, |
54 | // publisher = {ACM Press}, |
55 | // address = {New York, NY, USA}, |
56 | // } |
57 | // |
58 | // It should be pointed out that the author does not provide a complete analysis for |
59 | // either time or space. This is in part, due to the fact that it's a fairly input |
60 | // sensitive problem related to the density and construction of the graph, not just |
61 | // its size. |
62 | // |
63 | // I've also taken some liberties with the interpretation of the algorithm - I've |
64 | // basically modernized it to use real data structures (no more arrays and matrices). |
65 | // Oh... and there's explicit control structures - not just gotos. |
66 | // |
67 | // The problem is definitely NP-complete, an unbounded implementation of this |
68 | // will probably run for quite a while on a large graph. The conclusions |
69 | // of this paper also reference a Paton algorithm for undirected graphs as being |
70 | // much more efficient (apparently based on spanning trees). Although not implemented, |
71 | // it can be found here: |
72 | // |
73 | // @article{363232, |
74 | // author = {Keith Paton}, |
75 | // title = {An algorithm for finding a fundamental set of cycles of a graph}, |
76 | // journal = {Commun. ACM}, |
77 | // volume = {12}, |
78 | // number = {9}, |
79 | // year = {1969}, |
80 | // issn = {0001-0782}, |
81 | // pages = {514--518}, |
82 | // doi = {http://doi.acm.org/10.1145/363219.363232}, |
83 | // publisher = {ACM Press}, |
84 | // address = {New York, NY, USA}, |
85 | // } |
86 | |
87 | /** |
88 | * The default cycle visitor provides an empty visit function for cycle |
89 | * visitors. |
90 | */ |
91 | struct cycle_visitor |
92 | { |
93 | template <typename Path, typename Graph> |
94 | inline void cycle(const Path& p, const Graph& g) |
95 | { } |
96 | }; |
97 | |
98 | /** |
99 | * The min_max_cycle_visitor simultaneously records the minimum and maximum |
100 | * cycles in a graph. |
101 | */ |
102 | struct min_max_cycle_visitor |
103 | { |
104 | min_max_cycle_visitor(std::size_t& min_, std::size_t& max_) |
105 | : minimum(min_), maximum(max_) |
106 | { } |
107 | |
108 | template <typename Path, typename Graph> |
109 | inline void cycle(const Path& p, const Graph& g) |
110 | { |
111 | BOOST_USING_STD_MIN(); |
112 | BOOST_USING_STD_MAX(); |
113 | std::size_t len = p.size(); |
114 | minimum = min BOOST_PREVENT_MACRO_SUBSTITUTION (minimum, len); |
115 | maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION (maximum, len); |
116 | } |
117 | std::size_t& minimum; |
118 | std::size_t& maximum; |
119 | }; |
120 | |
121 | inline min_max_cycle_visitor |
122 | find_min_max_cycle(std::size_t& min_, std::size_t& max_) |
123 | { return min_max_cycle_visitor(min_, max_); } |
124 | |
125 | namespace detail |
126 | { |
127 | template <typename Graph, typename Path> |
128 | inline bool |
129 | is_vertex_in_path(const Graph&, |
130 | typename graph_traits<Graph>::vertex_descriptor v, |
131 | const Path& p) |
132 | { |
133 | return (std::find(p.begin(), p.end(), v) != p.end()); |
134 | } |
135 | |
136 | template <typename Graph, typename ClosedMatrix> |
137 | inline bool |
138 | is_path_closed(const Graph& g, |
139 | typename graph_traits<Graph>::vertex_descriptor u, |
140 | typename graph_traits<Graph>::vertex_descriptor v, |
141 | const ClosedMatrix& closed) |
142 | { |
143 | // the path from u to v is closed if v can be found in the list |
144 | // of closed vertices associated with u. |
145 | typedef typename ClosedMatrix::const_reference Row; |
146 | Row r = closed[get(vertex_index, g, u)]; |
147 | if(find(r.begin(), r.end(), v) != r.end()) { |
148 | return true; |
149 | } |
150 | return false; |
151 | } |
152 | |
153 | template <typename Graph, typename Path, typename ClosedMatrix> |
154 | inline bool |
155 | can_extend_path(const Graph& g, |
156 | typename graph_traits<Graph>::edge_descriptor e, |
157 | const Path& p, |
158 | const ClosedMatrix& m) |
159 | { |
160 | BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> )); |
161 | BOOST_CONCEPT_ASSERT(( VertexIndexGraphConcept<Graph> )); |
162 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
163 | |
164 | // get the vertices in question |
165 | Vertex |
166 | u = source(e, g), |
167 | v = target(e, g); |
168 | |
169 | // conditions for allowing a traversal along this edge are: |
170 | // 1. the index of v must be greater than that at which the |
171 | // path is rooted (p.front()). |
172 | // 2. the vertex v cannot already be in the path |
173 | // 3. the vertex v cannot be closed to the vertex u |
174 | |
175 | bool indices = get(vertex_index, g, p.front()) < get(vertex_index, g, v); |
176 | bool path = !is_vertex_in_path(g, v, p); |
177 | bool closed = !is_path_closed(g, u, v, m); |
178 | return indices && path && closed; |
179 | } |
180 | |
181 | template <typename Graph, typename Path> |
182 | inline bool |
183 | can_wrap_path(const Graph& g, const Path& p) |
184 | { |
185 | BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> )); |
186 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
187 | typedef typename graph_traits<Graph>::out_edge_iterator OutIterator; |
188 | |
189 | // iterate over the out-edges of the back, looking for the |
190 | // front of the path. also, we can't travel along the same |
191 | // edge that we did on the way here, but we don't quite have the |
192 | // stringent requirements that we do in can_extend_path(). |
193 | Vertex |
194 | u = p.back(), |
195 | v = p.front(); |
196 | OutIterator i, end; |
197 | for(boost::tie(i, end) = out_edges(u, g); i != end; ++i) { |
198 | if((target(*i, g) == v)) { |
199 | return true; |
200 | } |
201 | } |
202 | return false; |
203 | } |
204 | |
205 | template <typename Graph, |
206 | typename Path, |
207 | typename ClosedMatrix> |
208 | inline typename graph_traits<Graph>::vertex_descriptor |
209 | extend_path(const Graph& g, |
210 | Path& p, |
211 | ClosedMatrix& closed) |
212 | { |
213 | BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> )); |
214 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
215 | typedef typename graph_traits<Graph>::out_edge_iterator OutIterator; |
216 | |
217 | // get the current vertex |
218 | Vertex u = p.back(); |
219 | Vertex ret = graph_traits<Graph>::null_vertex(); |
220 | |
221 | // AdjacencyIterator i, end; |
222 | OutIterator i, end; |
223 | for(boost::tie(i, end) = out_edges(u, g); i != end; ++i) { |
224 | Vertex v = target(*i, g); |
225 | |
226 | // if we can actually extend along this edge, |
227 | // then that's what we want to do |
228 | if(can_extend_path(g, *i, p, closed)) { |
229 | p.push_back(v); // add the vertex to the path |
230 | ret = v; |
231 | break; |
232 | } |
233 | } |
234 | return ret; |
235 | } |
236 | |
237 | template <typename Graph, typename Path, typename ClosedMatrix> |
238 | inline bool |
239 | exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed) |
240 | { |
241 | BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> )); |
242 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
243 | |
244 | // if there's more than one vertex in the path, this closes |
245 | // of some possible routes and returns true. otherwise, if there's |
246 | // only one vertex left, the vertex has been used up |
247 | if(p.size() > 1) { |
248 | // get the last and second to last vertices, popping the last |
249 | // vertex off the path |
250 | Vertex last, prev; |
251 | last = p.back(); |
252 | p.pop_back(); |
253 | prev = p.back(); |
254 | |
255 | // reset the closure for the last vertex of the path and |
256 | // indicate that the last vertex in p is now closed to |
257 | // the next-to-last vertex in p |
258 | closed[get(vertex_index, g, last)].clear(); |
259 | closed[get(vertex_index, g, prev)].push_back(last); |
260 | return true; |
261 | } |
262 | else { |
263 | return false; |
264 | } |
265 | } |
266 | |
267 | template <typename Graph, typename Visitor> |
268 | inline void |
269 | all_cycles_from_vertex(const Graph& g, |
270 | typename graph_traits<Graph>::vertex_descriptor v, |
271 | Visitor vis, |
272 | std::size_t minlen, |
273 | std::size_t maxlen) |
274 | { |
275 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); |
276 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
277 | typedef std::vector<Vertex> Path; |
278 | BOOST_CONCEPT_ASSERT(( CycleVisitorConcept<Visitor,Path,Graph> )); |
279 | typedef std::vector<Vertex> VertexList; |
280 | typedef std::vector<VertexList> ClosedMatrix; |
281 | |
282 | Path p; |
283 | ClosedMatrix closed(num_vertices(g), VertexList()); |
284 | Vertex null = graph_traits<Graph>::null_vertex(); |
285 | |
286 | // each path investigation starts at the ith vertex |
287 | p.push_back(v); |
288 | |
289 | while(1) { |
290 | // extend the path until we've reached the end or the |
291 | // maxlen-sized cycle |
292 | Vertex j = null; |
293 | while(((j = detail::extend_path(g, p, closed)) != null) |
294 | && (p.size() < maxlen)) |
295 | ; // empty loop |
296 | |
297 | // if we're done extending the path and there's an edge |
298 | // connecting the back to the front, then we should have |
299 | // a cycle. |
300 | if(detail::can_wrap_path(g, p) && p.size() >= minlen) { |
301 | vis.cycle(p, g); |
302 | } |
303 | |
304 | if(!detail::exhaust_paths(g, p, closed)) { |
305 | break; |
306 | } |
307 | } |
308 | } |
309 | |
310 | // Select the minimum allowable length of a cycle based on the directedness |
311 | // of the graph - 2 for directed, 3 for undirected. |
312 | template <typename D> struct min_cycles { enum { value = 2 }; }; |
313 | template <> struct min_cycles<undirected_tag> { enum { value = 3 }; }; |
314 | } /* namespace detail */ |
315 | |
316 | template <typename Graph, typename Visitor> |
317 | inline void |
318 | tiernan_all_cycles(const Graph& g, |
319 | Visitor vis, |
320 | std::size_t minlen, |
321 | std::size_t maxlen) |
322 | { |
323 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); |
324 | typedef typename graph_traits<Graph>::vertex_iterator VertexIterator; |
325 | |
326 | VertexIterator i, end; |
327 | for(boost::tie(i, end) = vertices(g); i != end; ++i) { |
328 | detail::all_cycles_from_vertex(g, *i, vis, minlen, maxlen); |
329 | } |
330 | } |
331 | |
332 | template <typename Graph, typename Visitor> |
333 | inline void |
334 | tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t maxlen) |
335 | { |
336 | typedef typename graph_traits<Graph>::directed_category Dir; |
337 | tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value, maxlen); |
338 | } |
339 | |
340 | template <typename Graph, typename Visitor> |
341 | inline void |
342 | tiernan_all_cycles(const Graph& g, Visitor vis) |
343 | { |
344 | typedef typename graph_traits<Graph>::directed_category Dir; |
345 | tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value, |
346 | (std::numeric_limits<std::size_t>::max)()); |
347 | } |
348 | |
349 | template <typename Graph> |
350 | inline std::pair<std::size_t, std::size_t> |
351 | tiernan_girth_and_circumference(const Graph& g) |
352 | { |
353 | std::size_t |
354 | min_ = (std::numeric_limits<std::size_t>::max)(), |
355 | max_ = 0; |
356 | tiernan_all_cycles(g, find_min_max_cycle(min_, max_)); |
357 | |
358 | // if this is the case, the graph is acyclic... |
359 | if(max_ == 0) max_ = min_; |
360 | |
361 | return std::make_pair(x&: min_, y&: max_); |
362 | } |
363 | |
364 | template <typename Graph> |
365 | inline std::size_t |
366 | tiernan_girth(const Graph& g) |
367 | { return tiernan_girth_and_circumference(g).first; } |
368 | |
369 | template <typename Graph> |
370 | inline std::size_t |
371 | tiernan_circumference(const Graph& g) |
372 | { return tiernan_girth_and_circumference(g).second; } |
373 | |
374 | } /* namespace boost */ |
375 | |
376 | #endif |
377 | |