]>
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> | |
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(min_, 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 |