boost/graph/tiernan_all_cycles.hpp

   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
  17 #include <boost/concept/detail/concept_def.hpp>
  18 namespace boost {
  19     namespace concepts {
  20         BOOST_concept(CycleVisitor,(Visitor)(Path)(Graph))
  21         {
  22             BOOST_CONCEPT_USAGE(CycleVisitor)
  23             {
  24                 vis.cycle(p, g);
  25             }
  26         private:
  27             Visitor vis;
  28             Graph g;
  29             Path p;
  30         };
  31     } /* namespace concepts */
  32 using concepts::CycleVisitorConcept;
  33 } /* namespace boost */
  34 #include <boost/concept/detail/concept_undef.hpp>
  35
  36
  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},
  45 //         title = {An efficient search algorithm to find the elementary circuits of a graph},
  46 //         journal = {Commun. ACM},
  47 //         volume = {13},
  48 //         number = {12},
  49 //         year = {1970},
  50 //         issn = {0001-0782},
  51 //         pages = {722--726},
  52 //         doi = {http://doi.acm.org/10.1145/362814.362819},
  53 //             publisher = {ACM Press},
  54 //             address = {New York, NY, USA},
  55 //         }
  56 //
  57 // It should be pointed out that the author does not provide a complete analysis for
  58 // either time or space. This is in part, due to the fact that it's a fairly input
  59 // sensitive problem related to the density and construction of the graph, not just
  60 // its size.
  61 //
  62 // I've also taken some liberties with the interpretation of the algorithm - I've
  63 // basically modernized it to use real data structures (no more arrays and matrices).
  64 // Oh... and there's explicit control structures - not just gotos.
  65 //
  66 // The problem is definitely NP-complete, an an unbounded implementation of this
  67 // will probably run for quite a while on a large graph. The conclusions
  68 // of this paper also reference a Paton algorithm for undirected graphs as being
  69 // much more efficient (apparently based on spanning trees). Although not implemented,
  70 // it can be found here:
  71 //
  72 //     @article{363232,
  73 //         author = {Keith Paton},
  74 //         title = {An algorithm for finding a fundamental set of cycles of a graph},
  75 //         journal = {Commun. ACM},
  76 //         volume = {12},
  77 //         number = {9},
  78 //         year = {1969},
  79 //         issn = {0001-0782},
  80 //         pages = {514--518},
  81 //         doi = {http://doi.acm.org/10.1145/363219.363232},
  82 //             publisher = {ACM Press},
  83 //             address = {New York, NY, USA},
  84 //         }
  85
  86 /**
  87  * The default cycle visitor providse an empty visit function for cycle
  88  * visitors.
  89  */
  90 struct cycle_visitor
  91 {
  92     template <typename Path, typename Graph>
  93     inline void cycle(const Path& p, const Graph& g)
  94     { }
  95 };
  96
  97 /**
  98  * The min_max_cycle_visitor simultaneously records the minimum and maximum
  99  * cycles in a graph.
 100  */
 101 struct min_max_cycle_visitor
 102 {
 103     min_max_cycle_visitor(std::size_t& min_, std::size_t& max_)
 104         : minimum(min_), maximum(max_)
 105     { }
 106
 107     template <typename Path, typename Graph>
 108     inline void cycle(const Path& p, const Graph& g)
 109     {
 110         BOOST_USING_STD_MIN();
 111         BOOST_USING_STD_MAX();
 112         std::size_t len = p.size();
 113         minimum = min BOOST_PREVENT_MACRO_SUBSTITUTION (minimum, len);
 114         maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION (maximum, len);
 115     }
 116     std::size_t& minimum;
 117     std::size_t& maximum;
 118 };
 119
 120 inline min_max_cycle_visitor
 121 find_min_max_cycle(std::size_t& min_, std::size_t& max_)
 122 { return min_max_cycle_visitor(min_, max_); }
 123
 124 namespace detail
 125 {
 126     template <typename Graph, typename Path>
 127     inline bool
 128     is_vertex_in_path(const Graph&,
 129                         typename graph_traits<Graph>::vertex_descriptor v,
 130                         const Path& p)
 131     {
 132         return (std::find(p.begin(), p.end(), v) != p.end());
 133     }
 134
 135     template <typename Graph, typename ClosedMatrix>
 136     inline bool
 137     is_path_closed(const Graph& g,
 138                     typename graph_traits<Graph>::vertex_descriptor u,
 139                     typename graph_traits<Graph>::vertex_descriptor v,
 140                     const ClosedMatrix& closed)
 141     {
 142         // the path from u to v is closed if v can be found in the list
 143         // of closed vertices associated with u.
 144         typedef typename ClosedMatrix::const_reference Row;
 145         Row r = closed[get(vertex_index, g, u)];
 146         if(find(r.begin(), r.end(), v) != r.end()) {
 147             return true;
 148         }
 149         return false;
 150     }
 151
 152     template <typename Graph, typename Path, typename ClosedMatrix>
 153     inline bool
 154     can_extend_path(const Graph& g,
 155                     typename graph_traits<Graph>::edge_descriptor e,
 156                     const Path& p,
 157                     const ClosedMatrix& m)
 158     {
 159         function_requires< IncidenceGraphConcept<Graph> >();
 160         function_requires< VertexIndexGraphConcept<Graph> >();
 161         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 162
 163         // get the vertices in question
 164         Vertex
 165             u = source(e, g),
 166             v = target(e, g);
 167
 168         // conditions for allowing a traversal along this edge are:
 169         // 1. the index of v must be greater than that at which the
 170         //    the path is rooted (p.front()).
 171         // 2. the vertex v cannot already be in the path
 172         // 3. the vertex v cannot be closed to the vertex u
 173
 174         bool indices = get(vertex_index, g, p.front()) < get(vertex_index, g, v);
 175         bool path = !is_vertex_in_path(g, v, p);
 176         bool closed = !is_path_closed(g, u, v, m);
 177         return indices && path && closed;
 178     }
 179
 180     template <typename Graph, typename Path>
 181     inline bool
 182     can_wrap_path(const Graph& g, const Path& p)
 183     {
 184         function_requires< IncidenceGraphConcept<Graph> >();
 185         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 186         typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;
 187
 188         // iterate over the out-edges of the back, looking for the
 189         // front of the path. also, we can't travel along the same
 190         // edge that we did on the way here, but we don't quite have the
 191         // stringent requirements that we do in can_extend_path().
 192         Vertex
 193             u = p.back(),
 194             v = p.front();
 195         OutIterator i, end;
 196         for(tie(i, end) = out_edges(u, g); i != end; ++i) {
 197             if((target(*i, g) == v)) {
 198                 return true;
 199             }
 200         }
 201         return false;
 202     }
 203
 204     template <typename Graph,
 205         typename Path,
 206         typename ClosedMatrix>
 207     inline typename graph_traits<Graph>::vertex_descriptor
 208     extend_path(const Graph& g,
 209                 Path& p,
 210                 ClosedMatrix& closed)
 211     {
 212         function_requires< IncidenceGraphConcept<Graph> >();
 213         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 214         typedef typename graph_traits<Graph>::edge_descriptor Edge;
 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(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         function_requires< 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         function_requires< VertexListGraphConcept<Graph> >();
 276         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 277         typedef std::vector<Vertex> Path;
 278         function_requires< 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     function_requires< VertexListGraphConcept<Graph> >();
 324     typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
 325
 326     VertexIterator i, end;
 327     for(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