code:
//=======================================================================
// 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_NAMED_FUNCTION_PARAMS_HPP
#define BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP

#include <functional>
#include <vector>
#include <boost/limits.hpp>
#include <boost/ref.hpp>
#include <boost/utility/result_of.hpp>
#include <boost/preprocessor.hpp>
#include <boost/parameter/name.hpp>
#include <boost/parameter/binding.hpp>
#include <boost/type_traits.hpp>
#include <boost/mpl/not.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/detail/d_ary_heap.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/shared_array_property_map.hpp>

namespace boost {

  struct parity_map_t { };
  struct vertex_assignment_map_t { };
  struct distance_compare_t { };
  struct distance_combine_t { };
  struct distance_inf_t { };
  struct distance_zero_t { };
  struct buffer_param_t { };
  struct edge_copy_t { };
  struct vertex_copy_t { };
  struct vertex_isomorphism_t { };
  struct vertex_invariant_t { };
  struct vertex_invariant1_t { };
  struct vertex_invariant2_t { };
  struct edge_compare_t { };
  struct vertex_max_invariant_t { };
  struct orig_to_copy_t { };
  struct root_vertex_t { };
  struct polling_t { };
  struct lookahead_t { };
  struct in_parallel_t { };
  struct attractive_force_t { };
  struct repulsive_force_t { };
  struct force_pairs_t { };
  struct cooling_t { };
  struct vertex_displacement_t { };
  struct iterations_t { };
  struct diameter_range_t { };
  struct learning_constant_range_t { };
  struct vertices_equivalent_t { };
  struct edges_equivalent_t { };
  struct index_in_heap_map_t { };
  struct max_priority_queue_t { };

#define BOOST_BGL_DECLARE_NAMED_PARAMS \
    BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight) \
    BOOST_BGL_ONE_PARAM_CREF(weight_map2, edge_weight2) \
    BOOST_BGL_ONE_PARAM_CREF(distance_map, vertex_distance) \
    BOOST_BGL_ONE_PARAM_CREF(distance_map2, vertex_distance2) \
    BOOST_BGL_ONE_PARAM_CREF(predecessor_map, vertex_predecessor) \
    BOOST_BGL_ONE_PARAM_CREF(rank_map, vertex_rank) \
    BOOST_BGL_ONE_PARAM_CREF(root_map, vertex_root) \
    BOOST_BGL_ONE_PARAM_CREF(root_vertex, root_vertex) \
    BOOST_BGL_ONE_PARAM_CREF(edge_centrality_map, edge_centrality) \
    BOOST_BGL_ONE_PARAM_CREF(centrality_map, vertex_centrality) \
    BOOST_BGL_ONE_PARAM_CREF(parity_map, parity_map) \
    BOOST_BGL_ONE_PARAM_CREF(color_map, vertex_color) \
    BOOST_BGL_ONE_PARAM_CREF(edge_color_map, edge_color) \
    BOOST_BGL_ONE_PARAM_CREF(capacity_map, edge_capacity) \
    BOOST_BGL_ONE_PARAM_CREF(residual_capacity_map, edge_residual_capacity) \
    BOOST_BGL_ONE_PARAM_CREF(reverse_edge_map, edge_reverse) \
    BOOST_BGL_ONE_PARAM_CREF(discover_time_map, vertex_discover_time) \
    BOOST_BGL_ONE_PARAM_CREF(lowpoint_map, vertex_lowpoint) \
    BOOST_BGL_ONE_PARAM_CREF(vertex_index_map, vertex_index) \
    BOOST_BGL_ONE_PARAM_CREF(vertex_index1_map, vertex_index1) \
    BOOST_BGL_ONE_PARAM_CREF(vertex_index2_map, vertex_index2) \
    BOOST_BGL_ONE_PARAM_CREF(vertex_assignment_map, vertex_assignment_map) \
    BOOST_BGL_ONE_PARAM_CREF(visitor, graph_visitor) \
    BOOST_BGL_ONE_PARAM_CREF(distance_compare, distance_compare) \
    BOOST_BGL_ONE_PARAM_CREF(distance_combine, distance_combine) \
    BOOST_BGL_ONE_PARAM_CREF(distance_inf, distance_inf) \
    BOOST_BGL_ONE_PARAM_CREF(distance_zero, distance_zero) \
    BOOST_BGL_ONE_PARAM_CREF(edge_copy, edge_copy) \
    BOOST_BGL_ONE_PARAM_CREF(vertex_copy, vertex_copy) \
    BOOST_BGL_ONE_PARAM_REF(buffer, buffer_param) \
    BOOST_BGL_ONE_PARAM_CREF(orig_to_copy, orig_to_copy) \
    BOOST_BGL_ONE_PARAM_CREF(isomorphism_map, vertex_isomorphism) \
    BOOST_BGL_ONE_PARAM_CREF(vertex_invariant, vertex_invariant) \
    BOOST_BGL_ONE_PARAM_CREF(vertex_invariant1, vertex_invariant1) \
    BOOST_BGL_ONE_PARAM_CREF(vertex_invariant2, vertex_invariant2) \
    BOOST_BGL_ONE_PARAM_CREF(vertex_max_invariant, vertex_max_invariant) \
    BOOST_BGL_ONE_PARAM_CREF(polling, polling) \
    BOOST_BGL_ONE_PARAM_CREF(lookahead, lookahead) \
    BOOST_BGL_ONE_PARAM_CREF(in_parallel, in_parallel) \
    BOOST_BGL_ONE_PARAM_CREF(displacement_map, vertex_displacement) \
    BOOST_BGL_ONE_PARAM_CREF(attractive_force, attractive_force) \
    BOOST_BGL_ONE_PARAM_CREF(repulsive_force, repulsive_force) \
    BOOST_BGL_ONE_PARAM_CREF(force_pairs, force_pairs) \
    BOOST_BGL_ONE_PARAM_CREF(cooling, cooling) \
    BOOST_BGL_ONE_PARAM_CREF(iterations, iterations) \
    BOOST_BGL_ONE_PARAM_CREF(diameter_range, diameter_range) \
    BOOST_BGL_ONE_PARAM_CREF(learning_constant_range, learning_constant_range) \
    BOOST_BGL_ONE_PARAM_CREF(vertices_equivalent, vertices_equivalent) \
    BOOST_BGL_ONE_PARAM_CREF(edges_equivalent, edges_equivalent) \
    BOOST_BGL_ONE_PARAM_CREF(index_in_heap_map, index_in_heap_map) \
    BOOST_BGL_ONE_PARAM_REF(max_priority_queue, max_priority_queue)

  template <typename T, typename Tag, typename Base = no_property>
  struct bgl_named_params
  {
    typedef bgl_named_params self;
    typedef Base next_type;
    typedef Tag tag_type;
    typedef T value_type;
    bgl_named_params(T v = T()) : m_value(v) { }
    bgl_named_params(T v, const Base& b) : m_value(v), m_base(b) { }
    T m_value;
    Base m_base;

#define BOOST_BGL_ONE_PARAM_REF(name, key) \
    template <typename PType> \
    bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t), self> \
    name(PType& p) const { \
      typedef bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t), self> Params; \
      return Params(boost::ref(p), *this); \
    } \

#define BOOST_BGL_ONE_PARAM_CREF(name, key) \
    template <typename PType> \
    bgl_named_params<PType, BOOST_PP_CAT(key, _t), self> \
    name(const PType& p) const { \
      typedef bgl_named_params<PType, BOOST_PP_CAT(key, _t), self> Params; \
      return Params(p, *this); \
    } \

BOOST_BGL_DECLARE_NAMED_PARAMS

#undef BOOST_BGL_ONE_PARAM_REF
#undef BOOST_BGL_ONE_PARAM_CREF

    // Duplicate
    template <typename PType>
    bgl_named_params<PType, vertex_color_t, self>
    vertex_color_map(const PType& p) const {return this->color_map(p);}
  };

#define BOOST_BGL_ONE_PARAM_REF(name, key) \
    template <typename PType> \
    bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t)> \
    name(PType& p) { \
      typedef bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t)> Params; \
      return Params(boost::ref(p)); \
    } \

#define BOOST_BGL_ONE_PARAM_CREF(name, key) \
    template <typename PType> \
    bgl_named_params<PType, BOOST_PP_CAT(key, _t)> \
    name(const PType& p) { \
      typedef bgl_named_params<PType, BOOST_PP_CAT(key, _t)> Params; \
      return Params(p); \
    } \

BOOST_BGL_DECLARE_NAMED_PARAMS

