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 graph_as_tree_base(Graph & g,Node root)32 graph_as_tree_base(Graph& g, Node root) : _g(g), _root(root) { } 33 root(const Tree & t)34 friend Node root(const Tree& t) { return t._root; } 35 36 template <class N> 37 friend std::pair<ChIt,ChIt> children(N n,const Tree & t)38 children(N n, const Tree& t) { return adjacent_vertices(n, t._g); } 39 40 template<class N> parent(N n,const Tree & t)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: graph_as_tree(Graph & g,Node root)64 graph_as_tree(Graph& g, Node root) : super(g, root) { } 65 graph_as_tree(Graph & g,Node root,ParentMap p)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 } parent_pa() const71 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 get(Property p,graph_as_tree<Graph,P,N,C> & g)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 get(Property p,const graph_as_tree<Graph,P,N,C> & g)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 get(Property p,const graph_as_tree<Graph,P,N,C> & g,const Key & k)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 put(Property p,const graph_as_tree<Graph,P,N,C> & g,const Key & k,const Value & val)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