ceph/src/boost/libs/graph/include/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 #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