| // |
| //======================================================================= |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| // |
| #ifndef BOOST_GRAPH_GRAPH_AS_TREE_HPP |
| #define BOOST_GRAPH_GRAPH_AS_TREE_HPP |
| |
| #include <vector> |
| #include <boost/config.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <boost/graph/tree_traits.hpp> |
| #include <boost/graph/graph_traits.hpp> |
| #include <boost/graph/breadth_first_search.hpp> |
| #include <boost/graph/visitors.hpp> |
| |
| namespace boost { |
| |
| template <class Graph, class Node, class ChIt, class Derived> |
| class graph_as_tree_base |
| { |
| typedef Derived Tree; |
| public: |
| typedef Node node_descriptor; |
| typedef ChIt children_iterator; |
| |
| graph_as_tree_base(Graph& g, Node root) : _g(g), _root(root) { } |
| |
| friend Node root(const Tree& t) { return t._root; } |
| |
| template <class N> |
| friend std::pair<ChIt,ChIt> |
| children(N n, const Tree& t) { return adjacent_vertices(n, t._g); } |
| |
| template<class N> |
| friend Node parent(N n, const Tree& t) { |
| return boost::get(t.parent_pa(), n); |
| } |
| |
| Graph& _g; |
| Node _root; |
| }; |
| |
| struct graph_as_tree_tag { }; |
| |
| template <class Graph, class ParentMap |
| , class Node |
| #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION |
| = typename graph_traits<Graph>::vertex_descriptor |
| #endif |
| , class ChIt |
| #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION |
| = typename graph_traits<Graph>::adjacency_iterator |
| #endif |
| > |
| class graph_as_tree |
| : public graph_as_tree_base<Graph, Node, ChIt, |
| graph_as_tree<Graph,ParentMap,Node,ChIt> > |
| { |
| typedef graph_as_tree self; |
| typedef graph_as_tree_base<Graph, Node, ChIt, self> super; |
| public: |
| graph_as_tree(Graph& g, Node root) : super(g, root) { } |
| |
| graph_as_tree(Graph& g, Node root, ParentMap p) : super(g, root), _p(p) { |
| breadth_first_search(g, root, |
| visitor(make_bfs_visitor |
| (record_predecessors(p, boost::on_tree_edge())))); |
| } |
| ParentMap parent_pa() const { return _p; } |
| typedef graph_as_tree_tag graph_tag; // for property_map |
| protected: |
| ParentMap _p; |
| }; |
| |
| |
| namespace detail { |
| |
| struct graph_as_tree_vertex_property_selector { |
| template <typename GraphAsTree, typename Property, typename Tag> |
| struct bind_ { |
| typedef typename GraphAsTree::base_type Graph; |
| typedef property_map<Graph, Tag> PMap; |
| typedef typename PMap::type type; |
| typedef typename PMap::const_type const_type; |
| }; |
| }; |
| |
| struct graph_as_tree_edge_property_selector { |
| template <typename GraphAsTree, typename Property, typename Tag> |
| struct bind_ { |
| typedef typename GraphAsTree::base_type Graph; |
| typedef property_map<Graph, Tag> PMap; |
| typedef typename PMap::type type; |
| typedef typename PMap::const_type const_type; |
| }; |
| }; |
| |
| } // namespace detail |
| |
| template <> |
| struct vertex_property_selector<graph_as_tree_tag> { |
| typedef detail::graph_as_tree_vertex_property_selector type; |
| }; |
| |
| template <> |
| struct edge_property_selector<graph_as_tree_tag> { |
| typedef detail::graph_as_tree_edge_property_selector type; |
| }; |
| |
| template <typename Graph, typename P, typename N, typename C, |
| typename Property> |
| typename property_map<Graph, Property>::type |
| get(Property p, graph_as_tree<Graph,P,N,C>& g) |
| { |
| return get(p, g._g); |
| } |
| |
| template <typename Graph, typename P, typename N, typename C, |
| typename Property> |
| typename property_map<Graph, Property>::const_type |
| get(Property p, const graph_as_tree<Graph,P,N,C>& g) |
| { |
| const Graph& gref = g._g; // in case GRef is non-const |
| return get(p, gref); |
| } |
| |
| template <typename Graph, typename P, typename N, typename C, |
| typename Property, typename Key> |
| typename property_traits< |
| typename property_map<Graph, Property>::const_type |
| >::value_type |
| get(Property p, const graph_as_tree<Graph,P,N,C>& g, const Key& k) |
| { |
| return get(p, g._g, k); |
| } |
| |
| template <typename Graph, typename P, typename N, typename C, |
| typename Property, typename Key, typename Value> |
| void |
| put(Property p, const graph_as_tree<Graph,P,N,C>& g, const Key& k, |
| const Value& val) |
| { |
| put(p, g._g, k, val); |
| } |
| |
| } // namespace boost |
| |
| #endif // BOOST_GRAPH_GRAPH_AS_TREE_HPP |