comparison DEPENDENCIES/generic/include/boost/graph/graph_as_tree.hpp @ 16:2665513ce2d3

Add boost headers

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