boost/graph/tiernan_all_cycles.hpp

0001 // (C) Copyright 2007-2009 Andrew Sutton
0002 //
0003 // Use, modification and distribution are subject to the
0004 // Boost Software License, Version 1.0 (See accompanying file
0005 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_GRAPH_CYCLE_HPP
0008 #define BOOST_GRAPH_CYCLE_HPP
0009
0010 #include <vector>
0011
0012 #include <boost/config.hpp>
0013 #include <boost/graph/graph_concepts.hpp>
0014 #include <boost/graph/graph_traits.hpp>
0015 #include <boost/graph/properties.hpp>
0016 #include <boost/concept/assert.hpp>
0017
0018 #include <boost/concept/detail/concept_def.hpp>
0019 namespace boost
0020 {
0021 namespace concepts
0022 {
0023     BOOST_concept(CycleVisitor, (Visitor)(Path)(Graph))
0024     {
0025         BOOST_CONCEPT_USAGE(CycleVisitor) { vis.cycle(p, g); }
0026
0027     private:
0028         Visitor vis;
0029         Graph g;
0030         Path p;
0031     };
0032 } /* namespace concepts */
0033 using concepts::CycleVisitorConcept;
0034 } /* namespace boost */
0035 #include <boost/concept/detail/concept_undef.hpp>
0036
0037 namespace boost
0038 {
0039
0040 // The implementation of this algorithm is a reproduction of the Teirnan
0041 // approach for directed graphs: bibtex follows
0042 //
0043 //     @article{362819,
0044 //         author = {James C. Tiernan},
0045 //         title = {An efficient search algorithm to find the elementary
0046 //         circuits of a graph}, journal = {Commun. ACM}, volume = {13}, number
0047 //         = {12}, year = {1970}, issn = {0001-0782}, pages = {722--726}, doi =
0048 //         {http://doi.acm.org/10.1145/362814.362819},
0049 //             publisher = {ACM Press},
0050 //             address = {New York, NY, USA},
0051 //         }
0052 //
0053 // It should be pointed out that the author does not provide a complete analysis
0054 // for either time or space. This is in part, due to the fact that it's a fairly
0055 // input sensitive problem related to the density and construction of the graph,
0056 // not just its size.
0057 //
0058 // I've also taken some liberties with the interpretation of the algorithm -
0059 // I've basically modernized it to use real data structures (no more arrays and
0060 // matrices). Oh... and there's explicit control structures - not just gotos.
0061 //
0062 // The problem is definitely NP-complete, an unbounded implementation of this
0063 // will probably run for quite a while on a large graph. The conclusions
0064 // of this paper also reference a Paton algorithm for undirected graphs as being
0065 // much more efficient (apparently based on spanning trees). Although not
0066 // implemented, it can be found here:
0067 //
0068 //     @article{363232,
0069 //         author = {Keith Paton},
0070 //         title = {An algorithm for finding a fundamental set of cycles of a
0071 //         graph}, journal = {Commun. ACM}, volume = {12}, number = {9}, year =
0072 //         {1969}, issn = {0001-0782}, pages = {514--518}, doi =
0073 //         {http://doi.acm.org/10.1145/363219.363232},
0074 //             publisher = {ACM Press},
0075 //             address = {New York, NY, USA},
0076 //         }
0077
0078 /**
0079  * The default cycle visitor provides an empty visit function for cycle
0080  * visitors.
0081  */
0082 struct cycle_visitor
0083 {
0084     template < typename Path, typename Graph >
0085     inline void cycle(const Path& p, const Graph& g)
0086     {
0087     }
0088 };
0089
0090 /**
0091  * The min_max_cycle_visitor simultaneously records the minimum and maximum
0092  * cycles in a graph.
0093  */
0094 struct min_max_cycle_visitor
0095 {
0096     min_max_cycle_visitor(std::size_t& min_, std::size_t& max_)
0097     : minimum(min_), maximum(max_)
0098     {
0099     }
0100
0101     template < typename Path, typename Graph >
0102     inline void cycle(const Path& p, const Graph& g)
0103     {
0104         BOOST_USING_STD_MIN();
0105         BOOST_USING_STD_MAX();
0106         std::size_t len = p.size();
0107         minimum = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum, len);
0108         maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION(maximum, len);
0109     }
0110     std::size_t& minimum;
0111     std::size_t& maximum;
0112 };
0113
0114 inline min_max_cycle_visitor find_min_max_cycle(
0115     std::size_t& min_, std::size_t& max_)
0116 {
0117     return min_max_cycle_visitor(min_, max_);
0118 }
0119
0120 namespace detail
0121 {
0122     template < typename Graph, typename Path >
0123     inline bool is_vertex_in_path(const Graph&,
0124         typename graph_traits< Graph >::vertex_descriptor v, const Path& p)
0125     {
0126         return (std::find(p.begin(), p.end(), v) != p.end());
0127     }
0128
0129     template < typename Graph, typename ClosedMatrix >
0130     inline bool is_path_closed(const Graph& g,
0131         typename graph_traits< Graph >::vertex_descriptor u,
0132         typename graph_traits< Graph >::vertex_descriptor v,
0133         const ClosedMatrix& closed)
0134     {
0135         // the path from u to v is closed if v can be found in the list
0136         // of closed vertices associated with u.
0137         typedef typename ClosedMatrix::const_reference Row;
0138         Row r = closed[get(vertex_index, g, u)];
0139         if (find(r.begin(), r.end(), v) != r.end())
0140         {
0141             return true;
0142         }
0143         return false;
0144     }
0145
0146     template < typename Graph, typename Path, typename ClosedMatrix >
0147     inline bool can_extend_path(const Graph& g,
0148         typename graph_traits< Graph >::edge_descriptor e, const Path& p,
0149         const ClosedMatrix& m)
0150     {
0151         BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
0152         BOOST_CONCEPT_ASSERT((VertexIndexGraphConcept< Graph >));
0153         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0154
0155         // get the vertices in question
0156         Vertex u = source(e, g), v = target(e, g);
0157
0158         // conditions for allowing a traversal along this edge are:
0159         // 1. the index of v must be greater than that at which the
0160         //    path is rooted (p.front()).
0161         // 2. the vertex v cannot already be in the path
0162         // 3. the vertex v cannot be closed to the vertex u
0163
0164         bool indices
0165             = get(vertex_index, g, p.front()) < get(vertex_index, g, v);
0166         bool path = !is_vertex_in_path(g, v, p);
0167         bool closed = !is_path_closed(g, u, v, m);
0168         return indices && path && closed;
0169     }
0170
0171     template < typename Graph, typename Path >
0172     inline bool can_wrap_path(const Graph& g, const Path& p)
0173     {
0174         BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
0175         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0176         typedef typename graph_traits< Graph >::out_edge_iterator OutIterator;
0177
0178         // iterate over the out-edges of the back, looking for the
0179         // front of the path. also, we can't travel along the same
0180         // edge that we did on the way here, but we don't quite have the
0181         // stringent requirements that we do in can_extend_path().
0182         Vertex u = p.back(), v = p.front();
0183         OutIterator i, end;
0184         for (boost::tie(i, end) = out_edges(u, g); i != end; ++i)
0185         {
0186             if ((target(*i, g) == v))
0187             {
0188                 return true;
0189             }
0190         }
0191         return false;
0192     }
0193
0194     template < typename Graph, typename Path, typename ClosedMatrix >
0195     inline typename graph_traits< Graph >::vertex_descriptor extend_path(
0196         const Graph& g, Path& p, ClosedMatrix& closed)
0197     {
0198         BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
0199         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0200         typedef typename graph_traits< Graph >::out_edge_iterator OutIterator;
0201
0202         // get the current vertex
0203         Vertex u = p.back();
0204         Vertex ret = graph_traits< Graph >::null_vertex();
0205
0206         // AdjacencyIterator i, end;
0207         OutIterator i, end;
0208         for (boost::tie(i, end) = out_edges(u, g); i != end; ++i)
0209         {
0210             Vertex v = target(*i, g);
0211
0212             // if we can actually extend along this edge,
0213             // then that's what we want to do
0214             if (can_extend_path(g, *i, p, closed))
0215             {
0216                 p.push_back(v); // add the vertex to the path
0217                 ret = v;
0218                 break;
0219             }
0220         }
0221         return ret;
0222     }
0223
0224     template < typename Graph, typename Path, typename ClosedMatrix >
0225     inline bool exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
0226     {
0227         BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
0228         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0229
0230         // if there's more than one vertex in the path, this closes
0231         // of some possible routes and returns true. otherwise, if there's
0232         // only one vertex left, the vertex has been used up
0233         if (p.size() > 1)
0234         {
0235             // get the last and second to last vertices, popping the last
0236             // vertex off the path
0237             Vertex last, prev;
0238             last = p.back();
0239             p.pop_back();
0240             prev = p.back();
0241
0242             // reset the closure for the last vertex of the path and
0243             // indicate that the last vertex in p is now closed to
0244             // the next-to-last vertex in p
0245             closed[get(vertex_index, g, last)].clear();
0246             closed[get(vertex_index, g, prev)].push_back(last);
0247             return true;
0248         }
0249         else
0250         {
0251             return false;
0252         }
0253     }
0254
0255     template < typename Graph, typename Visitor >
0256     inline void all_cycles_from_vertex(const Graph& g,
0257         typename graph_traits< Graph >::vertex_descriptor v, Visitor vis,
0258         std::size_t minlen, std::size_t maxlen)
0259     {
0260         BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0261         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0262         typedef std::vector< Vertex > Path;
0263         BOOST_CONCEPT_ASSERT((CycleVisitorConcept< Visitor, Path, Graph >));
0264         typedef std::vector< Vertex > VertexList;
0265         typedef std::vector< VertexList > ClosedMatrix;
0266
0267         Path p;
0268         ClosedMatrix closed(num_vertices(g), VertexList());
0269         Vertex null = graph_traits< Graph >::null_vertex();
0270
0271         // each path investigation starts at the ith vertex
0272         p.push_back(v);
0273
0274         while (1)
0275         {
0276             // extend the path until we've reached the end or the
0277             // maxlen-sized cycle
0278             Vertex j = null;
0279             while (((j = detail::extend_path(g, p, closed)) != null)
0280                 && (p.size() < maxlen))
0281                 ; // empty loop
0282
0283             // if we're done extending the path and there's an edge
0284             // connecting the back to the front, then we should have
0285             // a cycle.
0286             if (detail::can_wrap_path(g, p) && p.size() >= minlen)
0287             {
0288                 vis.cycle(p, g);
0289             }
0290
0291             if (!detail::exhaust_paths(g, p, closed))
0292             {
0293                 break;
0294             }
0295         }
0296     }
0297
0298     // Select the minimum allowable length of a cycle based on the directedness
0299     // of the graph - 2 for directed, 3 for undirected.
0300     template < typename D > struct min_cycles
0301     {
0302         enum
0303         {
0304             value = 2
0305         };
0306     };
0307     template <> struct min_cycles< undirected_tag >
0308     {
0309         enum
0310         {
0311             value = 3
0312         };
0313     };
0314 } /* namespace detail */
0315
0316 template < typename Graph, typename Visitor >
0317 inline void tiernan_all_cycles(
0318     const Graph& g, Visitor vis, std::size_t minlen, std::size_t maxlen)
0319 {
0320     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0321     typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
0322
0323     VertexIterator i, end;
0324     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0325     {
0326         detail::all_cycles_from_vertex(g, *i, vis, minlen, maxlen);
0327     }
0328 }
0329
0330 template < typename Graph, typename Visitor >
0331 inline void tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t maxlen)
0332 {
0333     typedef typename graph_traits< Graph >::directed_category Dir;
0334     tiernan_all_cycles(g, vis, detail::min_cycles< Dir >::value, maxlen);
0335 }
0336
0337 template < typename Graph, typename Visitor >
0338 inline void tiernan_all_cycles(const Graph& g, Visitor vis)
0339 {
0340     typedef typename graph_traits< Graph >::directed_category Dir;
0341     tiernan_all_cycles(g, vis, detail::min_cycles< Dir >::value,
0342         (std::numeric_limits< std::size_t >::max)());
0343 }
0344
0345 template < typename Graph >
0346 inline std::pair< std::size_t, std::size_t > tiernan_girth_and_circumference(
0347     const Graph& g)
0348 {
0349     std::size_t min_ = (std::numeric_limits< std::size_t >::max)(), max_ = 0;
0350     tiernan_all_cycles(g, find_min_max_cycle(min_, max_));
0351
0352     // if this is the case, the graph is acyclic...
0353     if (max_ == 0)
0354         max_ = min_;
0355
0356     return std::make_pair(min_, max_);
0357 }
0358
0359 template < typename Graph > inline std::size_t tiernan_girth(const Graph& g)
0360 {
0361     return tiernan_girth_and_circumference(g).first;
0362 }
0363
0364 template < typename Graph >
0365 inline std::size_t tiernan_circumference(const Graph& g)
0366 {
0367     return tiernan_girth_and_circumference(g).second;
0368 }
0369
0370 } /* namespace boost */
0371
0372 #endif