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