1 //
2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 //
11 #ifndef BOOST_GRAPH_GRAPH_AS_TREE_HPP
12 #define BOOST_GRAPH_GRAPH_AS_TREE_HPP
13 
14 #include <vector>
15 #include <boost/config.hpp>
16 #include <boost/property_map/property_map.hpp>
17 #include <boost/graph/tree_traits.hpp>
18 #include <boost/graph/graph_traits.hpp>
19 #include <boost/graph/breadth_first_search.hpp>
20 #include <boost/graph/visitors.hpp>
21 
22 namespace boost {
23 
24   template <class Graph, class Node, class ChIt, class Derived>
25   class graph_as_tree_base
26   {
27     typedef Derived Tree;
28   public:
29     typedef Node node_descriptor;
30     typedef ChIt children_iterator;
31 
graph_as_tree_base(Graph & g,Node root)32     graph_as_tree_base(Graph& g, Node root) : _g(g), _root(root) { }
33 
root(const Tree & t)34     friend Node root(const Tree& t) { return t._root; }
35 
36     template <class N>
37     friend std::pair<ChIt,ChIt>
children(N n,const Tree & t)38     children(N n, const Tree& t) { return adjacent_vertices(n, t._g);  }
39 
40     template<class N>
parent(N n,const Tree & t)41     friend Node parent(N n, const Tree& t) {
42       return boost::get(t.parent_pa(), n);
43     }
44 
45     Graph& _g;
46     Node _root;
47   };
48 
49   struct graph_as_tree_tag { };
50 
51   template <class Graph, class ParentMap
52           , class Node
53              = typename graph_traits<Graph>::vertex_descriptor
54           , class ChIt
55               = typename graph_traits<Graph>::adjacency_iterator
56            >
57   class graph_as_tree
58     : public graph_as_tree_base<Graph, Node, ChIt,
59             graph_as_tree<Graph,ParentMap,Node,ChIt> >
60   {
61     typedef graph_as_tree self;
62     typedef graph_as_tree_base<Graph, Node, ChIt, self> super;
63   public:
graph_as_tree(Graph & g,Node root)64     graph_as_tree(Graph& g, Node root) : super(g, root) {  }
65 
graph_as_tree(Graph & g,Node root,ParentMap p)66     graph_as_tree(Graph& g, Node root, ParentMap p) : super(g, root), _p(p) {
67       breadth_first_search(g, root,
68                            visitor(make_bfs_visitor
69                    (record_predecessors(p, boost::on_tree_edge()))));
70     }
parent_pa() const71     ParentMap parent_pa() const { return _p; }
72     typedef graph_as_tree_tag graph_tag; // for property_map
73   protected:
74     ParentMap _p;
75   };
76 
77 
78   namespace detail {
79 
80     struct graph_as_tree_vertex_property_selector {
81       template <typename GraphAsTree, typename Property, typename Tag>
82       struct bind_ {
83         typedef typename GraphAsTree::base_type Graph;
84         typedef property_map<Graph, Tag> PMap;
85         typedef typename PMap::type type;
86         typedef typename PMap::const_type const_type;
87       };
88     };
89 
90     struct graph_as_tree_edge_property_selector {
91       template <typename GraphAsTree, typename Property, typename Tag>
92       struct bind_ {
93         typedef typename GraphAsTree::base_type Graph;
94         typedef property_map<Graph, Tag> PMap;
95         typedef typename PMap::type type;
96         typedef typename PMap::const_type const_type;
97       };
98     };
99 
100   } // namespace detail
101 
102   template <>
103   struct vertex_property_selector<graph_as_tree_tag> {
104     typedef detail::graph_as_tree_vertex_property_selector type;
105   };
106 
107   template <>
108   struct edge_property_selector<graph_as_tree_tag> {
109     typedef detail::graph_as_tree_edge_property_selector type;
110   };
111 
112   template <typename Graph, typename P, typename N, typename C,
113             typename Property>
114   typename property_map<Graph, Property>::type
get(Property p,graph_as_tree<Graph,P,N,C> & g)115   get(Property p, graph_as_tree<Graph,P,N,C>& g)
116   {
117     return get(p, g._g);
118   }
119 
120   template <typename Graph, typename P, typename N, typename C,
121             typename Property>
122   typename property_map<Graph, Property>::const_type
get(Property p,const graph_as_tree<Graph,P,N,C> & g)123   get(Property p, const graph_as_tree<Graph,P,N,C>& g)
124   {
125     const Graph& gref = g._g; // in case GRef is non-const
126     return get(p, gref);
127   }
128 
129   template <typename Graph, typename P, typename N, typename C,
130             typename Property, typename Key>
131   typename property_traits<
132     typename property_map<Graph, Property>::const_type
133   >::value_type
get(Property p,const graph_as_tree<Graph,P,N,C> & g,const Key & k)134   get(Property p, const graph_as_tree<Graph,P,N,C>& g, const Key& k)
135   {
136     return get(p, g._g, k);
137   }
138 
139   template <typename Graph, typename P, typename N, typename C,
140             typename Property, typename Key, typename Value>
141   void
put(Property p,const graph_as_tree<Graph,P,N,C> & g,const Key & k,const Value & val)142   put(Property p, const graph_as_tree<Graph,P,N,C>& g, const Key& k,
143       const Value& val)
144   {
145     put(p, g._g, k, val);
146   }
147 
148 } // namespace boost
149 
150 #endif //  BOOST_GRAPH_GRAPH_AS_TREE_HPP
151