#undef BOOST_BGL_ONE_PARAM_REF
#undef BOOST_BGL_ONE_PARAM_CREF

  // Duplicate
  template <typename PType>
  bgl_named_params<PType, vertex_color_t>
  vertex_color_map(const PType& p) {return color_map(p);}

  namespace detail {
    struct unused_tag_type {};
  }
  typedef bgl_named_params<char, detail::unused_tag_type> no_named_parameters;

  //===========================================================================
  // Functions for extracting parameters from bgl_named_params

  template <typename Tag, typename Args>
  struct lookup_named_param {};

  template <typename T, typename Tag, typename Base>
  struct lookup_named_param<Tag, bgl_named_params<T, Tag, Base> > {
    typedef T type;
    static const T& get(const bgl_named_params<T, Tag, Base>& p) {
      return p.m_value;
    }
  };

  template <typename Tag1, typename T, typename Tag, typename Base>
  struct lookup_named_param<Tag1, bgl_named_params<T, Tag, Base> > {
    typedef typename lookup_named_param<Tag1, Base>::type type;
    static const type& get(const bgl_named_params<T, Tag, Base>& p) {
      return lookup_named_param<Tag1, Base>::get(p.m_base);
    }
  };

  template <typename Tag, typename Args, typename Def>
  struct lookup_named_param_def {
    typedef Def type;
    static const Def& get(const Args&, const Def& def) {return def;}
  };

  template <typename T, typename Tag, typename Base, typename Def>
  struct lookup_named_param_def<Tag, bgl_named_params<T, Tag, Base>, Def> {
    typedef T type;
    static const type& get(const bgl_named_params<T, Tag, Base>& p, const Def&) {
      return p.m_value;
    }
  };

  template <typename Tag1, typename T, typename Tag, typename Base, typename Def>
  struct lookup_named_param_def<Tag1, bgl_named_params<T, Tag, Base>, Def> {
    typedef typename lookup_named_param_def<Tag1, Base, Def>::type type;
    static const type& get(const bgl_named_params<T, Tag, Base>& p, const Def& def) {
      return lookup_named_param_def<Tag1, Base, Def>::get(p.m_base, def);
    }
  };

  struct param_not_found {};

  template <typename Tag, typename Args>
  struct get_param_type:
    lookup_named_param_def<Tag, Args, param_not_found> {};

  template <class Tag, typename Args>
  inline
  const typename lookup_named_param_def<Tag, Args, param_not_found>::type&
  get_param(const Args& p, Tag) {
    return lookup_named_param_def<Tag, Args, param_not_found>::get(p, param_not_found());
  }

  template <class P, class Default>
  const P& choose_param(const P& param, const Default&) {
    return param;
  }

  template <class Default>
  Default choose_param(const param_not_found&, const Default& d) {
    return d;
  }

  template <typename T>
  inline bool is_default_param(const T&) { return false; }

  inline bool is_default_param(const param_not_found&)
    { return true; }

  namespace detail {
    template <typename T>
    struct const_type_as_type {typedef typename T::const_type type;};
  } // namespace detail

  // Use this function instead of choose_param() when you want
  // to avoid requiring get(tag, g) when it is not used.
  namespace detail {
    template <typename GraphIsConst, typename Graph, typename Param, typename Tag>
    struct choose_impl_result:
      boost::mpl::eval_if<
        boost::is_same<Param, param_not_found>,
        boost::mpl::eval_if<
          GraphIsConst,
          detail::const_type_as_type<property_map<Graph, Tag> >,
          property_map<Graph, Tag> >,
        boost::mpl::identity<Param> > {};

    // Parameters of f are (GraphIsConst, Graph, Param, Tag)
    template <bool Found> struct choose_impl_helper;

    template <> struct choose_impl_helper<false> {
      template <typename Param, typename Graph, typename PropertyTag>
      static typename property_map<typename boost::remove_const<Graph>::type, PropertyTag>::const_type
      f(boost::mpl::true_, const Graph& g, const Param&, PropertyTag tag) {
        return get(tag, g);
      }

      template <typename Param, typename Graph, typename PropertyTag>
      static typename property_map<typename boost::remove_const<Graph>::type, PropertyTag>::type
      f(boost::mpl::false_, Graph& g, const Param&, PropertyTag tag) {
        return get(tag, g);
      }
    };

    template <> struct choose_impl_helper<true> {
      template <typename GraphIsConst, typename Param, typename Graph, typename PropertyTag>
      static Param f(GraphIsConst, const Graph&, const Param& p, PropertyTag) {
        return p;
      }
    };
  }

  template <typename Param, typename Graph, typename PropertyTag>
  typename detail::choose_impl_result<boost::mpl::true_, Graph, Param, PropertyTag>::type
  choose_const_pmap(const Param& p, const Graph& g, PropertyTag tag)
  {
    return detail::choose_impl_helper<!boost::is_same<Param, param_not_found>::value>
             ::f(boost::mpl::true_(), g, p, tag);
  }

  template <typename Param, typename Graph, typename PropertyTag>
  typename detail::choose_impl_result<boost::mpl::false_, Graph, Param, PropertyTag>::type
  choose_pmap(const Param& p, Graph& g, PropertyTag tag)
  {
    return detail::choose_impl_helper<!boost::is_same<Param, param_not_found>::value>
             ::f(boost::mpl::false_(), g, p, tag);
  }

  namespace detail {

    // used in the max-flow algorithms
    template <class Graph, class P, class T, class R>
    struct edge_capacity_value
    {
      typedef bgl_named_params<P, T, R> Params;
      typedef typename detail::choose_impl_result<boost::mpl::true_, Graph, typename get_param_type<edge_capacity_t, Params>::type, edge_capacity_t>::type CapacityEdgeMap;
      typedef typename property_traits<CapacityEdgeMap>::value_type type;
    };
    // used in the max-flow algorithms
    template <class Graph, class P, class T, class R>
    struct edge_weight_value
    {
      typedef bgl_named_params<P, T, R> Params;
      typedef typename detail::choose_impl_result<boost::mpl::true_, Graph, typename get_param_type<edge_weight_t, Params>::type, edge_weight_t>::type WeightMap;
      typedef typename property_traits<WeightMap>::value_type type;
    };

  }

  // Declare all new tags
  namespace graph {
    namespace keywords {
#define BOOST_BGL_ONE_PARAM_REF(name, key) BOOST_PARAMETER_NAME(name)
#define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_PARAMETER_NAME(name)
      BOOST_BGL_DECLARE_NAMED_PARAMS
#undef BOOST_BGL_ONE_PARAM_REF
#undef BOOST_BGL_ONE_PARAM_CREF
    }
  }

  namespace detail {
    template <typename Tag> struct convert_one_keyword {};
#define BOOST_BGL_ONE_PARAM_REF(name, key) \
    template <> \
    struct convert_one_keyword<BOOST_PP_CAT(key, _t)> { \
      typedef boost::graph::keywords::tag::name type; \
    };
#define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_BGL_ONE_PARAM_REF(name, key)
    BOOST_BGL_DECLARE_NAMED_PARAMS
#undef BOOST_BGL_ONE_PARAM_REF
#undef BOOST_BGL_ONE_PARAM_CREF

    template <typename T>
    struct convert_bgl_params_to_boost_parameter {
      typedef typename convert_one_keyword<typename T::tag_type>::type new_kw;
      typedef boost::parameter::aux::tagged_argument<new_kw, const typename T::value_type> tagged_arg_type;
      typedef convert_bgl_params_to_boost_parameter<typename T::next_type> rest_conv;
      typedef boost::parameter::aux::arg_list<tagged_arg_type, typename rest_conv::type> type;
      static type conv(const T& x) {
        return type(tagged_arg_type(x.m_value), rest_conv::conv(x.m_base));
      }
    };

    template <typename P, typename R>
    struct convert_bgl_params_to_boost_parameter<bgl_named_params<P, int, R> > {
      typedef convert_bgl_params_to_boost_parameter<R> rest_conv;
      typedef typename rest_conv::type type;
      static type conv(const bgl_named_params<P, int, R>& x) {
        return rest_conv::conv(x.m_base);
      }
    };

    template <>
    struct convert_bgl_params_to_boost_parameter<boost::no_property> {
      typedef boost::parameter::aux::empty_arg_list type;
      static type conv(const boost::no_property&) {return type();}
    };

    template <>
    struct convert_bgl_params_to_boost_parameter<boost::no_named_parameters> {
      typedef boost::parameter::aux::empty_arg_list type;
      static type conv(const boost::no_named_parameters&) {return type();}
    };

    struct bgl_parameter_not_found_type {};

    template <typename ArgPack, typename KeywordType>
    struct parameter_exists : boost::mpl::not_<boost::is_same<typename boost::parameter::binding<ArgPack, KeywordType, bgl_parameter_not_found_type>::type, bgl_parameter_not_found_type> > {};
  }

#define BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_type, old_var) \
  typedef typename boost::detail::convert_bgl_params_to_boost_parameter<old_type>::type arg_pack_type; \
  arg_pack_type arg_pack = boost::detail::convert_bgl_params_to_boost_parameter<old_type>::conv(old_var);

  namespace detail {

    template <typename ArgType, typename Prop, typename Graph, bool Exists>
    struct override_const_property_t {
      typedef typename boost::remove_const<ArgType>::type result_type;
      result_type operator()(const Graph&, const ArgType& a) const {return a;}
    };

    template <typename ArgType, typename Prop, typename Graph>
    struct override_const_property_t<ArgType, Prop, Graph, false> {
      typedef typename boost::property_map<Graph, Prop>::const_type result_type;
      result_type operator()(const Graph& g, const ArgType&) const {return get(Prop(), g);}
    };

    template <typename ArgPack, typename Tag, typename Prop, typename Graph>
    struct override_const_property_result {
      typedef
        typename override_const_property_t<
                   typename boost::parameter::value_type<ArgPack, Tag, int>::type,
                   Prop,
                   Graph,
                   boost::detail::parameter_exists<ArgPack, Tag>::value
                 >::result_type
        type;
    };

    template <typename ArgPack, typename Tag, typename Prop, typename Graph>
    typename override_const_property_result<ArgPack, Tag, Prop, Graph>::type
    override_const_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) {
    return override_const_property_t<
             typename boost::parameter::value_type<ArgPack, Tag, int>::type,
             Prop,
             Graph,
             boost::detail::parameter_exists<ArgPack, Tag>::value
           >()(g, ap[t | 0]);
    }

    template <typename ArgType, typename Prop, typename Graph, bool Exists>
    struct override_property_t {
      typedef ArgType result_type;
      result_type operator()(const Graph&, const typename boost::add_reference<ArgType>::type a) const {return a;}
    };

    template <typename ArgType, typename Prop, typename Graph>
    struct override_property_t<ArgType, Prop, Graph, false> {
      typedef typename boost::property_map<Graph, Prop>::type result_type;
      result_type operator()(const Graph& g, const ArgType&) const {return get(Prop(), g);}
    };

    template <typename ArgPack, typename Tag, typename Prop, typename Graph>
    struct override_property_result {
      typedef
        typename override_property_t<
                   typename boost::parameter::value_type<ArgPack, Tag, int>::type,
                   Prop,
                   Graph,
                   boost::detail::parameter_exists<ArgPack, Tag>::value
                 >::result_type
        type;
    };

    template <typename ArgPack, typename Tag, typename Prop, typename Graph>
    typename override_property_result<ArgPack, Tag, Prop, Graph>::type
    override_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) {
    return override_property_t<
             typename boost::parameter::value_type<ArgPack, Tag, int>::type,
             Prop,
             Graph,
             boost::detail::parameter_exists<ArgPack, Tag>::value
           >()(g, ap[t | 0]);
    }

    template <typename F> struct make_arg_pack_type;
    template <> struct make_arg_pack_type<void()> {typedef boost::parameter::aux::empty_arg_list type;};
    template <typename K, typename A>
    struct make_arg_pack_type<void(K, A)> {
      typedef boost::parameter::aux::tagged_argument<K, A> type;
    };

#define BOOST_GRAPH_OPENING_PART_OF_PAIR(z, i, n) boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, BOOST_PP_SUB(n, i)),  BOOST_PP_CAT(Arg, BOOST_PP_SUB(n, i))>,
#define BOOST_GRAPH_MAKE_PAIR_PARAM(z, i, _) const boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, i), BOOST_PP_CAT(Arg, i)>& BOOST_PP_CAT(kw, i)

#define BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(z, i, _) \
    template <BOOST_PP_ENUM_PARAMS(i, typename Keyword), BOOST_PP_ENUM_PARAMS(i, typename Arg)> \
    struct make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(i, Keyword), BOOST_PP_ENUM_PARAMS(i, Arg))> { \
      typedef \
        BOOST_PP_REPEAT(i, BOOST_GRAPH_OPENING_PART_OF_PAIR, BOOST_PP_DEC(i)) boost::parameter::aux::empty_arg_list BOOST_PP_REPEAT(i, > BOOST_PP_TUPLE_EAT(3), ~) \
        type; \
    };
    BOOST_PP_REPEAT_FROM_TO(2, 11, BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION, ~)
#undef BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION

#define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(name, nfixed, nnamed_max) \
  /* Entry point for conversion from BGL-style named parameters */ \
  template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_COMMA_IF(nfixed) typename ArgPack> \
  typename boost::result_of< \
             detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>(BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) const ArgPack&) \
           >::type \
  BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) BOOST_PP_COMMA_IF(nfixed) const ArgPack& arg_pack) { \
    return detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>()(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \
  } \
  /* Individual functions taking Boost.Parameter-style keyword arguments */ \
  BOOST_PP_REPEAT(BOOST_PP_INC(nnamed_max), BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE, (name)(nfixed))

#define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE(z, nnamed, seq) \
  BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, BOOST_PP_SEQ_ELEM(0, seq), BOOST_PP_SEQ_ELEM(1, seq))

#define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, name, nfixed) \
  template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Keyword) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Arg)> \
  typename boost::result_of< \
             detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)> \
               (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \
                const typename boost::detail::make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(nnamed, Keyword) BOOST_PP_COMMA_IF(nnamed) BOOST_PP_ENUM_PARAMS(nnamed, Arg))>::type&) \
           >::type \
  name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) \
       BOOST_PP_ENUM_TRAILING(nnamed, BOOST_GRAPH_MAKE_PAIR_PARAM, ~)) { \
    return detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>() \
             (BOOST_PP_ENUM_PARAMS(nfixed, param), \
              (boost::parameter::aux::empty_arg_list() BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, kw))); \
  }

#define BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(name, nfixed) \
  template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_COMMA_IF(nfixed) class P, class T, class R> \
  typename boost::result_of< \
    ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \
      (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \
       const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<P, T, R> >::type &) \
    >::type \
  name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) BOOST_PP_COMMA_IF(nfixed) const boost::bgl_named_params<P, T, R>& old_style_params) { \
    typedef boost::bgl_named_params<P, T, R> old_style_params_type; \
    BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_style_params_type, old_style_params) \
    return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \
  } \
  \
  BOOST_PP_EXPR_IF(nfixed, template <) BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_EXPR_IF(nfixed, >) \
  BOOST_PP_EXPR_IF(nfixed, typename) boost::result_of< \
    ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \
      (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) const boost::parameter::aux::empty_arg_list &) \
    >::type \
  name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param)) { \
    BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(boost::no_named_parameters, boost::no_named_parameters()) \
    return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \
  }

  }

  namespace detail {

    template <bool Exists, typename Graph, typename ArgPack, typename Value, typename PM>
    struct map_maker_helper {
      typedef PM map_type;
      static PM make_map(const Graph&, Value, const PM& pm, const ArgPack&) {
        return pm;
      }
    };

    template <typename Graph, typename ArgPack, typename Value, typename PM>
    struct map_maker_helper<false, Graph, ArgPack, Value, PM> {
      typedef typename boost::remove_const<
        typename override_const_property_t<
          typename boost::parameter::value_type<
            ArgPack, boost::graph::keywords::tag::vertex_index_map, int>::type,
          boost::vertex_index_t,
          Graph,
          boost::detail::parameter_exists<
            ArgPack, boost::graph::keywords::tag::vertex_index_map>::value
        >::result_type>::type vi_map_type;
      typedef
        boost::shared_array_property_map<Value, vi_map_type>
        map_type;
      static map_type make_map(const Graph& g,
                               Value v,
                               const PM&,
                               const ArgPack& ap) {
        return make_shared_array_property_map(
                 num_vertices(g),
                 v,
                 override_const_property(
                   ap,
                   boost::graph::keywords::_vertex_index_map,
                   g, vertex_index));
      }
    };

    template <typename Graph, typename ArgPack, typename MapTag, typename ValueType>
    struct map_maker {
      BOOST_STATIC_CONSTANT(
        bool,
        has_map =
          (parameter_exists<ArgPack, MapTag>
           ::value));
      typedef map_maker_helper<has_map, Graph, ArgPack, ValueType,
                               typename boost::remove_const<
                                 typename boost::parameter::value_type<
                                            ArgPack,
                                            MapTag,
                                            int
                                          >::type
                                        >::type> helper;
      typedef typename helper::map_type map_type;
      static map_type make_map(const Graph& g, const ArgPack& ap, ValueType default_value) {
        return helper::make_map(g, default_value, ap[::boost::parameter::keyword<MapTag>::instance | 0], ap);
      }
    };

    template <typename MapTag, typename ValueType = void>
    class make_property_map_from_arg_pack_gen {
      ValueType default_value;

      public:
      make_property_map_from_arg_pack_gen(ValueType default_value)
        : default_value(default_value) {}

      template <typename Graph, typename ArgPack>
      typename map_maker<Graph, ArgPack, MapTag, ValueType>::map_type
      operator()(const Graph& g, const ArgPack& ap) const {
        return map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(g, ap, default_value);
      }
    };

    template <typename MapTag>
    class make_property_map_from_arg_pack_gen<MapTag, void> {
      public:
      template <typename ValueType, typename Graph, typename ArgPack>
      typename map_maker<Graph, ArgPack, MapTag, ValueType>::map_type
      operator()(const Graph& g, const ArgPack& ap, ValueType default_value) const {
        return map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(g, ap, default_value);
      }
    };

    static const
      make_property_map_from_arg_pack_gen<
        boost::graph::keywords::tag::color_map,
        default_color_type>
      make_color_map_from_arg_pack(white_color);

    template <bool Exists, class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q>
    struct priority_queue_maker_helper {
      typedef Q priority_queue_type;

      static priority_queue_type
      make_queue(const Graph&, const ArgPack&, KeyT, const Q& q) {
        return q;
      }
    };

    template <class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q>
    struct priority_queue_maker_helper<false, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare, Q> {
      typedef typename std::vector<ValueT>::size_type default_index_in_heap_type;
      typedef typename map_maker<Graph, ArgPack, IndexInHeapMapTag, default_index_in_heap_type>::helper::map_type index_in_heap_map;
      typedef boost::d_ary_heap_indirect<ValueT, 4, index_in_heap_map, typename map_maker<Graph, ArgPack, KeyMapTag, KeyT>::helper::map_type, Compare> priority_queue_type;

      static priority_queue_type
      make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey, const Q&) {
        return priority_queue_type(
            map_maker<Graph, ArgPack, KeyMapTag, KeyT>::make_map(g, ap, defaultKey),
            map_maker<Graph, ArgPack, IndexInHeapMapTag, default_index_in_heap_type>::make_map(g, ap, typename boost::property_traits<index_in_heap_map>::value_type(-1))
          );
      }
    };

    template <class Graph, class ArgPack, class KeyT, class ValueT, class PriorityQueueTag, class KeyMapTag, class IndexInHeapMapTag, class Compare>
    struct priority_queue_maker {
      BOOST_STATIC_CONSTANT(
        bool,
        g_hasQ =
          (parameter_exists<ArgPack, PriorityQueueTag>
           ::value));
      typedef boost::reference_wrapper<int> int_refw;
      typedef typename boost::parameter::value_type<
                         ArgPack,
                         PriorityQueueTag,
                         int_refw
                       >::type
        param_value_type_wrapper;
      typedef typename param_value_type_wrapper::type
        param_value_type;
      typedef typename boost::remove_const<param_value_type>::type param_value_type_no_const;
      typedef priority_queue_maker_helper<g_hasQ, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare,
                                          param_value_type_no_const> helper;
      typedef typename helper::priority_queue_type priority_queue_type;

      static priority_queue_type make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey) {
        return helper::make_queue(g, ap, defaultKey, ap[::boost::parameter::keyword<PriorityQueueTag>::instance | 0]);
      }
    };

    template <class PriorityQueueTag, class KeyT, class ValueT, class Compare = std::less<KeyT>, class KeyMapTag = boost::graph::keywords::tag::distance_map, class IndexInHeapMapTag = boost::graph::keywords::tag::index_in_heap_map>
    struct make_priority_queue_from_arg_pack_gen {
      KeyT defaultKey;

      make_priority_queue_from_arg_pack_gen(KeyT defaultKey_) : defaultKey(defaultKey_) { }

      template <class F>
      struct result {
        typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg1_type>::type>::type graph_type;
        typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg2_type>::type>::type arg_pack_type;
        typedef typename priority_queue_maker<graph_type, arg_pack_type, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type type;
      };

      template <class Graph, class ArgPack>
      typename priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type
      operator()(const Graph& g, const ArgPack& ap) const {
        return priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::make_queue(g, ap, defaultKey);
      }
    };

    template <typename G>
    typename boost::graph_traits<G>::vertex_descriptor
    get_null_vertex(const G&) {return boost::graph_traits<G>::null_vertex();}

    template <typename G>
    typename boost::graph_traits<G>::vertex_descriptor
    get_default_starting_vertex(const G& g) {
      std::pair<typename boost::graph_traits<G>::vertex_iterator, typename boost::graph_traits<G>::vertex_iterator> iters = vertices(g);
      return (iters.first == iters.second) ? boost::graph_traits<G>::null_vertex() : *iters.first;
    }

    template <typename G>
    struct get_default_starting_vertex_t {
      typedef typename boost::graph_traits<G>::vertex_descriptor result_type;
      const G& g;
      get_default_starting_vertex_t(const G& g): g(g) {}
      result_type operator()() const {return get_default_starting_vertex(g);}
    };

    // Wrapper to avoid instantiating numeric_limits when users provide distance_inf value manually
    template <typename T>
    struct get_max {
      T operator()() const {
        return (std::numeric_limits<T>::max)();
      }
      typedef T result_type;
    };

  } // namespace detail

} // namespace boost

