//

//=======================================================================

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