utilmm: utilmm: undirected_graph.hh Source File

00001 //  (C) Copyright Sylvain Joyeux 2006
00002 //
00003 // Original code from reverse_graph adaptor
00004 //  (C) Copyright David Abrahams 2000.
00005 //
00006 // Distributed under the Boost Software License, Version 1.0. (See
00007 // accompanying file LICENSE_1_0.txt or copy at
00008 // http://www.boost.org/LICENSE_1_0.txt)
00009 
00010 #ifndef UNDIRECTED_GRAPH_HPP
00011 #define UNDIRECTED_GRAPH_HPP
00012 
00013 #include <boost/graph/adjacency_iterator.hpp>
00014 #include <boost/graph/properties.hpp>
00015 #include <boost/static_assert.hpp>
00016 #include <utilmm/iterator_sequence.hh>
00017 #include <boost/iterator/transform_iterator.hpp>
00018 
00019 #include <boost/type_traits.hpp>
00020 
00021 namespace utilmm {
00022     struct undirected_graph_tag { };
00023 
00027     template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&>
00028     class undirected_graph {
00029         typedef undirected_graph<BidirectionalGraph, GraphRef> Self;
00030         typedef boost::graph_traits<BidirectionalGraph> Traits;
00031 
00032         BOOST_STATIC_ASSERT(( boost::is_same<boost::bidirectional_tag, typename BidirectionalGraph::directed_category>::value ));
00033 
00034      public:
00035         typedef BidirectionalGraph base_type;
00036 
00037         // Constructor
00038         undirected_graph(GraphRef g) : m_g(g) {}
00039 
00040         // Graph requirements
00041         typedef typename Traits::vertex_descriptor vertex_descriptor;
00042         typedef boost::undirected_tag directed_category;
00043         typedef typename Traits::edge_parallel_category edge_parallel_category;
00044         typedef typename Traits::traversal_category traversal_category;
00045 
00046         // Add a 'reverse' flag to edge descriptors, so that source() and target() know what
00047         // needs to be done
00048         typedef std::pair<typename Traits::edge_descriptor, bool> edge_descriptor;
00049         typedef edge_descriptor (*make_undirected_edge_descriptor)(typename Traits::edge_descriptor);
00050 
00051         // Out edges do not need to be swapped
00052         static edge_descriptor make_out_edge_descriptor(typename Traits::edge_descriptor e)
00053         { return make_pair(e, false); }
00054         class base_out_edge_iterator : 
00055             public boost::transform_iterator<make_undirected_edge_descriptor, typename Traits::out_edge_iterator>
00056         {
00057             typedef boost::transform_iterator<make_undirected_edge_descriptor, typename Traits::out_edge_iterator>
00058                 base_type;
00059 
00060         public:
00061             base_out_edge_iterator() {}
00062             base_out_edge_iterator(typename Traits::out_edge_iterator e)
00063                 : base_type(e, make_out_edge_descriptor) {}
00064         };
00065 
00066         static edge_descriptor make_in_edge_descriptor(typename Traits::edge_descriptor e)
00067         { return make_pair(e, true); }
00068         class base_in_edge_iterator : 
00069             public boost::transform_iterator<make_undirected_edge_descriptor, typename Traits::in_edge_iterator>
00070         {
00071             typedef boost::transform_iterator<make_undirected_edge_descriptor, typename Traits::in_edge_iterator>
00072                 base_type;
00073 
00074         public:
00075             base_in_edge_iterator() {}
00076             base_in_edge_iterator(typename Traits::in_edge_iterator e)
00077                 : base_type(e, make_in_edge_descriptor) {}
00078         };
00079 
00080         // Do not swap plain edge iterators
00081         class edge_iterator : 
00082             public boost::transform_iterator<make_undirected_edge_descriptor, typename Traits::edge_iterator>
00083         {
00084             typedef boost::transform_iterator<make_undirected_edge_descriptor, typename Traits::edge_iterator>
00085                 base_type;
00086         public:
00087             edge_iterator() {}
00088             edge_iterator(typename Traits::edge_iterator e)
00089                 : base_type(e, make_out_edge_descriptor) {}
00090         };
00091 
00092         // IncidenceGraph requirements
00093         typedef typename Traits::degree_size_type degree_size_type;
00094         typedef iterator_sequence
00095             < base_in_edge_iterator
00096             , base_out_edge_iterator
00097             > in_edge_iterator;
00098         typedef in_edge_iterator out_edge_iterator;
00099 
00100         // AdjacencyGraph requirements
00101         typedef iterator_sequence
00102             < typename Traits::adjacency_iterator
00103             , typename BidirectionalGraph::inv_adjacency_iterator
00104             > adjacency_iterator;
00105         typedef adjacency_iterator inv_adjacency_iterator;
00106 
00107         // VertexListGraph requirements
00108         typedef typename Traits::vertex_iterator vertex_iterator;
00109 
00110         // EdgeListGraph requirements
00111         typedef typename Traits::edge_iterator   edge_iterator;
00112         typedef typename Traits::vertices_size_type vertices_size_type;
00113         typedef typename Traits::edges_size_type edges_size_type;
00114 
00115         // More typedefs used by detail::edge_property_map, vertex_property_map
00116         typedef typename BidirectionalGraph::edge_property_type
00117           edge_property_type;
00118         typedef typename BidirectionalGraph::vertex_property_type
00119           vertex_property_type;
00120         typedef undirected_graph_tag graph_tag;
00121 
00122         static vertex_descriptor null_vertex()
00123         { return Traits::null_vertex(); }
00124 
00125         // Bundled properties support
00126         typename boost::graph::detail::bundled_result<BidirectionalGraph,
00127                  edge_descriptor>::type&
00128         operator[](edge_descriptor x)
00129         { return m_g[x.first]; }
00130 
00131         typename boost::graph::detail::bundled_result<BidirectionalGraph,
00132                  edge_descriptor>::type const&
00133         operator[](edge_descriptor x) const
00134         { return m_g[x.first]; }
00135 
00136 
00137 
00138         typename boost::graph::detail::bundled_result<BidirectionalGraph,
00139                  vertex_descriptor>::type&
00140         operator[](vertex_descriptor x)
00141         { return m_g[x]; }
00142 
00143         typename boost::graph::detail::bundled_result<BidirectionalGraph,
00144                  vertex_descriptor>::type const&
00145         operator[](vertex_descriptor x) const
00146         { return m_g[x]; }
00147 
00148 
00149         // would be private, but template friends aren't portable enough.
00150      // private:
00151         GraphRef m_g;
00152     };
00153 
00154     template <class BidirectionalGraph>
00155     inline undirected_graph<BidirectionalGraph>
00156     make_undirected_graph(const BidirectionalGraph& g)
00157     {
00158         return undirected_graph<BidirectionalGraph>(g);
00159     }
00160 
00161     template <class BidirectionalGraph>
00162     inline undirected_graph<BidirectionalGraph, BidirectionalGraph&>
00163     make_undirected_graph(BidirectionalGraph& g)
00164     {
00165         return undirected_graph<BidirectionalGraph, BidirectionalGraph&>(g);
00166     }
00167 
00168     template <class BidirectionalGraph, class GRef>
00169     std::pair<typename undirected_graph<BidirectionalGraph>::vertex_iterator,
00170               typename undirected_graph<BidirectionalGraph>::vertex_iterator>
00171     vertices(const undirected_graph<BidirectionalGraph,GRef>& g)
00172     {
00173         return vertices(g.m_g);
00174     }
00175 
00176     template <class BidirectionalGraph, class GRef>
00177     std::pair<typename undirected_graph<BidirectionalGraph>::edge_iterator,
00178               typename undirected_graph<BidirectionalGraph>::edge_iterator>
00179     edges(const undirected_graph<BidirectionalGraph,GRef>& g)
00180     {
00181         return edges(g.m_g);
00182     }
00183 
00184     template <class BidirectionalGraph, class GRef>
00185     inline std::pair<typename undirected_graph<BidirectionalGraph,GRef>::out_edge_iterator,
00186                      typename undirected_graph<BidirectionalGraph,GRef>::out_edge_iterator>
00187     out_edges(const typename BidirectionalGraph::vertex_descriptor u,
00188               const undirected_graph<BidirectionalGraph,GRef>& g)
00189     {
00190         std::pair<typename BidirectionalGraph::out_edge_iterator,
00191                   typename BidirectionalGraph::out_edge_iterator>
00192                       out_edges = boost::out_edges(u, g.m_g);
00193         std::pair<typename BidirectionalGraph::in_edge_iterator,
00194                   typename BidirectionalGraph::in_edge_iterator> 
00195                       in_edges = boost::in_edges(u, g.m_g);
00196 
00197         typedef typename undirected_graph<BidirectionalGraph,GRef>::out_edge_iterator edge_iterator;
00198         return make_pair(
00199                 edge_iterator(in_edges.first, in_edges.second, out_edges.first, out_edges.first),
00200                 edge_iterator(in_edges.second, in_edges.second, out_edges.second, out_edges.second));
00201     }
00202 
00203     template <class BidirectionalGraph, class GRef>
00204     inline typename BidirectionalGraph::vertices_size_type
00205     num_vertices(const undirected_graph<BidirectionalGraph,GRef>& g)
00206     {
00207         return num_vertices(g.m_g);
00208     }
00209 
00210     template <class BidirectionalGraph, class GRef>
00211     inline typename undirected_graph<BidirectionalGraph>::edges_size_type
00212     num_edges(const undirected_graph<BidirectionalGraph,GRef>& g)
00213     {
00214         return num_edges(g.m_g);
00215     }
00216 
00217     template <class BidirectionalGraph, class GRef>
00218     inline typename BidirectionalGraph::degree_size_type
00219     out_degree(const typename BidirectionalGraph::vertex_descriptor u,
00220                const undirected_graph<BidirectionalGraph,GRef>& g)
00221     {
00222         return in_degree(u, g.m_g) + out_degree(u, g.m_g);
00223     }
00224 
00225     template <class BidirectionalGraph, class GRef>
00226     inline std::pair<typename BidirectionalGraph::edge_descriptor, bool>
00227     edge(const typename BidirectionalGraph::vertex_descriptor u,
00228          const typename BidirectionalGraph::vertex_descriptor v,
00229          const undirected_graph<BidirectionalGraph,GRef>& g)
00230     {
00231         return edge(v, u, g.m_g);
00232     }
00233 
00234     template <class BidirectionalGraph, class GRef>
00235     inline std::pair<typename BidirectionalGraph::out_edge_iterator,
00236         typename BidirectionalGraph::out_edge_iterator>
00237     in_edges(const typename BidirectionalGraph::vertex_descriptor u,
00238              const undirected_graph<BidirectionalGraph,GRef>& g)
00239     { return out_edges(u, g); }
00240 
00241     template <class BidirectionalGraph, class GRef>
00242     inline std::pair<typename undirected_graph<BidirectionalGraph,GRef>::adjacency_iterator,
00243                      typename undirected_graph<BidirectionalGraph,GRef>::adjacency_iterator>
00244     adjacent_vertices(const typename BidirectionalGraph::vertex_descriptor u,
00245                       const undirected_graph<BidirectionalGraph,GRef>& g)
00246     {
00247         std::pair<typename BidirectionalGraph::adjacency_iterator,
00248                   typename BidirectionalGraph::adjacency_iterator> 
00249                       adjacency = boost::adjacent_vertices(u, g.m_g);
00250         std::pair<typename BidirectionalGraph::inv_adjacency_iterator,
00251                   typename BidirectionalGraph::inv_adjacency_iterator>
00252                       inv_adjacency = boost::inv_adjacent_vertices(u, g.m_g);
00253 
00254         typedef typename undirected_graph<BidirectionalGraph,GRef>::adjacency_iterator adjacency_iterator;
00255         return std::make_pair(
00256                 adjacency_iterator(adjacency.first, adjacency.second, inv_adjacency.first, inv_adjacency.first),
00257                 adjacency_iterator(adjacency.second, adjacency.second, inv_adjacency.second, inv_adjacency.second));
00258     }
00259 
00260     template <class BidirectionalGraph, class GRef>
00261     inline typename BidirectionalGraph::degree_size_type
00262     in_degree(const typename BidirectionalGraph::vertex_descriptor u,
00263               const undirected_graph<BidirectionalGraph,GRef>& g)
00264     { return out_degree(u, g); }
00265 
00266     template <class Edge, class BidirectionalGraph, class GRef>
00267     inline typename boost::graph_traits<BidirectionalGraph>::vertex_descriptor
00268     source(const Edge& e, const undirected_graph<BidirectionalGraph,GRef>& g)
00269     {
00270         if (e.second)
00271             return target(e.first, g.m_g);
00272         else
00273             return source(e.first, g.m_g);
00274     }
00275 
00276     template <class Edge, class BidirectionalGraph, class GRef>
00277     inline typename boost::graph_traits<BidirectionalGraph>::vertex_descriptor
00278     target(const Edge& e, const undirected_graph<BidirectionalGraph,GRef>& g)
00279     {
00280         if (e.second)
00281             return source(e.first, g.m_g);
00282         else
00283             return target(e.first, g.m_g);
00284     }
00285 
00286 
00287     namespace detail {
00288 
00289       struct undirected_graph_vertex_property_selector {
00290         template <class UndirectedGraph, class Property, class Tag>
00291         struct bind_ {
00292           typedef typename UndirectedGraph::base_type Graph;
00293           typedef boost::property_map<Graph, Tag> PMap;
00294           typedef typename PMap::type type;
00295           typedef typename PMap::const_type const_type;
00296         };
00297       };
00298 
00299       struct undirected_graph_edge_property_selector {
00300         template <class UndirectedGraph, class Property, class Tag>
00301         struct bind_ {
00302           typedef typename UndirectedGraph::base_type Graph;
00303           typedef boost::property_map<Graph, Tag> PMap;
00304           typedef typename PMap::type type;
00305           typedef typename PMap::const_type const_type;
00306         };
00307       };
00308 
00309     } // namespace detail
00310 
00313     template<typename PropertyMap>
00314     class undirected_property_map 
00315     { 
00316     public:
00317         undirected_property_map(PropertyMap pmap)
00318             : m_map(pmap) {}
00319 
00320         PropertyMap& map() { return m_map; }
00321         PropertyMap const& map() const { return m_map; }
00322 
00323     private:
00324         PropertyMap m_map;
00325     };
00326 
00327     template<typename PropertyMap, typename EdgeDescriptor, typename ValueType>
00328     void put(undirected_property_map<PropertyMap>& map, 
00329             EdgeDescriptor e, ValueType value)
00330     { put(map.map(), e.first, value); }
00331     template<typename PropertyMap, typename EdgeDescriptor>
00332     typename boost::property_traits<PropertyMap>::value_type
00333         get(undirected_property_map<PropertyMap> const& map, 
00334             EdgeDescriptor e)
00335     { return get(map.map(), e.first); }
00336 
00337     template<typename PropertyMap>
00338     undirected_property_map<PropertyMap> make_undirected_edge_map(PropertyMap pmap)
00339     { return undirected_property_map<PropertyMap>(pmap); }
00340 
00341 
00342 } // namespace utilmm
00343 
00344 // Include specialization in the boost namespace
00345 namespace boost {
00346     template<typename PropertyMap>
00347     struct property_traits< utilmm::undirected_property_map<PropertyMap> >
00348         : property_traits<PropertyMap> {};
00349 
00350     template <>
00351     struct vertex_property_selector<utilmm::undirected_graph_tag> {
00352         typedef utilmm::detail::undirected_graph_vertex_property_selector type;
00353     };
00354 
00355     template <>
00356     struct edge_property_selector<utilmm::undirected_graph_tag> {
00357         typedef utilmm::detail::undirected_graph_edge_property_selector type;
00358     };
00359 
00360     namespace detail {
00361         template<typename BidirGraph, typename GRef, typename Property>
00362         struct get_property_map_type { };
00363         template<typename BidirGraph, typename Property>
00364         struct get_property_map_type<BidirGraph, const BidirGraph&, Property>
00365         { typedef typename property_map<BidirGraph, Property>::const_type type; };
00366         template<typename BidirGraph, typename Property>
00367         struct get_property_map_type<BidirGraph, BidirGraph&, Property>
00368         { typedef typename property_map<BidirGraph, Property>::type type; };
00369     }
00370 
00371     template <class BidirGraph, class GRef, class Property>
00372     typename detail::get_property_map_type<BidirGraph, GRef, Property>::type
00373     get(Property p, utilmm::undirected_graph<BidirGraph,GRef>& g)
00374     {
00375       return get(p, g.m_g);
00376     }
00377 
00378     template <class BidirGraph, class GRef, class Property>
00379     typename detail::get_property_map_type<BidirGraph, GRef, Property>::type
00380     get(Property p, const utilmm::undirected_graph<BidirGraph,GRef>& g)
00381     {
00382       return get(p, g.m_g);
00383     }
00384 
00385     template <class BidirectionalGraph, class GRef, class Property, class Key>
00386     typename property_traits<
00387       typename property_map<BidirectionalGraph, Property>::const_type
00388     >::value_type
00389     get(Property p, const utilmm::undirected_graph<BidirectionalGraph,GRef>& g, const Key& k)
00390     {
00391       return get(p, g.m_g, k);
00392     }
00393 
00394     template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>
00395     void
00396     put(Property p, const utilmm::undirected_graph<BidirectionalGraph,GRef>& g, const Key& k,
00397         const Value& val)
00398     {
00399       put(p, g.m_g, k, val);
00400     }
00401 
00402     template<typename BidirectionalGraph, typename GRef, typename Tag,
00403              typename Value>
00404     inline void
00405     set_property(const utilmm::undirected_graph<BidirectionalGraph,GRef>& g, Tag tag, 
00406                  const Value& value)
00407     {
00408       set_property(g.m_g, tag, value);
00409     }
00410 
00411     template<typename BidirectionalGraph, typename GRef, typename Tag>
00412     inline
00413     typename graph_property<BidirectionalGraph, Tag>::type
00414     get_property(const utilmm::undirected_graph<BidirectionalGraph,GRef>& g, Tag tag)
00415     {
00416       return get_property(g.m_g, tag);
00417     }
00418 
00419 } // namespace boost
00420 
00421 #endif