comparison DEPENDENCIES/generic/include/boost/graph/tiernan_all_cycles.hpp @ 16:2665513ce2d3

Add boost headers

+// (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