]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |