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>
19namespace 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 */
33using concepts::CycleVisitorConcept;
34} /* namespace boost */
35#include <boost/concept/detail/concept_undef.hpp>
36
37
38namespace 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 */
91struct 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 */
102struct 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
121inline min_max_cycle_visitor
122find_min_max_cycle(std::size_t& min_, std::size_t& max_)
123{ return min_max_cycle_visitor(min_, max_); }
124
125namespace 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
316template <typename Graph, typename Visitor>
317inline void
318tiernan_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
332template <typename Graph, typename Visitor>
333inline void
334tiernan_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
340template <typename Graph, typename Visitor>
341inline void
342tiernan_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
349template <typename Graph>
350inline std::pair<std::size_t, std::size_t>
351tiernan_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
364template <typename Graph>
365inline std::size_t
366tiernan_girth(const Graph& g)
367{ return tiernan_girth_and_circumference(g).first; }
368
369template <typename Graph>
370inline std::size_t
371tiernan_circumference(const Graph& g)
372{ return tiernan_girth_and_circumference(g).second; }
373
374} /* namespace boost */
375
376#endif
377

source code of boost/boost/graph/tiernan_all_cycles.hpp