#undef BOOST_BGL_DECLARE_NAMED_PARAMS

#endif // BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP


code:
// Copyright (C) 2007 Douglas Gregor

// Use, modification and distribution is subject to 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)

// Provides support for named vertices in graphs, allowing one to more
// easily associate unique external names (URLs, city names, employee
// ID numbers, etc.) with the vertices of a graph.
#ifndef BOOST_GRAPH_NAMED_GRAPH_HPP
#define BOOST_GRAPH_NAMED_GRAPH_HPP

#include <boost/config.hpp>
#include <boost/static_assert.hpp>
#include <boost/functional/hash.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/optional.hpp>
#include <boost/pending/property.hpp> // for boost::lookup_one_property
#include <boost/pending/container_traits.hpp>
#include <boost/throw_exception.hpp>
#include <boost/tuple/tuple.hpp> // for boost::make_tuple
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/is_base_of.hpp>
#include <boost/type_traits/remove_cv.hpp>
#include <boost/type_traits/remove_reference.hpp>
#include <boost/utility/enable_if.hpp>
#include <functional> // for std::equal_to
#include <stdexcept> // for std::runtime_error
#include <utility> // for std::pair

namespace boost { namespace graph {

/*******************************************************************
 * User-customized traits                                          *
 *******************************************************************/

/**
 * @brief Trait used to extract the internal vertex name from a vertex
 * property.
 *
 * To enable the use of internal vertex names in a graph type,
 * specialize the @c internal_vertex_name trait for your graph
 * property (e.g., @c a City class, which stores information about the
 * vertices in a road map).
 */
template<typename VertexProperty>
struct internal_vertex_name
{
  /**
   *  The @c type field provides a function object that extracts a key
   *  from the @c VertexProperty. The function object type must have a
   *  nested @c result_type that provides the type of the key. For
   *  more information, see the @c KeyExtractor concept in the
   *  Boost.MultiIndex documentation: @c type must either be @c void
   *  (if @c VertexProperty does not have an internal vertex name) or
   *  a model of @c KeyExtractor.
   */
  typedef void type;
};

/**
 * Extract the internal vertex name from a @c property structure by
 * looking at its base.
 */
template<typename Tag, typename T, typename Base>
struct internal_vertex_name<property<Tag, T, Base> >
  : internal_vertex_name<Base> { };

/**
 * Construct an instance of @c VertexProperty directly from its
 * name. This function object should be used within the @c
 * internal_vertex_constructor trait.
 */
template<typename VertexProperty>
struct vertex_from_name
{
private:
  typedef typename internal_vertex_name<VertexProperty>::type extract_name_type;

  typedef typename remove_cv<
            typename remove_reference<
              typename extract_name_type::result_type>::type>::type
    vertex_name_type;

public:
  typedef vertex_name_type argument_type;
  typedef VertexProperty result_type;

  VertexProperty operator()(const vertex_name_type& name)
  {
    return VertexProperty(name);
  }
};

/**
 * Throw an exception whenever one tries to construct a @c
 * VertexProperty instance from its name.
 */
template<typename VertexProperty>
struct cannot_add_vertex
{
private:
  typedef typename internal_vertex_name<VertexProperty>::type extract_name_type;

  typedef typename remove_cv<
            typename remove_reference<
              typename extract_name_type::result_type>::type>::type
    vertex_name_type;

public:
  typedef vertex_name_type argument_type;
  typedef VertexProperty result_type;

  VertexProperty operator()(const vertex_name_type&)
  {
      boost::throw_exception(std::runtime_error("add_vertex: "
                                                "unable to create a vertex from its name"));
  }
};

/**
 * @brief Trait used to construct an instance of a @c VertexProperty,
 * which is a class type that stores the properties associated with a
 * vertex in a graph, from just the name of that vertex property. This
 * operation is used when an operation is required to map from a
 * vertex name to a vertex descriptor (e.g., to add an edge outgoing
 * from that vertex), but no vertex by the name exists. The function
 * object provided by this trait will be used to add new vertices
 * based only on their names. Since this cannot be done for arbitrary
 * types, the default behavior is to throw an exception when this
 * routine is called, which requires that all named vertices be added
 * before adding any edges by name.
 */
template<typename VertexProperty>
struct internal_vertex_constructor
{
  /**
   * The @c type field provides a function object that constructs a
   * new instance of @c VertexProperty from the name of the vertex (as
   * determined by @c internal_vertex_name). The function object shall
   * accept a vertex name and return a @c VertexProperty. Predefined
   * options include:
   *
   *   @c vertex_from_name<VertexProperty>: construct an instance of
   *   @c VertexProperty directly from the name.
   *
   *   @c cannot_add_vertex<VertexProperty>: the default value, which
   *   throws an @c std::runtime_error if one attempts to add a vertex
   *   given just the name.
   */
  typedef cannot_add_vertex<VertexProperty> type;
};

/**
 * Extract the internal vertex constructor from a @c property structure by
 * looking at its base.
 */
template<typename Tag, typename T, typename Base>
struct internal_vertex_constructor<property<Tag, T, Base> >
  : internal_vertex_constructor<Base> { };

/*******************************************************************
 * Named graph mixin                                               *
 *******************************************************************/

/**
 * named_graph is a mixin that provides names for the vertices of a
 * graph, including a mapping from names to vertices. Graph types that
 * may or may not be have vertex names (depending on the properties
 * supplied by the user) should use maybe_named_graph.
 *
 * Template parameters:
 *
 *   Graph: the graph type that derives from named_graph
 *
 *   Vertex: the type of a vertex descriptor in Graph. Note: we cannot
 *   use graph_traits here, because the Graph is not yet defined.
 *
 *   VertexProperty: the type stored with each vertex in the Graph.
 */
template<typename Graph, typename Vertex, typename VertexProperty>
class named_graph
{
public:
  /// The type of the function object that extracts names from vertex
  /// properties.
  typedef typename internal_vertex_name<VertexProperty>::type extract_name_type;
  /// The type of the "bundled" property, from which the name can be
  /// extracted.
  typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type
    bundled_vertex_property_type;

