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 | |
32 | graph_as_tree_base(Graph& g, Node root) : _g(g), _root(root) { } |
33 | |
34 | friend Node root(const Tree& t) { return t._root; } |
35 | |
36 | template <class N> |
37 | friend std::pair<ChIt,ChIt> |
38 | children(N n, const Tree& t) { return adjacent_vertices(n, t._g); } |
39 | |
40 | template<class N> |
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: |
64 | graph_as_tree(Graph& g, Node root) : super(g, root) { } |
65 | |
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 | } |
71 | 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 |
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 |
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 |
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 |
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 | |