Douglas Gregor wrote: [Benoit wrote:]
Can you think of another way ? Is there already such an adapter somewhere (i have unsuccessfully tried to find one...) ? In case it didn't exist, would anyone else be interested to have one ?
I think this is the right way to handle the problem you describe. I do not know of anyone who has implemented such an adapter, but it would be a welcome addition to the BGL. If you do write this adapter, please consider contributing it to the BGL!
There is an adapter for reversing a graph. Based on this, I have written an adapter for making a bidirectional graph bidirected, that is, having a graph were each edge occurs twice, once for its original direction and once for the reverse direction. I have tested it in BFS implementations, but I'm sure it's full of bugs ;-) I don't remember if I already posted it, so it's attached. CC: to Benoit, as his and Douglas' posts were from quite long ago ... I don't think an undirected graph adapter should be so much trouble. // //======================================================================= // Copyright 2007 University of Karlsruhe // Author: Jens Mueller // // Based on boost/graph/reverse_graph.hpp // (C) Copyright David Abrahams 2000. // Distributed under 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 bidirected_graph_HPP_893441 #define bidirected_graph_HPP_893441 #include <boost/type_traits/is_convertible.hpp> #include <boost/graph/properties.hpp> namespace boost { /** This is a tag to distinguish the bidirected graph adapter adapter from other graph implementations. It is used for tag dispatching purposes. */ struct bidirected_graph_tag {}; namespace detail { /** This template provides the edge iterator for the class (through the bind_ member template). \param isEdgeList Is the graph an EdgeListGraph? If not, no edge iterator is defined. */ template<bool isEdgeList> struct choose_bidi_edge_iter {}; template<> struct choose_bidi_edge_iter<true> { template<class Self> struct bind_ { class edge_iterator : public boost::iterator_facade<edge_iterator, typename Self::edge_descriptor const, boost::forward_traversal_tag, typename Self::edge_descriptor const> { public: edge_iterator(typename boost::graph_traits<typename Self::base_type>::edge_iterator iter, bool reverse_direction) : m_iter(iter), m_reverse_direction(reverse_direction) {} edge_iterator() {} private: typename Self::edge_descriptor dereference() const { return std::make_pair(*m_iter, m_reverse_direction); } bool equal(const edge_iterator& other) const { return (m_reverse_direction == other.m_reverse_direction) && (m_iter == other.m_iter); } void increment() { if (m_reverse_direction==false) m_reverse_direction = true; else { ++m_iter; m_reverse_direction=false; } } typename boost::graph_traits<typename Self::base_type>::edge_iterator m_iter; bool m_reverse_direction; friend class boost::iterator_core_access; }; typedef edge_iterator type; }; }; template<> struct choose_bidi_edge_iter<false> { template<class Self> struct bind_ { typedef void type; }; }; /** The out edge iterator class for the bidirected graph adapter \param Self the bidirected_graph for which this iterator class is used. */ template<class Self> class bidirected_out_edge_iterator : public boost::iterator_facade<bidirected_out_edge_iterator<Self>, typename Self::edge_descriptor const, boost::forward_traversal_tag, typename Self::edge_descriptor const> { public: /** Constructs the iterator. \param cur_out The current out edge the iterator points at \param cur_in The current in edge the iterator points at \param in_begin The first in edge - used to switch to after the last out edge \param out_end The end iterator for out edges - switch to in edges after it \param out_p Is the iterator currently iterating over out edges? */ bidirected_out_edge_iterator( typename boost::graph_traits<typename Self::base_type>::out_edge_iterator cur_out, typename boost::graph_traits<typename Self::base_type>::in_edge_iterator cur_in, typename boost::graph_traits<typename Self::base_type>::in_edge_iterator in_begin, typename boost::graph_traits<typename Self::base_type>::out_edge_iterator out_end, bool out_p) : m_cur_out(cur_out), m_cur_in(cur_in), m_in_begin(in_begin), m_out_end(out_end), m_out_p(out_p) { if (m_out_p) { if (m_cur_out==m_out_end) { m_out_p = false; m_cur_in = m_in_begin; } } } // constructor /** Copy constructor */ bidirected_out_edge_iterator(const bidirected_out_edge_iterator<Self> & other) : m_cur_out(other.m_cur_out), m_cur_in(other.m_cur_in), m_in_begin(other.m_in_begin), m_out_end(other.m_out_end), m_out_p(other.m_out_p) { } /** Default constructor. Does nothing useful, but is required. */ bidirected_out_edge_iterator() {} private: /** Dereferences the iterator \return edge descriptor at which the iterator is pointing */ typename Self::edge_descriptor dereference() const { if (m_out_p) return std::make_pair(*m_cur_out, false); else return std::make_pair(*m_cur_in, true); } /** Compares the iterator to another iterator. \param other The other iterator */ bool equal (const bidirected_out_edge_iterator& other) const { if (m_out_p != other.m_out_p) { return false; } if (m_out_p) { return m_cur_out==other.m_cur_out; } else { return m_cur_in==other.m_cur_in; } } /** Increments the iterator. */ void increment() { if (m_out_p) { ++m_cur_out; if (m_cur_out==m_out_end) { m_out_p = false; m_cur_in = m_in_begin; } } else { ++m_cur_in; } } typename boost::graph_traits<typename Self::base_type>::out_edge_iterator m_cur_out; /// current out edge typename boost::graph_traits<typename Self::base_type>::in_edge_iterator m_cur_in; /// current in edge typename boost::graph_traits<typename Self::base_type>::in_edge_iterator m_in_begin; /// first in edge typename boost::graph_traits<typename Self::base_type>::out_edge_iterator m_out_end; /// end iterator for out edges bool m_out_p; /// true, if the iterator is currently pointing at an out edge friend class boost::iterator_core_access; }; // class bidirected_out_edge_iterator /** The in edge iterator class for the bidirected graph adapter. Everything is the same as for the out edge iterator. \param Self the bidirected_graph for which this iterator class is used. */ template<class Self> class bidirected_in_edge_iterator : public boost::iterator_facade<bidirected_in_edge_iterator<Self>, typename Self::edge_descriptor const, boost::forward_traversal_tag, typename Self::edge_descriptor const> { public: bidirected_in_edge_iterator( typename boost::graph_traits<typename Self::base_type>::out_edge_iterator cur_out, typename boost::graph_traits<typename Self::base_type>::in_edge_iterator cur_in, typename boost::graph_traits<typename Self::base_type>::in_edge_iterator in_begin, typename boost::graph_traits<typename Self::base_type>::out_edge_iterator out_end, bool out_p) : m_cur_out(cur_out), m_cur_in(cur_in), m_in_begin(in_begin), m_out_end(out_end), m_out_p(out_p) { if (m_out_p) { if (m_cur_out==m_out_end) { m_out_p = false; m_cur_in = m_in_begin; } } } private: typename Self::edge_descriptor dereference() const { if (m_out_p) return std::make_pair(*m_cur_out, true); // reverse from oe iter else return std::make_pair(*m_cur_in, false); // reverse from oe iter } bool equal (const bidirected_in_edge_iterator& other) const { if (m_out_p != other.m_out_p) return false; if (m_out_p) return m_cur_out==other.m_cur_out; else return m_cur_in==other.m_cur_in; } void increment() { if (m_out_p) { ++m_cur_out; if (m_cur_out==m_out_end) { m_out_p = false; m_cur_in = m_in_begin; } } else { ++m_cur_in; } } typename boost::graph_traits<typename Self::base_type>::out_edge_iterator m_cur_out; typename boost::graph_traits<typename Self::base_type>::in_edge_iterator m_cur_in; typename boost::graph_traits<typename Self::base_type>::in_edge_iterator m_in_begin; typename boost::graph_traits<typename Self::base_type>::out_edge_iterator m_out_end; bool m_out_p; friend class boost::iterator_core_access; }; }; // namespace detail namespace detail { template<class Self> // Self: the corresponding bidirected_graph class bidi_graph_vertex_descriptor { public: // hmpf ... typename boost::graph_traits<typename Self::base_type>::vertex_descriptor m_vertex; public: bidi_graph_vertex_descriptor (const typename boost::graph_traits<typename Self::base_type>::vertex_descriptor v) : m_vertex(v) {} bidi_graph_vertex_descriptor() {} operator typename boost::graph_traits<typename Self::base_type>::vertex_descriptor () const { return m_vertex; } }; // class bidi_graph_vertex_descriptor template<class Self, class PMap> typename boost::property_traits<PMap>::value_type get(PMap p, bidi_graph_vertex_descriptor<Self> u) { return get(p, u.m_vertex); } template<class Self> // Self: the corresponding bidirected_graph class bidi_graph_vertex_iterator : public boost::iterator_facade<bidi_graph_vertex_iterator<Self>, typename Self::vertex_descriptor const, boost::forward_traversal_tag, typename Self::vertex_descriptor const> { public: bidi_graph_vertex_iterator (typename boost::graph_traits<typename Self::base_type>::vertex_iterator iter) : m_iter(iter) {} bidi_graph_vertex_iterator() {} private: typename Self::vertex_descriptor dereference() const { return *m_iter; } bool equal(const bidi_graph_vertex_iterator& other) const { return (m_iter == other.m_iter); } void increment() { ++m_iter; } typename boost::graph_traits<typename Self::base_type>::vertex_iterator m_iter; friend class boost::iterator_core_access; }; // class bidi_graph_vertex_iterator }; //namespace detail /** Adapter class to make a bidirectional graph (edges accessible in both directions) bidirected, as required e.g. by BFS algorithms. \param BidirectionalGraph Type of the underlying bidirectional graph. \param GraphRef Type of the reference to the underlying graph. */ template<class BidirectionalGraph, class GraphRef = /* const */ BidirectionalGraph&> class bidirected_graph { typedef bidirected_graph<BidirectionalGraph, GraphRef> Self; typedef boost::graph_traits<BidirectionalGraph> Traits; public: typedef BidirectionalGraph base_type; /** Constructs a bidirected_graph from a given base graph. \param g a reference to the base graph */ bidirected_graph(GraphRef g) : m_g(g) {} // Graph requirements //typedef typename Traits::vertex_descriptor vertex_descriptor; typedef detail::bidi_graph_vertex_descriptor<Self> vertex_descriptor; typedef std::pair<typename Traits::edge_descriptor, bool> edge_descriptor; // bool: original direction = true, reversed = false; typedef boost::directed_tag directed_category; typedef boost::allow_parallel_edge_tag edge_parallel_category; typedef typename Traits::traversal_category traversal_category; /// \todo maybe something better is needed here ... // IncidenceGraph requirements typedef typename detail::bidirected_out_edge_iterator<Self> out_edge_iterator; typedef typename Traits::degree_size_type degree_size_type; // BidirectionalGraph requirements typedef typename detail::bidirected_in_edge_iterator<Self> in_edge_iterator; // AdjacencyGraph requirements typedef void adjacency_iterator; //VertexListGraph requirements //typedef typename Traits::vertex_iterator vertex_iterator; typedef detail::bidi_graph_vertex_iterator<Self> vertex_iterator; typedef typename Traits::vertices_size_type vertices_size_type; // EdgeListGraph requirements enum { is_edge_list = boost::is_convertible<traversal_category, edge_list_graph_tag>::value }; typedef detail::choose_bidi_edge_iter<is_edge_list> ChooseEdgeIter; typedef typename ChooseEdgeIter:: template bind_<Self>::type edge_iterator; typedef typename Traits::edges_size_type edges_size_type; // properties ... typedef bidirected_graph_tag graph_tag; // Bundled properties support - TODO static vertex_descriptor null_vertex() { return Traits::null_vertex(); } // private: GraphRef m_g; }; /* template<typename Graph, typename GraphRef> struct boost::vertex_bundle_type<bidirected_graph<Graph, GraphRef> > : boost::vertex_bundle_type<Graph> { }; template<typename Graph, typename GraphRef> struct boost::edge_bundle_type<bidirected_graph<Graph, GraphRef> > : boost::edge_bundle_type<Graph> { }; */ /** Helper function to create a bidirected_graph. \param BidirectionalGraph Type of the underlying graph. Normally gets inferred. \param g The underlying graph. \return A bidirected graph adapter for the given graph. */ template<class BidirectionalGraph> inline bidirected_graph<BidirectionalGraph> make_bidirected_graph(const BidirectionalGraph& g) { return bidirected_graph<BidirectionalGraph>(g); } template<class BidirectionalGraph> inline bidirected_graph<BidirectionalGraph, BidirectionalGraph&> make_bidirected_graph(BidirectionalGraph& g) { return bidirected_graph<BidirectionalGraph, BidirectionalGraph&>(g); } /** Get the vertices of the bidirected graph \param g The bidirected graph \return a pair of iterators for the vertices of the graph. */ template<class BidirectionalGraph, class GRef> std::pair<typename bidirected_graph<BidirectionalGraph, GRef>::vertex_iterator, typename bidirected_graph<BidirectionalGraph, GRef>::vertex_iterator> vertices(const bidirected_graph<BidirectionalGraph,GRef>& g) { return vertices(g.m_g); } /** Get the edges of the bidirected graph \param g The bidirected graph \return a pair of iterators for the edges of the graph. Each edge of the underlying graph occurs twice, once for the original and once for the reversed direction. */ template <class BidirectionalGraph, class GRef> std::pair<typename bidirected_graph<BidirectionalGraph, GRef>::edge_iterator, typename bidirected_graph<BidirectionalGraph, GRef>::edge_iterator> edges(const bidirected_graph<BidirectionalGraph,GRef>& g) { return std::make_pair( typename bidirected_graph<BidirectionalGraph,GRef>::edge_iterator( edges(g.m_g).first, false), typename bidirected_graph<BidirectionalGraph,GRef>::edge_iterator( edges(g.m_g).second, false)); } /** Get the out edges of a specific vertex \param g The bidirected graph \param u The vertex \return a pair of iterators for the out edges of u. These contain the out edges in their original direction and the in edges in reversed direction. */ template <class BidirectionalGraph, class GRef> std::pair<typename bidirected_graph<BidirectionalGraph>::out_edge_iterator, typename bidirected_graph<BidirectionalGraph>::out_edge_iterator> // out_edges(const typename BidirectionalGraph::vertex_descriptor u, // const bidirected_graph<BidirectionalGraph,GRef>& g) out_edges(const detail::bidi_graph_vertex_descriptor< boost::bidirected_graph<BidirectionalGraph, GRef> > u, const bidirected_graph<BidirectionalGraph,GRef>& g) { return std::make_pair( typename bidirected_graph<BidirectionalGraph,GRef>::out_edge_iterator( out_edges(u.m_vertex, g.m_g).first, in_edges(u.m_vertex, g.m_g).first, // dummy in_edges(u.m_vertex, g.m_g).first, out_edges(u.m_vertex, g.m_g).second, true), typename bidirected_graph<BidirectionalGraph,GRef>::out_edge_iterator( out_edges(u.m_vertex, g.m_g).second, // dummy in_edges(u.m_vertex, g.m_g).second, // cur_in == end in_edges(u.m_vertex, g.m_g).first, // not needed ... out_edges(u.m_vertex, g.m_g).second, // not needed ... false) ); } /** Get the in edges of a specific vertex \param g The bidirected graph \param u The vertex \return a pair of iterators for the out edges of u. These contain the in edges in their original direction and the out edges in reversed direction. */ template <class BidirectionalGraph, class GRef> std::pair<typename bidirected_graph<BidirectionalGraph>::in_edge_iterator, typename bidirected_graph<BidirectionalGraph>::in_edge_iterator> in_edges(const typename BidirectionalGraph::vertex_descriptor u, const bidirected_graph<BidirectionalGraph,GRef>& g) { return std::make_pair( typename bidirected_graph<BidirectionalGraph,GRef>::in_edge_iterator( out_edges(u, g.m_g).first, in_edges(u, g.m_g).first, // dummy in_edges(u, g.m_g).first, out_edges(u, g.m_g).second, true), typename bidirected_graph<BidirectionalGraph,GRef>::in_edge_iterator( out_edges(u, g.m_g).second, // dummy in_edges(u, g.m_g).second, // cur_in == end in_edges(u, g.m_g).first, // not needed ... out_edges(u, g.m_g).second, // not needed ... false) ); } template <class BidirectionalGraph, class GRef> inline typename bidirected_graph<BidirectionalGraph, GRef>::vertices_size_type num_vertices(const bidirected_graph<BidirectionalGraph,GRef>& g) { return num_vertices(g.m_g); } /** Get the number of edges. This is twice the number of edges of the underlying graph. */ template <class BidirectionalGraph, class GRef> inline typename bidirected_graph<BidirectionalGraph, GRef>::edges_size_type num_edges(const bidirected_graph<BidirectionalGraph, GRef>& g) { return 2*num_edges(g.m_g); } template <class BidirectionalGraph, class GRef> inline typename bidirected_graph<BidirectionalGraph, GRef>::degree_size_type out_degree(const typename bidirected_graph<BidirectionalGraph, GRef>::vertex_descriptor u, const bidirected_graph<BidirectionalGraph, GRef>& g) { return in_degree(u, g.m_g)+out_degree(u, g.m_g); } template <class BidirectionalGraph, class GRef> inline typename bidirected_graph<BidirectionalGraph, GRef>::vertex_descriptor source(const typename bidirected_graph<BidirectionalGraph, GRef>::edge_descriptor e, const bidirected_graph<BidirectionalGraph, GRef>& g) { return e.second ? target(e.first, g.m_g) : source(e.first, g.m_g); } template <class BidirectionalGraph, class GRef> inline typename bidirected_graph<BidirectionalGraph, GRef>::vertex_descriptor target(const typename bidirected_graph<BidirectionalGraph, GRef>::edge_descriptor e, const bidirected_graph<BidirectionalGraph, GRef>& g) { return e.second ? source(e.first, g.m_g) : target(e.first, g.m_g); } template <class BidirectionalGraph, class GRef> inline std::pair<typename bidirected_graph<BidirectionalGraph, GRef>::edge_descriptor, bool> edge(const typename BidirectionalGraph::vertex_descriptor u, const typename BidirectionalGraph::vertex_descriptor v, const bidirected_graph<BidirectionalGraph,GRef>& g) { std::pair<typename BidirectionalGraph::edge_descriptor, bool> normal = edge(u, v, g.m_g); if (normal.second) return std::make_pair(std::make_pair(normal.first, true), true); std::pair<typename BidirectionalGraph::edge_descriptor, bool> reverse = edge(v, u, g.m_g); // if (reverse.second) return std::make_pair(std::make_pair(reverse.first, false), reverse.second); /* in case no edge is found, just return *anything* with false as second */ } namespace detail { template<class BidiGraph> class bidi_graph_edge_index_map { typedef typename BidiGraph::base_type Graph; typedef typename property_map<Graph, edge_index_t>::type PMap; PMap pm_; public: typedef typename BidiGraph::edge_descriptor key_type; typedef typename property_traits<PMap>::value_type value_type; typedef typename property_traits<PMap>::reference reference; typedef boost::readable_property_map_tag category; value_type get_(key_type key) { value_type original_value = get(pm_, key.first); return original_value + (key.second ? 0 : 1); } bidi_graph_edge_index_map(PMap pm) : pm_(pm) {} }; // class template<class BidiGraph> typename bidi_graph_edge_index_map<BidiGraph>::value_type get(bidi_graph_edge_index_map<BidiGraph> pm, typename bidi_graph_edge_index_map<BidiGraph>::key_type key) { return pm.get_(key); } template<class BidiGraph, class Tag> class bidi_graph_edge_property_map { typedef typename BidiGraph::base_type Graph; typedef typename property_map<Graph, Tag>::type PMap; PMap pm_; public: typedef typename BidiGraph::edge_descriptor key_type; typedef typename property_traits<PMap>::value_type value_type; typedef typename property_traits<PMap>::reference reference; typedef boost::readable_property_map_tag category; value_type get_(key_type key) { return get(pm_, key.first); } bidi_graph_edge_property_map(PMap pm) : pm_(pm) {} }; // class template<class BidiGraph, class Tag> typename bidi_graph_edge_property_map<BidiGraph, Tag>::value_type get(bidi_graph_edge_property_map<BidiGraph, Tag> pm, typename bidi_graph_edge_property_map<BidiGraph, Tag>::key_type key) { return pm.get_(key); } struct bidirected_graph_edge_property_selector { template <class BidiGraph, class PropertyTag> struct bind_ { typedef typename BidiGraph::base_type Graph; typedef bidi_graph_edge_property_map<BidiGraph, PropertyTag> PMap; typedef PMap type; typedef PMap const_type; }; template <class BidiGraph> struct bind_<BidiGraph, edge_index_t> { typedef typename BidiGraph::base_type Graph; typedef bidi_graph_edge_index_map<BidiGraph> PMap; typedef PMap type; typedef PMap const_type; }; }; // struct bidirected_graph_edge_property_selector struct bidirected_graph_vertex_property_selector { template <class BidiGraph, class PropertyTag> struct bind_ { typedef typename BidiGraph::base_type Graph; typedef property_map<Graph, PropertyTag> PMap; typedef typename PMap::type type; typedef typename PMap::const_type const_type; }; }; template <class Graph, class PropertyTag> struct bidi_vertex_property_map { typedef bidirected_graph_vertex_property_selector Selector; typedef Selector::template bind_<Graph, PropertyTag> Bind; typedef typename Bind::type type; typedef typename Bind::const_type const_type; }; template <class Graph, class PropertyTag> struct bidi_edge_property_map { typedef bidirected_graph_edge_property_selector Selector; typedef Selector::template bind_<Graph, PropertyTag> Bind; typedef typename Bind::type type; typedef typename Bind::const_type const_type; }; struct bidi_choose_vertex_pm { template <class Graph, class Property> // Graph is an bidirected_graph! struct bind_ { typedef bidi_vertex_property_map<Graph, Property> type; }; }; struct bidi_choose_edge_pm { template <class Graph, class Property> // Graph is an bidirected_graph! struct bind_ { typedef bidi_edge_property_map<Graph, Property> type; }; }; template<class Kind> struct bidi_pm_kind_selector { }; template <> struct bidi_pm_kind_selector<vertex_property_tag> { typedef bidi_choose_vertex_pm type; }; template <> struct bidi_pm_kind_selector<edge_property_tag> { typedef bidi_choose_edge_pm type; }; } // namespace detail template <class BidirectionalGraph, class GRef, class Property> struct property_map<bidirected_graph<BidirectionalGraph, GRef>, Property>{ private: typedef bidirected_graph<BidirectionalGraph, GRef> Graph; typedef typename property_kind<Property>::type Kind; typedef typename detail::bidi_pm_kind_selector<Kind>::type Selector; typedef typename Selector::template bind_<Graph, Property> Bind; typedef typename Bind::type Map; public: typedef typename Map::type type; typedef typename Map::const_type const_type; }; namespace detail { template <class BidirGraph, class GRef, class Property> typename property_map<BidirGraph, Property>::type bidirected_graph_get_pmap_dispatch(Property p, const bidirected_graph<BidirGraph,GRef>& g, vertex_property_tag) { return get(p, g.m_g); } template <class BidirGraph, class GRef, class Property> typename property_map<BidirGraph, Property>::type bidirected_graph_get_pmap_dispatch(Property p, const bidirected_graph<BidirGraph,GRef>& g, edge_property_tag) { return bidi_graph_edge_property_map<BidirGraph, Property> (get(p, g.m_g)); } } // namespace detail template <class BidirGraph, class GRef, class Property> typename property_map<BidirGraph, Property>::type get(Property p, const bidirected_graph<BidirGraph,GRef>& g) { return detail::bidirected_graph_get_pmap_dispatch(p, g, typename property_kind<Property>::type()); } template <class BidirGraph, class GRef> typename property_map<bidirected_graph<BidirGraph,GRef>, edge_index_t>::type get(edge_index_t p, const bidirected_graph<BidirGraph,GRef>& g) { return detail::bidi_graph_edge_index_map<bidirected_graph<BidirGraph,GRef> >(get(p, g.m_g)); } } // namespace boost #endif