  /// The type of the function object that generates vertex properties
  /// from names, for the implicit addition of vertices.
  typedef typename internal_vertex_constructor<VertexProperty>::type
    vertex_constructor_type;

  /// The type used to name vertices in the graph
  typedef typename remove_cv<
            typename remove_reference<
              typename extract_name_type::result_type>::type>::type
    vertex_name_type;

  /// The type of vertex descriptors in the graph
  typedef Vertex vertex_descriptor;

private:
  /// Key extractor for use with the multi_index_container
  struct extract_name_from_vertex
  {
    typedef vertex_name_type result_type;

    extract_name_from_vertex(Graph& graph, const extract_name_type& extract)
      : graph(graph), extract(extract) { }

    const result_type& operator()(Vertex vertex) const
    {
      return extract(graph[vertex]);
    }

    Graph& graph;
    extract_name_type extract;
  };

public:
  /// The type that maps names to vertices
  typedef multi_index::multi_index_container<
            Vertex,
            multi_index::indexed_by<
              multi_index::hashed_unique<multi_index::tag<vertex_name_t>,
                                         extract_name_from_vertex> >
          > named_vertices_type;

  /// The set of vertices, indexed by name
  typedef typename named_vertices_type::template index<vertex_name_t>::type
    vertices_by_name_type;

  /// Construct an instance of the named graph mixin, using the given
  /// function object to extract a name from the bundled property
  /// associated with a vertex.
  named_graph(const extract_name_type& extract = extract_name_type(),
              const vertex_constructor_type& vertex_constructor
                = vertex_constructor_type());

  /// Notify the named_graph that we have added the given vertex. The
  /// name of the vertex will be added to the mapping.
  void added_vertex(Vertex vertex);

  /// Notify the named_graph that we are removing the given
  /// vertex. The name of the vertex will be removed from the mapping.
  template <typename VertexIterStability>
  void removing_vertex(Vertex vertex, VertexIterStability);

  /// Notify the named_graph that we are clearing the graph.
  /// This will clear out all of the name->vertex mappings
  void clearing_graph();

  /// Retrieve the derived instance
  Graph&       derived()       { return static_cast<Graph&>(*this); }
  const Graph& derived() const { return static_cast<const Graph&>(*this); }

  /// Extract the name from a vertex property instance
  typename extract_name_type::result_type
  extract_name(const bundled_vertex_property_type& property);

  /// Search for a vertex that has the given property (based on its
  /// name)
  optional<vertex_descriptor>
  vertex_by_property(const bundled_vertex_property_type& property);

  /// Mapping from names to vertices
  named_vertices_type named_vertices;

  /// Constructs a vertex from the name of that vertex
  vertex_constructor_type vertex_constructor;
};

/// Helper macro containing the template parameters of named_graph
#define BGL_NAMED_GRAPH_PARAMS \
  typename Graph, typename Vertex, typename VertexProperty
/// Helper macro containing the named_graph<...> instantiation
#define BGL_NAMED_GRAPH \
  named_graph<Graph, Vertex, VertexProperty>

template<BGL_NAMED_GRAPH_PARAMS>
BGL_NAMED_GRAPH::named_graph(const extract_name_type& extract,
                             const vertex_constructor_type& vertex_constructor)
  : named_vertices(
      typename named_vertices_type::ctor_args_list(
        boost::make_tuple(
          boost::make_tuple(
            0, // initial number of buckets
            extract_name_from_vertex(derived(), extract),
            boost::hash<vertex_name_type>(),
            std::equal_to<vertex_name_type>())))),
    vertex_constructor(vertex_constructor)
{
}

template<BGL_NAMED_GRAPH_PARAMS>
inline void BGL_NAMED_GRAPH::added_vertex(Vertex vertex)
{
  named_vertices.insert(vertex);
}

template<BGL_NAMED_GRAPH_PARAMS>
template<typename VertexIterStability>
inline void BGL_NAMED_GRAPH::removing_vertex(Vertex vertex, VertexIterStability)
{
  BOOST_STATIC_ASSERT_MSG ((boost::is_base_of<boost::graph_detail::stable_tag, VertexIterStability>::value), "Named graphs cannot use vecS as vertex container and remove vertices; the lack of vertex descriptor stability (which iterator stability is a proxy for) means that the name -> vertex mapping would need to be completely rebuilt after each deletion.  See https://svn.boost.org/trac/boost/ticket/7863 for more information and a test case.");
  typedef typename BGL_NAMED_GRAPH::vertex_name_type vertex_name_type;
  const vertex_name_type& vertex_name = extract_name(derived()[vertex]);
  named_vertices.erase(vertex_name);
}

template<BGL_NAMED_GRAPH_PARAMS>
inline void BGL_NAMED_GRAPH::clearing_graph()
{
  named_vertices.clear();
}

template<BGL_NAMED_GRAPH_PARAMS>
typename BGL_NAMED_GRAPH::extract_name_type::result_type
BGL_NAMED_GRAPH::extract_name(const bundled_vertex_property_type& property)
{
  return named_vertices.key_extractor().extract(property);
}

template<BGL_NAMED_GRAPH_PARAMS>
optional<typename BGL_NAMED_GRAPH::vertex_descriptor>
BGL_NAMED_GRAPH::
vertex_by_property(const bundled_vertex_property_type& property)
{
  return find_vertex(extract_name(property), *this);
}

/// Retrieve the vertex associated with the given name
template<BGL_NAMED_GRAPH_PARAMS>
optional<Vertex>
find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
            const BGL_NAMED_GRAPH& g)
{
  typedef typename BGL_NAMED_GRAPH::vertices_by_name_type
    vertices_by_name_type;

  // Retrieve the set of vertices indexed by name
  vertices_by_name_type const& vertices_by_name
    = g.named_vertices.template get<vertex_name_t>();

  /// Look for a vertex with the given name
  typename vertices_by_name_type::const_iterator iter
    = vertices_by_name.find(name);

  if (iter == vertices_by_name.end())
    return optional<Vertex>(); // vertex not found
  else
    return *iter;
}

/// Retrieve the vertex associated with the given name, or add a new
/// vertex with that name if no such vertex is available.
/// Note: This is enabled only when the vertex property type is different
///       from the vertex name to avoid ambiguous overload problems with
///       the add_vertex() function that takes a vertex property.
template<BGL_NAMED_GRAPH_PARAMS>
    typename disable_if<is_same<
        typename BGL_NAMED_GRAPH::vertex_name_type,
        VertexProperty
    >,
Vertex>::type
add_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
           BGL_NAMED_GRAPH& g)
{
  if (optional<Vertex> vertex = find_vertex(name, g))
    /// We found the vertex, so return it
    return *vertex;
  else
    /// There is no vertex with the given name, so create one
    return add_vertex(g.vertex_constructor(name), g.derived());
}

/// Add an edge using vertex names to refer to the vertices
template<BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
         BGL_NAMED_GRAPH& g)
{
  return add_edge(add_vertex(u_name, g.derived()),
                  add_vertex(v_name, g.derived()),
                  g.derived());
}

/// Add an edge using vertex descriptors or names to refer to the vertices
template<BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
         BGL_NAMED_GRAPH& g)
{
  return add_edge(u,
                  add_vertex(v_name, g.derived()),
                  g.derived());
}

/// Add an edge using vertex descriptors or names to refer to the vertices
template<BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
         typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
         BGL_NAMED_GRAPH& g)
{
  return add_edge(add_vertex(u_name, g.derived()),
                  v,
                  g.derived());
}

// Overloads to support EdgeMutablePropertyGraph graphs
template <BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
         typename edge_property_type<Graph>::type const& p,
         BGL_NAMED_GRAPH& g) {
    return add_edge(u, add_vertex(v_name, g.derived()), p, g.derived());
}

template <BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
         typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
         typename edge_property_type<Graph>::type const& p,
         BGL_NAMED_GRAPH& g) {
    return add_edge(add_vertex(u_name, g.derived()), v, p, g.derived());
}

template <BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
         typename edge_property_type<Graph>::type const& p,
         BGL_NAMED_GRAPH& g) {
    return add_edge(add_vertex(u_name, g.derived()),
                    add_vertex(v_name, g.derived()), p, g.derived());
}

#undef BGL_NAMED_GRAPH
#undef BGL_NAMED_GRAPH_PARAMS

/*******************************************************************
 * Maybe named graph mixin                                         *
 *******************************************************************/

/**
 * A graph mixin that can provide a mapping from names to vertices,
 * and use that mapping to simplify creation and manipulation of
 * graphs.
 */
template<typename Graph, typename Vertex, typename VertexProperty,
         typename ExtractName
           = typename internal_vertex_name<VertexProperty>::type>
struct maybe_named_graph : public named_graph<Graph, Vertex, VertexProperty>
{
};

/**
 * A graph mixin that can provide a mapping from names to vertices,
 * and use that mapping to simplify creation and manipulation of
 * graphs. This partial specialization turns off this functionality
 * when the @c VertexProperty does not have an internal vertex name.
 */
