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
22namespace 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

source code of boost/boost/graph/graph_as_tree.hpp