text: // (C) Copyright 2007-2009 Andrew Sutton
  //
  // Use, modification and distribution are subject to the
  // Boost Software License, Version 1.0 (See accompanying file
  // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
  
  #ifndef BOOST_GRAPH_CYCLE_HPP
  #define BOOST_GRAPH_CYCLE_HPP
  
  #include <vector>
  
  #include <boost/config.hpp>
  #include <boost/graph/graph_concepts.hpp>
  #include <boost/graph/graph_traits.hpp>
  #include <boost/graph/properties.hpp>
  #include <boost/concept/assert.hpp>
  
  #include <boost/concept/detail/concept_def.hpp>
  namespace boost {
      namespace concepts {
          BOOST_concept(CycleVisitor,(Visitor)(Path)(Graph))
          {
              BOOST_CONCEPT_USAGE(CycleVisitor)
              {
                  vis.cycle(p, g);
              }
          private:
              Visitor vis;
              Graph g;
              Path p;
          };
      } /* namespace concepts */
  using concepts::CycleVisitorConcept;
  } /* namespace boost */
  #include <boost/concept/detail/concept_undef.hpp>
  
  
  namespace boost
  {
  
  // The implementation of this algorithm is a reproduction of the Teirnan
  // approach for directed graphs: bibtex follows
  //
  //     @article{362819,
  //         author = {James C. Tiernan},
  //         title = {An efficient search algorithm to find the elementary circuits of a graph},
  //         journal = {Commun. ACM},
  //         volume = {13},
  //         number = {12},
  //         year = {1970},
  //         issn = {0001-0782},
  //         pages = {722--726},
  //         doi = {http://doi.acm.org/10.1145/362814.362819},
  //             publisher = {ACM Press},
  //             address = {New York, NY, USA},
  //         }
  //
  // It should be pointed out that the author does not provide a complete analysis for
  // either time or space. This is in part, due to the fact that it's a fairly input
  // sensitive problem related to the density and construction of the graph, not just
  // its size.
  //
  // I've also taken some liberties with the interpretation of the algorithm - I've
  // basically modernized it to use real data structures (no more arrays and matrices).
  // Oh... and there's explicit control structures - not just gotos.
  //
  // The problem is definitely NP-complete, an unbounded implementation of this
  // will probably run for quite a while on a large graph. The conclusions
  // of this paper also reference a Paton algorithm for undirected graphs as being
  // much more efficient (apparently based on spanning trees). Although not implemented,
  // it can be found here:
  //
  //     @article{363232,
  //         author = {Keith Paton},
  //         title = {An algorithm for finding a fundamental set of cycles of a graph},
  //         journal = {Commun. ACM},
  //         volume = {12},
  //         number = {9},
  //         year = {1969},
  //         issn = {0001-0782},
  //         pages = {514--518},
  //         doi = {http://doi.acm.org/10.1145/363219.363232},
  //             publisher = {ACM Press},
  //             address = {New York, NY, USA},
  //         }
  
  /**
   * The default cycle visitor provides an empty visit function for cycle
   * visitors.
   */
  struct cycle_visitor
  {
      template <typename Path, typename Graph>
      inline void cycle(const Path& p, const Graph& g)
      { }
  };
  
  /**
   * The min_max_cycle_visitor simultaneously records the minimum and maximum
   * cycles in a graph.
   */
  struct min_max_cycle_visitor
  {
      min_max_cycle_visitor(std::size_t& min_, std::size_t& max_)
          : minimum(min_), maximum(max_)
      { }
  
      template <typename Path, typename Graph>
      inline void cycle(const Path& p, const Graph& g)
      {
          BOOST_USING_STD_MIN();
          BOOST_USING_STD_MAX();
          std::size_t len = p.size();
          minimum = min BOOST_PREVENT_MACRO_SUBSTITUTION (minimum, len);
          maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION (maximum, len);
      }
      std::size_t& minimum;
      std::size_t& maximum;
  };
  
  inline min_max_cycle_visitor
  find_min_max_cycle(std::size_t& min_, std::size_t& max_)
  { return min_max_cycle_visitor(min_, max_); }
  
  namespace detail
  {
      template <typename Graph, typename Path>
      inline bool
      is_vertex_in_path(const Graph&,
                          typename graph_traits<Graph>::vertex_descriptor v,
                          const Path& p)
      {
          return (std::find(p.begin(), p.end(), v) != p.end());
      }
  
      template <typename Graph, typename ClosedMatrix>
      inline bool
      is_path_closed(const Graph& g,
                      typename graph_traits<Graph>::vertex_descriptor u,
                      typename graph_traits<Graph>::vertex_descriptor v,
                      const ClosedMatrix& closed)
      {
          // the path from u to v is closed if v can be found in the list
          // of closed vertices associated with u.
          typedef typename ClosedMatrix::const_reference Row;
          Row r = closed[get(vertex_index, g, u)];
          if(find(r.begin(), r.end(), v) != r.end()) {
              return true;
          }
          return false;
      }
  
      template <typename Graph, typename Path, typename ClosedMatrix>
      inline bool
      can_extend_path(const Graph& g,
                      typename graph_traits<Graph>::edge_descriptor e,
                      const Path& p,
                      const ClosedMatrix& m)
      {
          BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
          BOOST_CONCEPT_ASSERT(( VertexIndexGraphConcept<Graph> ));
          typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  
          // get the vertices in question
          Vertex
              u = source(e, g),
              v = target(e, g);
  
          // conditions for allowing a traversal along this edge are:
          // 1. the index of v must be greater than that at which the
          //    path is rooted (p.front()).
          // 2. the vertex v cannot already be in the path
          // 3. the vertex v cannot be closed to the vertex u
  
          bool indices = get(vertex_index, g, p.front()) < get(vertex_index, g, v);
          bool path = !is_vertex_in_path(g, v, p);
          bool closed = !is_path_closed(g, u, v, m);
          return indices && path && closed;
      }
  
      template <typename Graph, typename Path>
      inline bool
      can_wrap_path(const Graph& g, const Path& p)
      {
          BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
          typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
          typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;
  
          // iterate over the out-edges of the back, looking for the
          // front of the path. also, we can't travel along the same
          // edge that we did on the way here, but we don't quite have the
          // stringent requirements that we do in can_extend_path().
          Vertex
              u = p.back(),
              v = p.front();
          OutIterator i, end;
          for(boost::tie(i, end) = out_edges(u, g); i != end; ++i) {
              if((target(*i, g) == v)) {
                  return true;
              }
          }
          return false;
      }
  
      template <typename Graph,
          typename Path,
          typename ClosedMatrix>
      inline typename graph_traits<Graph>::vertex_descriptor
      extend_path(const Graph& g,
                  Path& p,
                  ClosedMatrix& closed)
      {
          BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
          typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
          typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;
  
          // get the current vertex
          Vertex u = p.back();
          Vertex ret = graph_traits<Graph>::null_vertex();
  
          // AdjacencyIterator i, end;
          OutIterator i, end;
          for(boost::tie(i, end) = out_edges(u, g); i != end; ++i) {
              Vertex v = target(*i, g);
  
              // if we can actually extend along this edge,
              // then that's what we want to do
              if(can_extend_path(g, *i, p, closed)) {
                  p.push_back(v);         // add the vertex to the path
                  ret = v;
                  break;
              }
          }
          return ret;
      }
  
      template <typename Graph, typename Path, typename ClosedMatrix>
      inline bool
      exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
      {
          BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
          typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  
          // if there's more than one vertex in the path, this closes
          // of some possible routes and returns true. otherwise, if there's
          // only one vertex left, the vertex has been used up
          if(p.size() > 1) {
              // get the last and second to last vertices, popping the last
              // vertex off the path
              Vertex last, prev;
              last = p.back();
              p.pop_back();
              prev = p.back();
  
              // reset the closure for the last vertex of the path and
              // indicate that the last vertex in p is now closed to
              // the next-to-last vertex in p
              closed[get(vertex_index, g, last)].clear();
              closed[get(vertex_index, g, prev)].push_back(last);
              return true;
          }
          else {
              return false;
          }
      }
  
      template <typename Graph, typename Visitor>
      inline void
      all_cycles_from_vertex(const Graph& g,
                              typename graph_traits<Graph>::vertex_descriptor v,
                              Visitor vis,
                              std::size_t minlen,
                              std::size_t maxlen)
      {
          BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
          typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
          typedef std::vector<Vertex> Path;
          BOOST_CONCEPT_ASSERT(( CycleVisitorConcept<Visitor,Path,Graph> ));
          typedef std::vector<Vertex> VertexList;
          typedef std::vector<VertexList> ClosedMatrix;
  
          Path p;
          ClosedMatrix closed(num_vertices(g), VertexList());
          Vertex null = graph_traits<Graph>::null_vertex();
  
          // each path investigation starts at the ith vertex
          p.push_back(v);
  
          while(1) {
              // extend the path until we've reached the end or the
              // maxlen-sized cycle
              Vertex j = null;
              while(((j = detail::extend_path(g, p, closed)) != null)
                      && (p.size() < maxlen))
                  ; // empty loop
  
              // if we're done extending the path and there's an edge
              // connecting the back to the front, then we should have
              // a cycle.
              if(detail::can_wrap_path(g, p) && p.size() >= minlen) {
                  vis.cycle(p, g);
              }
  
              if(!detail::exhaust_paths(g, p, closed)) {
                  break;
              }
          }
      }
  
      // Select the minimum allowable length of a cycle based on the directedness
      // of the graph - 2 for directed, 3 for undirected.
      template <typename D> struct min_cycles { enum { value = 2 }; };
      template <> struct min_cycles<undirected_tag> { enum { value = 3 }; };
  } /* namespace detail */
  
  template <typename Graph, typename Visitor>
  inline void
  tiernan_all_cycles(const Graph& g,
                      Visitor vis,
                      std::size_t minlen,
                      std::size_t maxlen)
  {
      BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
      typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
  
      VertexIterator i, end;
      for(boost::tie(i, end) = vertices(g); i != end; ++i) {
          detail::all_cycles_from_vertex(g, *i, vis, minlen, maxlen);
      }
  }
  
  template <typename Graph, typename Visitor>
  inline void
  tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t maxlen)
  {
      typedef typename graph_traits<Graph>::directed_category Dir;
      tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value, maxlen);
  }
  
  template <typename Graph, typename Visitor>
  inline void
  tiernan_all_cycles(const Graph& g, Visitor vis)
  {
      typedef typename graph_traits<Graph>::directed_category Dir;
      tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value,
                         (std::numeric_limits<std::size_t>::max)());
  }
  
  template <typename Graph>
  inline std::pair<std::size_t, std::size_t>
  tiernan_girth_and_circumference(const Graph& g)
  {
      std::size_t
          min_ = (std::numeric_limits<std::size_t>::max)(),
          max_ = 0;
      tiernan_all_cycles(g, find_min_max_cycle(min_, max_));
  
      // if this is the case, the graph is acyclic...
      if(max_ == 0) max_ = min_;
  
      return std::make_pair(min_, max_);
  }
  
  template <typename Graph>
  inline std::size_t
  tiernan_girth(const Graph& g)
  { return tiernan_girth_and_circumference(g).first; }
  
  template <typename Graph>
  inline std::size_t
  tiernan_circumference(const Graph& g)
  { return tiernan_girth_and_circumference(g).second; }
  
  } /* namespace boost */
  
  #endif
  