template<typename Graph, typename Vertex, typename VertexProperty>
struct maybe_named_graph<Graph, Vertex, VertexProperty, void>
{
  /// The type of the "bundled" property, from which the name can be
  /// extracted.
  typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type
    bundled_vertex_property_type;

  /// Notify the named_graph that we have added the given vertex. This
  /// is a no-op.
  void added_vertex(Vertex) { }

  /// Notify the named_graph that we are removing the given
  /// vertex. This is a no-op.
  template <typename VertexIterStability>
  void removing_vertex(Vertex, VertexIterStability) { }

  /// Notify the named_graph that we are clearing the graph. This is a
  /// no-op.
  void clearing_graph() { }

  /// Search for a vertex that has the given property (based on its
  /// name). This always returns an empty optional<>
  optional<Vertex>
  vertex_by_property(const bundled_vertex_property_type&)
  {
    return optional<Vertex>();
  }
};

} } // end namespace boost::graph

#endif // BOOST_GRAPH_NAMED_GRAPH_HPP

license: mit


code:
// (C) Copyright 2007-2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GRAPH_NUMERIC_VALUES_HPP
#define BOOST_GRAPH_NUMERIC_VALUES_HPP

#include <limits>

namespace boost
{

#define BOOST_GRAPH_SPECIALIZE_NUMERIC_FLOAT(type) \
    template <> struct numeric_values<type> { \
        typedef type value_type; \
        static type zero() { return 0.0; } \
        static type infinity() { return std::numeric_limits<type>::infinity(); } \
    };

    /**
     * This generic type reports various numeric values for some type. In the
     * general case, numeric values simply treat their maximum value as infinity
     * and the default-constructed value as 0.
     *
     * Specializations of this template can redefine the notions of zero and
     * infinity for various types. For example, the class is specialized for
     * floating point types to use the built in notion of infinity.
     */
    template <typename T>
    struct numeric_values
    {
        typedef T value_type;

        static T zero()
        { return T(); }

        static T infinity()
        { return (std::numeric_limits<T>::max)(); }
    };

    // Specializations for floating point types refer to 0.0 and their infinity
    // value defined by numeric_limits.
    BOOST_GRAPH_SPECIALIZE_NUMERIC_FLOAT(float)
    BOOST_GRAPH_SPECIALIZE_NUMERIC_FLOAT(double)
    BOOST_GRAPH_SPECIALIZE_NUMERIC_FLOAT(long double)

#undef BOOST_GRAPH_SPECIALIZE_NUMERIC_VALUE
}

#endif


code:
// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to 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)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine

//
// This file contains helps that enable concept-based overloading
// within the Boost Graph Library.
//
#ifndef BOOST_GRAPH_OVERLOADING_HPP
#define BOOST_GRAPH_OVERLOADING_HPP

#include <boost/type_traits/is_base_and_derived.hpp>
#include <boost/utility/enable_if.hpp>

namespace boost {  namespace graph { namespace detail {

struct no_parameter {};

} } } // end namespace boost::graph::detail

#ifndef BOOST_NO_SFINAE

#define BOOST_GRAPH_ENABLE_IF_MODELS(Graph, Tag, Type)               \
  typename enable_if_c<(is_base_and_derived<                         \
                          Tag,                                       \
                          typename graph_traits<Graph>::traversal_category>::value), \
                       Type>::type

#define BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, Tag)                   \
  , BOOST_GRAPH_ENABLE_IF_MODELS(Graph, Tag,                            \
                                 ::boost::graph::detail::no_parameter)  \
    = ::boost::graph::detail::no_parameter()

#else

#define BOOST_GRAPH_ENABLE_IF_MODELS(Graph, Tag, Type) Type
#define BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, Tag)

#endif // no SFINAE support

#endif // BOOST_GRAPH_OVERLOADING_HPP


code:
// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to 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)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine
#ifndef BOOST_PARALLEL_ALGORITHM_HPP
#define BOOST_PARALLEL_ALGORITHM_HPP

#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif

#include <boost/optional.hpp>
#include <boost/config.hpp> // for BOOST_STATIC_CONSTANT
#include <vector>
#include <functional>

namespace boost { namespace parallel {
  template<typename BinaryOp>
  struct is_commutative
  {
    BOOST_STATIC_CONSTANT(bool, value = false);
  };

  template<typename T>
  struct minimum : std::binary_function<T, T, T>
  {
    const T& operator()(const T& x, const T& y) const { return x < y? x : y; }
  };

  template<typename T>
  struct maximum : std::binary_function<T, T, T>
  {
    const T& operator()(const T& x, const T& y) const { return x < y? y : x; }
  };

  template<typename T>
  struct sum : std::binary_function<T, T, T>
  {
    const T operator()(const T& x, const T& y) const { return x + y; }
  };

  template<typename ProcessGroup, typename InputIterator,
           typename OutputIterator, typename BinaryOperation>
  OutputIterator
  reduce(ProcessGroup pg, typename ProcessGroup::process_id_type root,
         InputIterator first, InputIterator last, OutputIterator out,
         BinaryOperation bin_op);

  template<typename ProcessGroup, typename T, typename BinaryOperation>
  inline T
  all_reduce(ProcessGroup pg, const T& value, BinaryOperation bin_op)
  {
    T result;
    all_reduce(pg,
               const_cast<T*>(&value), const_cast<T*>(&value+1),
               &result, bin_op);
    return result;
  }

  template<typename ProcessGroup, typename T, typename BinaryOperation>
  inline T
  scan(ProcessGroup pg, const T& value, BinaryOperation bin_op)
  {
    T result;
    scan(pg,
         const_cast<T*>(&value), const_cast<T*>(&value+1),
         &result, bin_op);
    return result;
  }

  template<typename ProcessGroup, typename InputIterator, typename T>
  void
  all_gather(ProcessGroup pg, InputIterator first, InputIterator last,
             std::vector<T>& out);
} } // end namespace boost::parallel

#include <boost/graph/parallel/detail/inplace_all_to_all.hpp>

#endif // BOOST_PARALLEL_ALGORITHM_HPP


code:
// Copyright (C) 2004-2006 The Trustees of Indiana University.

// Use, modification and distribution is subject to 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)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine

//
// This file contains traits that describe
//
#ifndef BOOST_GRAPH_PARALLEL_CONTAINER_TRAITS_HPP
#define BOOST_GRAPH_PARALLEL_CONTAINER_TRAITS_HPP

#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif

namespace boost { namespace graph { namespace parallel {

template<typename T>
struct process_group_type
{
  typedef typename T::process_group_type type;
};

template<typename T>
inline typename process_group_type<T>::type
process_group(const T& x)
{ return x.process_group(); }

// Helper function that algorithms should use to get the process group
// out of a container.
template<typename Container>
inline typename process_group_type<Container>::type
process_group_adl(const Container& container)
{
  return process_group(container);
}

} } } // end namespace boost::graph::parallel

#endif // BOOST_GRAPH_PARALLEL_CONTAINER_TRAITS_HPP


code:
// Copyright 2005 The Trustees of Indiana University.

// Use, modification and distribution is subject to 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)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine

#ifndef BOOST_GRAPH_PARALLEL_INPLACE_ALL_TO_ALL_HPP
#define BOOST_GRAPH_PARALLEL_INPLACE_ALL_TO_ALL_HPP

#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif

//
// Implements the inplace all-to-all communication algorithm.
//
#include <vector>
#include <iterator>

namespace boost { namespace parallel {

template<typename ProcessGroup, typename T>
// where {LinearProcessGroup<ProcessGroup>, MessagingProcessGroup<ProcessGroup>}
void
inplace_all_to_all(ProcessGroup pg,
                   const std::vector<std::vector<T> >& outgoing,
                   std::vector<std::vector<T> >& incoming)
{
  typedef typename std::vector<T>::size_type size_type;

  typedef typename ProcessGroup::process_size_type process_size_type;
  typedef typename ProcessGroup::process_id_type process_id_type;

  process_size_type p = num_processes(pg);

  // Make sure there are no straggling messages
  synchronize(pg);

  // Send along the count (always) and the data (if count > 0)
  for (process_id_type dest = 0; dest < p; ++dest) {
    if (dest != process_id(pg)) {
      send(pg, dest, 0, outgoing[dest].size());
      if (!outgoing[dest].empty())
        send(pg, dest, 1, &outgoing[dest].front(), outgoing[dest].size());
    }
  }

  // Make sure all of the data gets transferred
  synchronize(pg);

  // Receive the sizes and data
  for (process_id_type source = 0; source < p; ++source) {
    if (source != process_id(pg)) {
      size_type size;
      receive(pg, source, 0, size);
      incoming[source].resize(size);
      if (size > 0)
        receive(pg, source, 1, &incoming[source].front(), size);
    } else if (&incoming != &outgoing) {
      incoming[source] = outgoing[source];
    }
  }
}

template<typename ProcessGroup, typename T>
// where {LinearProcessGroup<ProcessGroup>, MessagingProcessGroup<ProcessGroup>}
void
inplace_all_to_all(ProcessGroup pg, std::vector<std::vector<T> >& data)
{
  inplace_all_to_all(pg, data, data);
}

} } // end namespace boost::parallel

