diff options
author | Anas Nashif <anas.nashif@intel.com> | 2012-10-30 12:57:26 -0700 |
---|---|---|
committer | Anas Nashif <anas.nashif@intel.com> | 2012-10-30 12:57:26 -0700 |
commit | 1a78a62555be32868418fe52f8e330c9d0f95d5a (patch) | |
tree | d3765a80e7d3b9640ec2e930743630cd6b9fce2b /boost/graph/tiernan_all_cycles.hpp | |
download | boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.tar.gz boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.tar.bz2 boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.zip |
Imported Upstream version 1.49.0upstream/1.49.0
Diffstat (limited to 'boost/graph/tiernan_all_cycles.hpp')
-rw-r--r-- | boost/graph/tiernan_all_cycles.hpp | 377 |
1 files changed, 377 insertions, 0 deletions
diff --git a/boost/graph/tiernan_all_cycles.hpp b/boost/graph/tiernan_all_cycles.hpp new file mode 100644 index 0000000000..2e7ebc97cd --- /dev/null +++ b/boost/graph/tiernan_all_cycles.hpp @@ -0,0 +1,377 @@ +// (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 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 providse 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 + // 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>::edge_descriptor Edge; + 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 |