boost/graph/hawick_circuits.hpp
// 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