#endif // BOOST_GRAPH_PARALLEL_INPLACE_ALL_TO_ALL_HPP


code:
// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to 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)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine

// File moved
#include <boost/property_map/parallel/process_group.hpp>


code:
// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to 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)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine

#ifndef BOOST_GRAPH_PARALLEL_PROPERTIES_HPP
#define BOOST_GRAPH_PARALLEL_PROPERTIES_HPP

#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif

#include <boost/graph/properties.hpp>
#include <boost/property_map/parallel/distributed_property_map.hpp>

namespace boost {
  /***************************************************************************
   * Property map reduction operations
   ***************************************************************************/
  /**
   * Metafunction that produces a reduction operation for the given
   * property. The default behavior merely forwards to @ref
   * basic_reduce, but it is expected that this class template will be
   * specified for important properties.
   */
  template<typename Property>
  struct property_reduce
  {
    template<typename Value>
    class apply : public parallel::basic_reduce<Value> {};
  };

  /**
   * Reduction of vertex colors can only darken, not lighten, the
   * color. Black cannot turn black, grey can only turn black, and
   * white can be changed to either color. The default color is white.
   */
  template<>
  struct property_reduce<vertex_color_t>
  {
    template<typename Color>
    class apply
    {
      typedef color_traits<Color> traits;

    public:
      BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);

      template<typename Key>
      Color operator()(const Key&) const { return traits::white(); }

      template<typename Key>
      Color operator()(const Key&, Color local, Color remote) const {
        if (local == traits::white()) return remote;
        else if (remote == traits::black()) return remote;
        else return local;
      }
    };
  };

  /**
   * Reduction of a distance always takes the shorter distance. The
   * default distance value is the maximum value for the data type.
   */
  template<>
  struct property_reduce<vertex_distance_t>
  {
    template<typename T>
    class apply
    {
    public:
      BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);

      template<typename Key>
      T operator()(const Key&) const { return (std::numeric_limits<T>::max)(); }

      template<typename Key>
      T operator()(const Key&, T x, T y) const { return x < y? x : y; }
    };
  };

  template<>
  struct property_reduce<vertex_predecessor_t>
  {
    template<typename T>
    class apply
    {
    public:
      BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);

      template<typename Key>
      T operator()(Key key) const { return key; }
      template<typename Key>
      T operator()(Key key, T, T y) const { return y; }
    };
  };

  template<typename Property, typename PropertyMap>
  inline void set_property_map_role(Property p, PropertyMap pm)
  {
    typedef typename property_traits<PropertyMap>::value_type value_type;
    typedef property_reduce<Property> property_red;
    typedef typename property_red::template apply<value_type> reduce;

    pm.set_reduce(reduce());
  }

} // end namespace boost
#endif // BOOST_GRAPH_PARALLEL_PROPERTIES_HPP


code:
// Copyright (C) 2007 Douglas Gregor

// Use, modification and distribution is subject to 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)

// This file contains a simplification of the "trigger" method for
// process groups. The simple trigger handles the common case where
// the handler associated with a trigger is a member function bound to
// a particular pointer.

// File moved
#include <boost/property_map/parallel/simple_trigger.hpp>


code:
//=======================================================================
// 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_PROPERTIES_HPP
#define BOOST_GRAPH_PROPERTIES_HPP

#include <boost/config.hpp>
#include <boost/assert.hpp>
#include <boost/pending/property.hpp>
#include <boost/detail/workaround.hpp>

// Include the property map library and extensions in the BGL.
#include <boost/property_map/property_map.hpp>
#include <boost/graph/property_maps/constant_property_map.hpp>
#include <boost/graph/property_maps/null_property_map.hpp>

#include <boost/graph/graph_traits.hpp>
#include <boost/type_traits.hpp>
#include <boost/limits.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/not.hpp>
#include <boost/mpl/if.hpp>

namespace boost {

  enum default_color_type { white_color, gray_color, green_color, red_color, black_color };

  template <class ColorValue>
  struct color_traits {
    static default_color_type white() { return white_color; }
    static default_color_type gray() { return gray_color; }
    static default_color_type green() { return green_color; }
    static default_color_type red() { return red_color; }
    static default_color_type black() { return black_color; }
  };

  // These functions are now obsolete, replaced by color_traits.
  inline default_color_type white(default_color_type) { return white_color; }
  inline default_color_type gray(default_color_type) { return gray_color; }
  inline default_color_type green(default_color_type) { return green_color; }
  inline default_color_type red(default_color_type) { return red_color; }
  inline default_color_type black(default_color_type) { return black_color; }

  struct graph_property_tag { };
  struct vertex_property_tag { };
  struct edge_property_tag { };

  // See examples/edge_property.cpp for how to use this.
#define BOOST_INSTALL_PROPERTY(KIND, NAME) \
  template <> struct property_kind<KIND##_##NAME##_t> { \
    typedef KIND##_property_tag type; \
  }

#define BOOST_DEF_PROPERTY(KIND, NAME) \
  enum KIND##_##NAME##_t { KIND##_##NAME }; \
  BOOST_INSTALL_PROPERTY(KIND, NAME)

  // These three are defined in boost/pending/property.hpp
  BOOST_INSTALL_PROPERTY(vertex, all);
  BOOST_INSTALL_PROPERTY(edge, all);
  BOOST_INSTALL_PROPERTY(graph, all);
  BOOST_DEF_PROPERTY(vertex, index);
  BOOST_DEF_PROPERTY(vertex, index1);
  BOOST_DEF_PROPERTY(vertex, index2);
  BOOST_DEF_PROPERTY(vertex, root);
  BOOST_DEF_PROPERTY(edge, index);
  BOOST_DEF_PROPERTY(edge, name);
  BOOST_DEF_PROPERTY(edge, weight);
  BOOST_DEF_PROPERTY(edge, weight2);
  BOOST_DEF_PROPERTY(edge, color);
  BOOST_DEF_PROPERTY(vertex, name);
  BOOST_DEF_PROPERTY(graph, name);
  BOOST_DEF_PROPERTY(vertex, distance);
  BOOST_DEF_PROPERTY(vertex, distance2);
  BOOST_DEF_PROPERTY(vertex, color);
  BOOST_DEF_PROPERTY(vertex, degree);
  BOOST_DEF_PROPERTY(vertex, in_degree);
  BOOST_DEF_PROPERTY(vertex, out_degree);
  BOOST_DEF_PROPERTY(vertex, current_degree);
  BOOST_DEF_PROPERTY(vertex, priority);
  BOOST_DEF_PROPERTY(vertex, discover_time);
  BOOST_DEF_PROPERTY(vertex, finish_time);
  BOOST_DEF_PROPERTY(vertex, predecessor);
  BOOST_DEF_PROPERTY(vertex, rank);
  BOOST_DEF_PROPERTY(vertex, centrality);
  BOOST_DEF_PROPERTY(vertex, lowpoint);
  BOOST_DEF_PROPERTY(vertex, potential);
  BOOST_DEF_PROPERTY(vertex, update);
  BOOST_DEF_PROPERTY(vertex, underlying);
  BOOST_DEF_PROPERTY(edge, reverse);
  BOOST_DEF_PROPERTY(edge, capacity);
  BOOST_DEF_PROPERTY(edge, flow);
  BOOST_DEF_PROPERTY(edge, residual_capacity);
  BOOST_DEF_PROPERTY(edge, centrality);
  BOOST_DEF_PROPERTY(edge, discover_time);
  BOOST_DEF_PROPERTY(edge, update);
  BOOST_DEF_PROPERTY(edge, finished);
  BOOST_DEF_PROPERTY(edge, underlying);
  BOOST_DEF_PROPERTY(graph, visitor);

  // These tags are used for property bundles
  // These three are defined in boost/pending/property.hpp
  BOOST_INSTALL_PROPERTY(graph, bundle);
  BOOST_INSTALL_PROPERTY(vertex, bundle);
  BOOST_INSTALL_PROPERTY(edge, bundle);

  // These tags are used to denote the owners and local descriptors
  // for the vertices and edges of a distributed graph.
  BOOST_DEF_PROPERTY(vertex, global);
  BOOST_DEF_PROPERTY(vertex, owner);
  BOOST_DEF_PROPERTY(vertex, local);
  BOOST_DEF_PROPERTY(edge, global);
  BOOST_DEF_PROPERTY(edge, owner);
  BOOST_DEF_PROPERTY(edge, local);
  BOOST_DEF_PROPERTY(vertex, local_index);
  BOOST_DEF_PROPERTY(edge, local_index);

