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