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