#undef BOOST_DEF_PROPERTY

  namespace detail {

    template <typename G, typename Tag>
    struct property_kind_from_graph: property_kind<Tag> {};

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    template <typename G, typename R, typename T>
    struct property_kind_from_graph<G, R T::*> {
      typedef typename boost::mpl::if_<
                boost::is_base_of<T, typename vertex_bundle_type<G>::type>,
                vertex_property_tag,
                typename boost::mpl::if_<
                  boost::is_base_of<T, typename edge_bundle_type<G>::type>,
                  edge_property_tag,
                  typename boost::mpl::if_<
                    boost::is_base_of<T, typename graph_bundle_type<G>::type>,
                    graph_property_tag,
                    void>::type>::type>::type type;
    };
#endif

    struct dummy_edge_property_selector {
      template <class Graph, class Property, class Tag>
      struct bind_ {
        typedef identity_property_map type;
        typedef identity_property_map const_type;
      };
    };
    struct dummy_vertex_property_selector {
      template <class Graph, class Property, class Tag>
      struct bind_ {
        typedef identity_property_map type;
        typedef identity_property_map const_type;
      };
    };

  } // namespace detail

  // Graph classes can either partially specialize property_map
  // or they can specialize these two selector classes.
  template <class GraphTag>
  struct edge_property_selector {
    typedef detail::dummy_edge_property_selector type;
  };

  template <class GraphTag>
  struct vertex_property_selector {
    typedef detail::dummy_vertex_property_selector type;
  };

  namespace detail {

    template <typename A> struct return_void {typedef void type;};

    template <typename Graph, typename Enable = void>
    struct graph_tag_or_void {
      typedef void type;
    };

    template <typename Graph>
    struct graph_tag_or_void<Graph, typename return_void<typename Graph::graph_tag>::type> {
      typedef typename Graph::graph_tag type;
    };

    template <class Graph, class PropertyTag>
    struct edge_property_map
      : edge_property_selector<
          typename graph_tag_or_void<Graph>::type
        >::type::template bind_<
                            Graph,
                            typename edge_property_type<Graph>::type,
                            PropertyTag>
      {};
    template <class Graph, class PropertyTag>
    struct vertex_property_map
      : vertex_property_selector<
          typename graph_tag_or_void<Graph>::type
        >::type::template bind_<
                            Graph,
                            typename vertex_property_type<Graph>::type,
                            PropertyTag>
      {};
  } // namespace detail

  template <class Graph, class Property, class Enable = void>
  struct property_map:
    mpl::if_<
      is_same<typename detail::property_kind_from_graph<Graph, Property>::type, edge_property_tag>,
      detail::edge_property_map<Graph, Property>,
      detail::vertex_property_map<Graph, Property> >::type
  {};

  // shortcut for accessing the value type of the property map
  template <class Graph, class Property>
  class property_map_value {
    typedef typename property_map<Graph, Property>::const_type PMap;
  public:
    typedef typename property_traits<PMap>::value_type type;
  };

  template <class Graph, class Property>
  class graph_property {
  public:
    typedef typename property_value<
      typename boost::graph_property_type<Graph>::type, Property
    >::type type;
  };

  template <typename Graph> struct vertex_property: vertex_property_type<Graph> {};
  template <typename Graph> struct edge_property: edge_property_type<Graph> {};

  template <typename Graph>
  class degree_property_map
    : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
                            degree_property_map<Graph> >
  {
  public:
    typedef typename graph_traits<Graph>::vertex_descriptor key_type;
    typedef typename graph_traits<Graph>::degree_size_type value_type;
    typedef value_type reference;
    typedef readable_property_map_tag category;
    degree_property_map(const Graph& g) : m_g(g) { }
    value_type operator[](const key_type& v) const {
      return degree(v, m_g);
    }
  private:
    const Graph& m_g;
  };
  template <typename Graph>
  inline degree_property_map<Graph>
  make_degree_map(const Graph& g) {
    return degree_property_map<Graph>(g);
  }

  //========================================================================
  // Iterator Property Map Generating Functions contributed by
  // Kevin Vanhorn. (see also the property map generating functions
  // in boost/property_map/property_map.hpp)

#if !defined(BOOST_NO_STD_ITERATOR_TRAITS)
  // A helper function for creating a vertex property map out of a
  // random access iterator and the internal vertex index map from a
  // graph.
  template <class PropertyGraph, class RandomAccessIterator>
  inline
  iterator_property_map<
    RandomAccessIterator,
    typename property_map<PropertyGraph, vertex_index_t>::type,
    typename std::iterator_traits<RandomAccessIterator>::value_type,
    typename std::iterator_traits<RandomAccessIterator>::reference
  >
  make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g)
  {
    return make_iterator_property_map(iter, get(vertex_index, g));
  }

  // Use this next function when vertex_descriptor is known to be an
  // integer type, with values ranging from 0 to num_vertices(g).
  //
  template <class RandomAccessIterator>
  inline
  iterator_property_map<
    RandomAccessIterator,
    identity_property_map,
    typename std::iterator_traits<RandomAccessIterator>::value_type,
    typename std::iterator_traits<RandomAccessIterator>::reference
  >
  make_iterator_vertex_map(RandomAccessIterator iter)
  {
    return make_iterator_property_map(iter, identity_property_map());
  }
#endif

  template <class PropertyGraph, class RandomAccessContainer>
  inline
  iterator_property_map<
    typename RandomAccessContainer::iterator,
    typename property_map<PropertyGraph, vertex_index_t>::type,
    typename RandomAccessContainer::value_type,
    typename RandomAccessContainer::reference
  >
  make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g)
  {
    BOOST_ASSERT(c.size() >= num_vertices(g));
    return make_iterator_vertex_map(c.begin(), g);
  }

  template <class RandomAccessContainer> inline
  iterator_property_map<
    typename RandomAccessContainer::iterator,
    identity_property_map,
    typename RandomAccessContainer::value_type,
    typename RandomAccessContainer::reference
  >
  make_container_vertex_map(RandomAccessContainer& c)
  {
    return make_iterator_vertex_map(c.begin());
  }

// NOTE: These functions are declared, but never defined since they need to
// be overloaded by graph implementations. However, we need them to be
// declared for the functions below.
template<typename Graph, typename Tag>
typename graph_property<Graph, graph_bundle_t>::type&
get_property(Graph& g, Tag);

template<typename Graph, typename Tag>
typename graph_property<Graph, graph_bundle_t>::type const&
get_property(Graph const& g, Tag);

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
// NOTE: This operation is a simple adaptor over the overloaded get_property
// operations.
template<typename Graph>
inline typename graph_property<Graph, graph_bundle_t>::type&
get_property(Graph& g) {
  return get_property(g, graph_bundle);
}

template<typename Graph>
inline typename graph_property<Graph, graph_bundle_t>::type const&
get_property(const Graph& g) {
  return get_property(g, graph_bundle);
}
#endif

} // namespace boost

#endif /* BOOST_GRAPH_PROPERTIES_HPP */


code:
// (C) Copyright 2007-2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GRAPH_CONSTANT_PROPERTY_HPP
#define BOOST_GRAPH_CONSTANT_PROPERTY_HPP

#include <boost/property_map/property_map.hpp>

// TODO: This should really be part of the property maps library rather than
// the Boost.Graph library.

namespace boost {

/**
 * A constant property is one, that regardless of the edge or vertex given,
 * will always return a constant value.
 */
template <typename Key, typename Value>
struct constant_property_map
    : public boost::put_get_helper<
            const Value&,
            constant_property_map<Key, Value>
    >
{
    typedef Key key_type;
    typedef Value value_type;
    typedef const Value& reference;
    typedef boost::readable_property_map_tag category;

    constant_property_map()
        : m_value()
    { }

    constant_property_map(const value_type &value)
        : m_value(value)
    { }

    constant_property_map(const constant_property_map& copy)
        : m_value(copy.m_value)
    { }

    inline reference operator [](const key_type&) const
    { return m_value; }

    value_type m_value;
};

template <typename Key, typename Value>
inline constant_property_map<Key, Value>
make_constant_property(const Value& value)
{ return constant_property_map<Key, Value>(value); }

/**
 * Same as above, but pretends to be writable as well.
 */
template <typename Key, typename Value>
struct constant_writable_property_map {
    typedef Key key_type;
    typedef Value value_type;
    typedef Value& reference;
    typedef boost::read_write_property_map_tag category;

    constant_writable_property_map()
        : m_value()
    { }

    constant_writable_property_map(const value_type &value)
        : m_value(value)
    { }

    constant_writable_property_map(const constant_writable_property_map& copy)
        : m_value(copy.m_value)
    { }

    friend Value get(const constant_writable_property_map& me, Key) {return me.m_value;}
    friend void put(const constant_writable_property_map&, Key, Value) {}

    value_type m_value;
};

template <typename Key, typename Value>
inline constant_writable_property_map<Key, Value>
make_constant_writable_property(const Value& value)
{ return constant_writable_property_map<Key, Value>(value); }

} /* namespace boost */

#endif


code:
// (C) Copyright Andrew Sutton 2007
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GRAPH_NULL_PROPERTY_HPP
#define BOOST_GRAPH_NULL_PROPERTY_HPP

#include <boost/property_map/property_map.hpp>

// TODO: This should really be part of the property maps library rather than
// the Boost.Graph library.

namespace boost
{
    // A null property is somewhat like the inverse of the constant
    // property map except that instead of returning a single value,
    // this eats any writes and cannot be read from.

    template <typename Key, typename Value>
    struct null_property_map
    {
        typedef Key key_type;
        typedef Value value_type;
        typedef void reference;
        typedef boost::writable_property_map_tag category;
    };

    // The null_property_map<K,V> only has a put() function.
    template <typename K, typename V>
    void put(null_property_map<K,V>& /*pm*/, const K& /*key*/, const V& /*value*/)
    { }

    // A helper function for intantiating null property maps.
    template <typename Key, typename Value>
    inline null_property_map<Key, Value> make_null_property()
    { return null_property_map<Key, Value>(); }
}

#endif