Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / graph_as_tree.hpp
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.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 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
54              = typename graph_traits<Graph>::vertex_descriptor
55 #endif
56           , class ChIt
57 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
58               = typename graph_traits<Graph>::adjacency_iterator
59 #endif
60            >
61   class graph_as_tree
62     : public graph_as_tree_base<Graph, Node, ChIt, 
63             graph_as_tree<Graph,ParentMap,Node,ChIt> >
64   {
65     typedef graph_as_tree self;
66     typedef graph_as_tree_base<Graph, Node, ChIt, self> super;
67   public:
68     graph_as_tree(Graph& g, Node root) : super(g, root) {  }
69     
70     graph_as_tree(Graph& g, Node root, ParentMap p) : super(g, root), _p(p) { 
71       breadth_first_search(g, root, 
72                            visitor(make_bfs_visitor
73                    (record_predecessors(p, boost::on_tree_edge()))));
74     }
75     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
82   namespace detail {
83
84     struct graph_as_tree_vertex_property_selector {
85       template <typename GraphAsTree, typename Property, typename Tag>
86       struct bind_ {
87         typedef typename GraphAsTree::base_type Graph;
88         typedef property_map<Graph, Tag> PMap;
89         typedef typename PMap::type type;
90         typedef typename PMap::const_type const_type;
91       };
92     };
93
94     struct graph_as_tree_edge_property_selector {
95       template <typename GraphAsTree, typename Property, typename Tag>
96       struct bind_ {
97         typedef typename GraphAsTree::base_type Graph;
98         typedef property_map<Graph, Tag> PMap;
99         typedef typename PMap::type type;
100         typedef typename PMap::const_type const_type;
101       };
102     };
103
104   } // namespace detail
105
106   template <>
107   struct vertex_property_selector<graph_as_tree_tag> {
108     typedef detail::graph_as_tree_vertex_property_selector type;
109   };
110
111   template <>
112   struct edge_property_selector<graph_as_tree_tag> {
113     typedef detail::graph_as_tree_edge_property_selector type;
114   };
115
116   template <typename Graph, typename P, typename N, typename C, 
117             typename Property>
118   typename property_map<Graph, Property>::type
119   get(Property p, graph_as_tree<Graph,P,N,C>& g)
120   {
121     return get(p, g._g);
122   }
123
124   template <typename Graph, typename P, typename N, typename C, 
125             typename Property>
126   typename property_map<Graph, Property>::const_type
127   get(Property p, const graph_as_tree<Graph,P,N,C>& g)
128   {
129     const Graph& gref = g._g; // in case GRef is non-const
130     return get(p, gref);
131   }
132
133   template <typename Graph, typename P, typename N, typename C, 
134             typename Property, typename Key>
135   typename property_traits<
136     typename property_map<Graph, Property>::const_type
137   >::value_type
138   get(Property p, const graph_as_tree<Graph,P,N,C>& g, const Key& k)
139   {
140     return get(p, g._g, k);
141   }
142
143   template <typename Graph, typename P, typename N, typename C, 
144             typename Property, typename Key, typename Value>
145   void
146   put(Property p, const graph_as_tree<Graph,P,N,C>& g, const Key& k,
147       const Value& val)
148   {
149     put(p, g._g, k, val);
150   }
151
152 } // namespace boost
153
154 #endif //  BOOST_GRAPH_GRAPH_AS_TREE_HPP