source: NonGTP/Boost/boost/graph/graph_as_tree.hpp @ 857

Revision 857, 4.7 KB checked in by igarcia, 19 years ago (diff)
Line 
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.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
22namespace 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   
32    graph_as_tree_base(Graph& g, Node root) : _g(g), _root(root) { }
33   
34    friend Node root(const Tree& t) { return t._root; }
35   
36    template <class N>
37    friend std::pair<ChIt,ChIt>
38    children(N n, const Tree& t) { return adjacent_vertices(n, t._g);  }
39   
40    template<class N>
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#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
54             = typename graph_traits<Graph>::vertex_descriptor
55#endif
56          , class ChIt
57#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
58              = typename graph_traits<Graph>::adjacency_iterator
59#endif
60           >
61  class graph_as_tree
62    : public graph_as_tree_base<Graph, Node, ChIt,
63            graph_as_tree<Graph,ParentMap,Node,ChIt> >
64  {
65    typedef graph_as_tree self;
66    typedef graph_as_tree_base<Graph, Node, ChIt, self> super;
67  public:
68    graph_as_tree(Graph& g, Node root) : super(g, root) {  }
69   
70    graph_as_tree(Graph& g, Node root, ParentMap p) : super(g, root), _p(p) {
71      breadth_first_search(g, root,
72                           visitor(make_bfs_visitor
73                   (record_predecessors(p, boost::on_tree_edge()))));
74    }
75    ParentMap parent_pa() const { return _p; }
76    typedef graph_as_tree_tag graph_tag; // for property_map
77  protected:
78    ParentMap _p;
79  };
80 
81
82  namespace detail {
83
84    struct graph_as_tree_vertex_property_selector {
85      template <typename GraphAsTree, typename Property, typename Tag>
86      struct bind_ {
87        typedef typename GraphAsTree::base_type Graph;
88        typedef property_map<Graph, Tag> PMap;
89        typedef typename PMap::type type;
90        typedef typename PMap::const_type const_type;
91      };
92    };
93
94    struct graph_as_tree_edge_property_selector {
95      template <typename GraphAsTree, typename Property, typename Tag>
96      struct bind_ {
97        typedef typename GraphAsTree::base_type Graph;
98        typedef property_map<Graph, Tag> PMap;
99        typedef typename PMap::type type;
100        typedef typename PMap::const_type const_type;
101      };
102    };
103
104  } // namespace detail
105
106  template <>
107  struct vertex_property_selector<graph_as_tree_tag> {
108    typedef detail::graph_as_tree_vertex_property_selector type;
109  };
110
111  template <>
112  struct edge_property_selector<graph_as_tree_tag> {
113    typedef detail::graph_as_tree_edge_property_selector type;
114  };
115
116  template <typename Graph, typename P, typename N, typename C,
117            typename Property>
118  typename property_map<Graph, Property>::type
119  get(Property p, graph_as_tree<Graph,P,N,C>& g)
120  {
121    return get(p, g._g);
122  }
123
124  template <typename Graph, typename P, typename N, typename C,
125            typename Property>
126  typename property_map<Graph, Property>::const_type
127  get(Property p, const graph_as_tree<Graph,P,N,C>& g)
128  {
129    const Graph& gref = g._g; // in case GRef is non-const
130    return get(p, gref);
131  }
132
133  template <typename Graph, typename P, typename N, typename C,
134            typename Property, typename Key>
135  typename property_traits<
136    typename property_map<Graph, Property>::const_type
137  >::value_type
138  get(Property p, const graph_as_tree<Graph,P,N,C>& g, const Key& k)
139  {
140    return get(p, g._g, k);
141  }
142
143  template <typename Graph, typename P, typename N, typename C,
144            typename Property, typename Key, typename Value>
145  void
146  put(Property p, const graph_as_tree<Graph,P,N,C>& g, const Key& k,
147      const Value& val)
148  {
149    put(p, g._g, k, val);
150  }
151
152} // namespace boost
153
154#endif //  BOOST_GRAPH_GRAPH_AS_TREE_HPP
Note: See TracBrowser for help on using the repository browser.