boost/graph/graph_as_tree.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_GRAPH_GRAPH_AS_TREE_HPP
0012 #define BOOST_GRAPH_GRAPH_AS_TREE_HPP
0013
0014 #include <vector>
0015 #include <boost/config.hpp>
0016 #include <boost/property_map/property_map.hpp>
0017 #include <boost/graph/tree_traits.hpp>
0018 #include <boost/graph/graph_traits.hpp>
0019 #include <boost/graph/breadth_first_search.hpp>
0020 #include <boost/graph/visitors.hpp>
0021
0022 namespace boost
0023 {
0024
0025 template < class Graph, class Node, class ChIt, class Derived >
0026 class graph_as_tree_base
0027 {
0028     typedef Derived Tree;
0029
0030 public:
0031     typedef Node node_descriptor;
0032     typedef ChIt children_iterator;
0033
0034     graph_as_tree_base(Graph& g, Node root) : _g(g), _root(root) {}
0035
0036     friend Node root(const Tree& t) { return t._root; }
0037
0038     template < class N >
0039     friend std::pair< ChIt, ChIt > children(N n, const Tree& t)
0040     {
0041         return adjacent_vertices(n, t._g);
0042     }
0043
0044     template < class N > friend Node parent(N n, const Tree& t)
0045     {
0046         return boost::get(t.parent_pa(), n);
0047     }
0048
0049     Graph& _g;
0050     Node _root;
0051 };
0052
0053 struct graph_as_tree_tag
0054 {
0055 };
0056
0057 template < class Graph, class ParentMap,
0058     class Node = typename graph_traits< Graph >::vertex_descriptor,
0059     class ChIt = typename graph_traits< Graph >::adjacency_iterator >
0060 class graph_as_tree : public graph_as_tree_base< Graph, Node, ChIt,
0061                           graph_as_tree< Graph, ParentMap, Node, ChIt > >
0062 {
0063     typedef graph_as_tree self;
0064     typedef graph_as_tree_base< Graph, Node, ChIt, self > super;
0065
0066 public:
0067     graph_as_tree(Graph& g, Node root) : super(g, root) {}
0068
0069     graph_as_tree(Graph& g, Node root, ParentMap p) : super(g, root), _p(p)
0070     {
0071         breadth_first_search(g, root,
0072             visitor(make_bfs_visitor(
0073                 record_predecessors(p, boost::on_tree_edge()))));
0074     }
0075     ParentMap parent_pa() const { return _p; }
0076     typedef graph_as_tree_tag graph_tag; // for property_map
0077 protected:
0078     ParentMap _p;
0079 };
0080
0081 namespace detail
0082 {
0083
0084     struct graph_as_tree_vertex_property_selector
0085     {
0086         template < typename GraphAsTree, typename Property, typename Tag >
0087         struct bind_
0088         {
0089             typedef typename GraphAsTree::base_type Graph;
0090             typedef property_map< Graph, Tag > PMap;
0091             typedef typename PMap::type type;
0092             typedef typename PMap::const_type const_type;
0093         };
0094     };
0095
0096     struct graph_as_tree_edge_property_selector
0097     {
0098         template < typename GraphAsTree, typename Property, typename Tag >
0099         struct bind_
0100         {
0101             typedef typename GraphAsTree::base_type Graph;
0102             typedef property_map< Graph, Tag > PMap;
0103             typedef typename PMap::type type;
0104             typedef typename PMap::const_type const_type;
0105         };
0106     };
0107
0108 } // namespace detail
0109
0110 template <> struct vertex_property_selector< graph_as_tree_tag >
0111 {
0112     typedef detail::graph_as_tree_vertex_property_selector type;
0113 };
0114
0115 template <> struct edge_property_selector< graph_as_tree_tag >
0116 {
0117     typedef detail::graph_as_tree_edge_property_selector type;
0118 };
0119
0120 template < typename Graph, typename P, typename N, typename C,
0121     typename Property >
0122 typename property_map< Graph, Property >::type get(
0123     Property p, graph_as_tree< Graph, P, N, C >& g)
0124 {
0125     return get(p, g._g);
0126 }
0127
0128 template < typename Graph, typename P, typename N, typename C,
0129     typename Property >
0130 typename property_map< Graph, Property >::const_type get(
0131     Property p, const graph_as_tree< Graph, P, N, C >& g)
0132 {
0133     const Graph& gref = g._g; // in case GRef is non-const
0134     return get(p, gref);
0135 }
0136
0137 template < typename Graph, typename P, typename N, typename C,
0138     typename Property, typename Key >
0139 typename property_traits<
0140     typename property_map< Graph, Property >::const_type >::value_type
0141 get(Property p, const graph_as_tree< Graph, P, N, C >& g, const Key& k)
0142 {
0143     return get(p, g._g, k);
0144 }
0145
0146 template < typename Graph, typename P, typename N, typename C,
0147     typename Property, typename Key, typename Value >
0148 void put(Property p, const graph_as_tree< Graph, P, N, C >& g, const Key& k,
0149     const Value& val)
0150 {
0151     put(p, g._g, k, val);
0152 }
0153
0154 } // namespace boost
0155
0156 #endif //  BOOST_GRAPH_GRAPH_AS_TREE_HPP