123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381 |
- // Copyright Louis Dionne 2013
- // Use, modification and distribution is subject to the Boost Software
- // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy
- // at http://www.boost.org/LICENSE_1_0.txt)
- #ifndef BOOST_GRAPH_HAWICK_CIRCUITS_HPP
- #define BOOST_GRAPH_HAWICK_CIRCUITS_HPP
- #include <algorithm>
- #include <boost/assert.hpp>
- #include <boost/foreach.hpp>
- #include <boost/graph/graph_traits.hpp>
- #include <boost/graph/one_bit_color_map.hpp>
- #include <boost/graph/properties.hpp>
- #include <boost/move/utility.hpp>
- #include <boost/property_map/property_map.hpp>
- #include <boost/range/begin.hpp>
- #include <boost/range/end.hpp>
- #include <boost/range/iterator.hpp>
- #include <boost/tuple/tuple.hpp> // for boost::tie
- #include <boost/type_traits/remove_reference.hpp>
- #include <boost/utility/result_of.hpp>
- #include <set>
- #include <utility> // for std::pair
- #include <vector>
- namespace boost {
- namespace hawick_circuits_detail {
- //! @internal Functor returning all the vertices adjacent to a vertex.
- struct get_all_adjacent_vertices {
- template <typename Sig>
- struct result;
- template <typename This, typename Vertex, typename Graph>
- struct result<This(Vertex, Graph)> {
- private:
- typedef typename remove_reference<Graph>::type RawGraph;
- typedef graph_traits<RawGraph> Traits;
- typedef typename Traits::adjacency_iterator AdjacencyIterator;
- public:
- typedef std::pair<AdjacencyIterator, AdjacencyIterator> type;
- };
- template <typename Vertex, typename Graph>
- typename result<
- get_all_adjacent_vertices(BOOST_FWD_REF(Vertex), BOOST_FWD_REF(Graph))
- >::type
- operator()(BOOST_FWD_REF(Vertex) v, BOOST_FWD_REF(Graph) g) const {
- return adjacent_vertices(boost::forward<Vertex>(v),
- boost::forward<Graph>(g));
- }
- };
- //! @internal Functor returning a set of the vertices adjacent to a vertex.
- struct get_unique_adjacent_vertices {
- template <typename Sig>
- struct result;
- template <typename This, typename Vertex, typename Graph>
- struct result<This(Vertex, Graph)> {
- typedef std::set<typename remove_reference<Vertex>::type> type;
- };
- template <typename Vertex, typename Graph>
- typename result<get_unique_adjacent_vertices(Vertex, Graph const&)>::type
- operator()(Vertex v, Graph const& g) const {
- typedef typename result<
- get_unique_adjacent_vertices(Vertex, Graph const&)
- >::type Set;
- return Set(adjacent_vertices(v, g).first,
- adjacent_vertices(v, g).second);
- }
- };
- //! @internal
- //! Return whether a container contains a given value.
- //! This is not meant as a general purpose membership testing function; it
- //! would have to be more clever about possible optimizations.
- template <typename Container, typename Value>
- bool contains(Container const& c, Value const& v) {
- return std::find(boost::begin(c), boost::end(c), v) != boost::end(c);
- }
- /*!
- * @internal
- * Algorithm finding all the cycles starting from a given vertex.
- *
- * The search is only done in the subgraph induced by the starting vertex
- * and the vertices with an index higher than the starting vertex.
- */
- template <
- typename Graph,
- typename Visitor,
- typename VertexIndexMap,
- typename Stack,
- typename ClosedMatrix,
- typename GetAdjacentVertices
- >
- struct hawick_circuits_from {
- private:
- typedef graph_traits<Graph> Traits;
- typedef typename Traits::vertex_descriptor Vertex;
- typedef typename Traits::edge_descriptor Edge;
- typedef typename Traits::vertices_size_type VerticesSize;
- typedef typename property_traits<VertexIndexMap>::value_type VertexIndex;
- typedef typename result_of<
- GetAdjacentVertices(Vertex, Graph const&)
- >::type AdjacentVertices;
- typedef typename range_iterator<AdjacentVertices const>::type AdjacencyIterator;
- // The one_bit_color_map starts all white, i.e. not blocked.
- // Since we make that assumption (I looked at the implementation, but
- // I can't find anything that documents this behavior), we're gonna
- // assert it in the constructor.
- typedef one_bit_color_map<VertexIndexMap> BlockedMap;
- typedef typename property_traits<BlockedMap>::value_type BlockedColor;
- static BlockedColor blocked_false_color()
- { return color_traits<BlockedColor>::white(); }
- static BlockedColor blocked_true_color()
- { return color_traits<BlockedColor>::black(); }
- // This is used by the constructor to secure the assumption
- // documented above.
- bool blocked_map_starts_all_unblocked() const {
- BOOST_FOREACH(Vertex v, vertices(graph_))
- if (is_blocked(v))
- return false;
- return true;
- }
- // This is only used in the constructor to make sure the optimization of
- // sharing data structures between iterations does not break the code.
- bool all_closed_rows_are_empty() const {
- BOOST_FOREACH(typename ClosedMatrix::reference row, closed_)
- if (!row.empty())
- return false;
- return true;
- }
- public:
- hawick_circuits_from(Graph const& graph, Visitor& visitor,
- VertexIndexMap const& vim,
- Stack& stack, ClosedMatrix& closed,
- VerticesSize n_vertices)
- : graph_(graph), visitor_(visitor), vim_(vim), stack_(stack),
- closed_(closed), blocked_(n_vertices, vim_)
- {
- BOOST_ASSERT(blocked_map_starts_all_unblocked());
- // Since sharing the data structures between iterations is
- // just an optimization, it must always be equivalent to
- // constructing new ones in this constructor.
- BOOST_ASSERT(stack_.empty());
- BOOST_ASSERT(closed_.size() == n_vertices);
- BOOST_ASSERT(all_closed_rows_are_empty());
- }
- private:
- //! @internal Return the index of a given vertex.
- VertexIndex index_of(Vertex v) const {
- return get(vim_, v);
- }
- //! @internal Return whether a vertex `v` is closed to a vertex `u`.
- bool is_closed_to(Vertex u, Vertex v) const {
- typedef typename ClosedMatrix::const_reference VertexList;
- VertexList closed_to_u = closed_[index_of(u)];
- return contains(closed_to_u, v);
- }
- //! @internal Close a vertex `v` to a vertex `u`.
- void close_to(Vertex u, Vertex v) {
- BOOST_ASSERT(!is_closed_to(u, v));
- closed_[index_of(u)].push_back(v);
- }
- //! @internal Return whether a given vertex is blocked.
- bool is_blocked(Vertex v) const {
- return get(blocked_, v) == blocked_true_color();
- }
- //! @internal Block a given vertex.
- void block(Vertex v) {
- put(blocked_, v, blocked_true_color());
- }
- //! @internal Unblock a given vertex.
- void unblock(Vertex u) {
- typedef typename ClosedMatrix::reference VertexList;
- put(blocked_, u, blocked_false_color());
- VertexList closed_to_u = closed_[index_of(u)];
- while (!closed_to_u.empty()) {
- Vertex const w = closed_to_u.back();
- closed_to_u.pop_back();
- if (is_blocked(w))
- unblock(w);
- }
- BOOST_ASSERT(closed_to_u.empty());
- }
- //! @internal Main procedure as described in the paper.
- bool circuit(Vertex start, Vertex v) {
- bool found_circuit = false;
- stack_.push_back(v);
- block(v);
- // Cache some values that are used more than once in the function.
- VertexIndex const index_of_start = index_of(start);
- AdjacentVertices const adj_vertices = GetAdjacentVertices()(v, graph_);
- AdjacencyIterator const w_end = boost::end(adj_vertices);
- for (AdjacencyIterator w_it = boost::begin(adj_vertices);
- w_it != w_end;
- ++w_it)
- {
- Vertex const w = *w_it;
- // Since we're only looking in the subgraph induced by `start`
- // and the vertices with an index higher than `start`, we skip
- // any vertex that does not satisfy that.
- if (index_of(w) < index_of_start)
- continue;
- // If the last vertex is equal to `start`, we have a circuit.
- else if (w == start) {
- // const_cast to ensure the visitor does not modify the stack
- visitor_.cycle(const_cast<Stack const&>(stack_), graph_);
- found_circuit = true;
- }
- // If `w` is not blocked, we continue searching further down the
- // same path for a cycle with `w` in it.
- else if (!is_blocked(w) && circuit(start, w))
- found_circuit = true;
- }
- if (found_circuit)
- unblock(v);
- else
- for (AdjacencyIterator w_it = boost::begin(adj_vertices);
- w_it != w_end;
- ++w_it)
- {
- Vertex const w = *w_it;
- // Like above, we skip vertices that are not in the subgraph
- // we're considering.
- if (index_of(w) < index_of_start)
- continue;
- // If `v` is not closed to `w`, we make it so.
- if (!is_closed_to(w, v))
- close_to(w, v);
- }
- BOOST_ASSERT(v == stack_.back());
- stack_.pop_back();
- return found_circuit;
- }
- public:
- void operator()(Vertex start) {
- circuit(start, start);
- }
- private:
- Graph const& graph_;
- Visitor& visitor_;
- VertexIndexMap const& vim_;
- Stack& stack_;
- ClosedMatrix& closed_;
- BlockedMap blocked_;
- };
- template <
- typename GetAdjacentVertices,
- typename Graph, typename Visitor, typename VertexIndexMap
- >
- void call_hawick_circuits(Graph const& graph,
- Visitor /* by value */ visitor,
- VertexIndexMap const& vertex_index_map) {
- typedef graph_traits<Graph> Traits;
- typedef typename Traits::vertex_descriptor Vertex;
- typedef typename Traits::vertices_size_type VerticesSize;
- typedef typename Traits::vertex_iterator VertexIterator;
- typedef std::vector<Vertex> Stack;
- typedef std::vector<std::vector<Vertex> > ClosedMatrix;
- typedef hawick_circuits_from<
- Graph, Visitor, VertexIndexMap, Stack, ClosedMatrix,
- GetAdjacentVertices
- > SubAlgorithm;
- VerticesSize const n_vertices = num_vertices(graph);
- Stack stack; stack.reserve(n_vertices);
- ClosedMatrix closed(n_vertices);
- VertexIterator start, last;
- for (boost::tie(start, last) = vertices(graph); start != last; ++start) {
- // Note1: The sub algorithm may NOT be reused once it has been called.
- // Note2: We reuse the Stack and the ClosedMatrix (after clearing them)
- // in each iteration to avoid redundant destruction and construction.
- // It would be strictly equivalent to have these as member variables
- // of the sub algorithm.
- SubAlgorithm sub_algo(graph, visitor, vertex_index_map,
- stack, closed, n_vertices);
- sub_algo(*start);
- stack.clear();
- typename ClosedMatrix::iterator row, last_row = closed.end();
- for (row = closed.begin(); row != last_row; ++row)
- row->clear();
- }
- }
- template <typename GetAdjacentVertices, typename Graph, typename Visitor>
- void call_hawick_circuits(Graph const& graph, BOOST_FWD_REF(Visitor) visitor) {
- call_hawick_circuits<GetAdjacentVertices>(
- graph, boost::forward<Visitor>(visitor), get(vertex_index, graph)
- );
- }
- } // end namespace hawick_circuits_detail
- //! Enumerate all the elementary circuits in a directed multigraph.
- template <typename Graph, typename Visitor, typename VertexIndexMap>
- void hawick_circuits(BOOST_FWD_REF(Graph) graph,
- BOOST_FWD_REF(Visitor) visitor,
- BOOST_FWD_REF(VertexIndexMap) vertex_index_map) {
- hawick_circuits_detail::call_hawick_circuits<
- hawick_circuits_detail::get_all_adjacent_vertices
- >(
- boost::forward<Graph>(graph),
- boost::forward<Visitor>(visitor),
- boost::forward<VertexIndexMap>(vertex_index_map)
- );
- }
- template <typename Graph, typename Visitor>
- void hawick_circuits(BOOST_FWD_REF(Graph) graph,
- BOOST_FWD_REF(Visitor) visitor) {
- hawick_circuits_detail::call_hawick_circuits<
- hawick_circuits_detail::get_all_adjacent_vertices
- >(boost::forward<Graph>(graph), boost::forward<Visitor>(visitor));
- }
- /*!
- * Same as `boost::hawick_circuits`, but duplicate circuits caused by parallel
- * edges will not be considered. Each circuit will be considered only once.
- */
- template <typename Graph, typename Visitor, typename VertexIndexMap>
- void hawick_unique_circuits(BOOST_FWD_REF(Graph) graph,
- BOOST_FWD_REF(Visitor) visitor,
- BOOST_FWD_REF(VertexIndexMap) vertex_index_map) {
- hawick_circuits_detail::call_hawick_circuits<
- hawick_circuits_detail::get_unique_adjacent_vertices
- >(
- boost::forward<Graph>(graph),
- boost::forward<Visitor>(visitor),
- boost::forward<VertexIndexMap>(vertex_index_map)
- );
- }
- template <typename Graph, typename Visitor>
- void hawick_unique_circuits(BOOST_FWD_REF(Graph) graph,
- BOOST_FWD_REF(Visitor) visitor) {
- hawick_circuits_detail::call_hawick_circuits<
- hawick_circuits_detail::get_unique_adjacent_vertices
- >(boost::forward<Graph>(graph), boost::forward<Visitor>(visitor));
- }
- } // end namespace boost
- #endif // !BOOST_GRAPH_HAWICK_CIRCUITS_HPP
|