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