http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/include/boost/graph/graph_as_tree.hpp

// //======================================================================= // 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.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