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
25 template < class Graph, class Node, class ChIt, class Derived >
26 class graph_as_tree_base
27 {
28 typedef Derived Tree;
29
30 public:
31 typedef Node node_descriptor;
32 typedef ChIt children_iterator;
33
graph_as_tree_base(Graph & g,Node root)34 graph_as_tree_base(Graph& g, Node root) : _g(g), _root(root) {}
35
root(const Tree & t)36 friend Node root(const Tree& t) { return t._root; }
37
38 template < class N >
children(N n,const Tree & t)39 friend std::pair< ChIt, ChIt > children(N n, const Tree& t)
40 {
41 return adjacent_vertices(n, t._g);
42 }
43
parent(N n,const Tree & t)44 template < class N > friend Node parent(N n, const Tree& t)
45 {
46 return boost::get(t.parent_pa(), n);
47 }
48
49 Graph& _g;
50 Node _root;
51 };
52
53 struct graph_as_tree_tag
54 {
55 };
56
57 template < class Graph, class ParentMap,
58 class Node = typename graph_traits< Graph >::vertex_descriptor,
59 class ChIt = typename graph_traits< Graph >::adjacency_iterator >
60 class graph_as_tree : public graph_as_tree_base< Graph, Node, ChIt,
61 graph_as_tree< Graph, ParentMap, Node, ChIt > >
62 {
63 typedef graph_as_tree self;
64 typedef graph_as_tree_base< Graph, Node, ChIt, self > super;
65
66 public:
graph_as_tree(Graph & g,Node root)67 graph_as_tree(Graph& g, Node root) : super(g, root) {}
68
graph_as_tree(Graph & g,Node root,ParentMap p)69 graph_as_tree(Graph& g, Node root, ParentMap p) : super(g, root), _p(p)
70 {
71 breadth_first_search(g, root,
72 visitor(make_bfs_visitor(
73 record_predecessors(p, boost::on_tree_edge()))));
74 }
parent_pa() const75 ParentMap parent_pa() const { return _p; }
76 typedef graph_as_tree_tag graph_tag; // for property_map
77 protected:
78 ParentMap _p;
79 };
80
81 namespace detail
82 {
83
84 struct graph_as_tree_vertex_property_selector
85 {
86 template < typename GraphAsTree, typename Property, typename Tag >
87 struct bind_
88 {
89 typedef typename GraphAsTree::base_type Graph;
90 typedef property_map< Graph, Tag > PMap;
91 typedef typename PMap::type type;
92 typedef typename PMap::const_type const_type;
93 };
94 };
95
96 struct graph_as_tree_edge_property_selector
97 {
98 template < typename GraphAsTree, typename Property, typename Tag >
99 struct bind_
100 {
101 typedef typename GraphAsTree::base_type Graph;
102 typedef property_map< Graph, Tag > PMap;
103 typedef typename PMap::type type;
104 typedef typename PMap::const_type const_type;
105 };
106 };
107
108 } // namespace detail
109
110 template <> struct vertex_property_selector< graph_as_tree_tag >
111 {
112 typedef detail::graph_as_tree_vertex_property_selector type;
113 };
114
115 template <> struct edge_property_selector< graph_as_tree_tag >
116 {
117 typedef detail::graph_as_tree_edge_property_selector type;
118 };
119
120 template < typename Graph, typename P, typename N, typename C,
121 typename Property >
get(Property p,graph_as_tree<Graph,P,N,C> & g)122 typename property_map< Graph, Property >::type get(
123 Property p, graph_as_tree< Graph, P, N, C >& g)
124 {
125 return get(p, g._g);
126 }
127
128 template < typename Graph, typename P, typename N, typename C,
129 typename Property >
get(Property p,const graph_as_tree<Graph,P,N,C> & g)130 typename property_map< Graph, Property >::const_type get(
131 Property p, const graph_as_tree< Graph, P, N, C >& g)
132 {
133 const Graph& gref = g._g; // in case GRef is non-const
134 return get(p, gref);
135 }
136
137 template < typename Graph, typename P, typename N, typename C,
138 typename Property, typename Key >
139 typename property_traits<
140 typename property_map< Graph, Property >::const_type >::value_type
get(Property p,const graph_as_tree<Graph,P,N,C> & g,const Key & k)141 get(Property p, const graph_as_tree< Graph, P, N, C >& g, const Key& k)
142 {
143 return get(p, g._g, k);
144 }
145
146 template < typename Graph, typename P, typename N, typename C,
147 typename Property, typename Key, typename Value >
put(Property p,const graph_as_tree<Graph,P,N,C> & g,const Key & k,const Value & val)148 void put(Property p, const graph_as_tree< Graph, P, N, C >& g, const Key& k,
149 const Value& val)
150 {
151 put(p, g._g, k, val);
152 }
153
154 } // namespace boost
155
156 #endif // BOOST_GRAPH_GRAPH_AS_TREE_HPP
157