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
//           Nick Edmonds
//           Andrew Lumsdaine
#include <boost/assert.hpp>
#include <boost/property_map/parallel/distributed_property_map.hpp>
#include <boost/property_map/parallel/detail/untracked_pair.hpp>
#include <boost/type_traits/is_base_and_derived.hpp>
#include <boost/bind.hpp>
#include <boost/property_map/parallel/simple_trigger.hpp>

namespace boost { namespace parallel {

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
template<typename Reduce>
PBGL_DISTRIB_PMAP
::distributed_property_map(const ProcessGroup& pg, const GlobalMap& global,
                           const StorageMap& pm, const Reduce& reduce)
  : data(new data_t(pg, global, pm, reduce, Reduce::non_default_resolver))
{
  typedef handle_message<Reduce> Handler;

  data->ghost_cells.reset(new ghost_cells_type());
  data->reset = &data_t::template do_reset<Reduce>;
  data->process_group.replace_handler(Handler(data, reduce));
  data->process_group.template get_receiver<Handler>()
    ->setup_triggers(data->process_group);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
PBGL_DISTRIB_PMAP::~distributed_property_map() { }

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
template<typename Reduce>
void
PBGL_DISTRIB_PMAP::set_reduce(const Reduce& reduce)
{
  typedef handle_message<Reduce> Handler;
  data->process_group.replace_handler(Handler(data, reduce));
  Handler* handler = data->process_group.template get_receiver<Handler>();
  BOOST_ASSERT(handler);
  handler->setup_triggers(data->process_group);
  data->get_default_value = reduce;
  data->has_default_resolver = Reduce::non_default_resolver;
  int model = data->model;
  data->reset = &data_t::template do_reset<Reduce>;
  set_consistency_model(model);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void PBGL_DISTRIB_PMAP::prune_ghost_cells() const
{
  if (data->max_ghost_cells == 0)
    return;

  while (data->ghost_cells->size() > data->max_ghost_cells) {
    // Evict the last ghost cell

    if (data->model & cm_flush) {
      // We need to flush values when we evict them.
      boost::parallel::detail::untracked_pair<key_type, value_type> const& victim
        = data->ghost_cells->back();
      send(data->process_group, get(data->global, victim.first).first,
           property_map_put, victim);
    }

    // Actually remove the ghost cell
    data->ghost_cells->pop_back();
  }
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
typename PBGL_DISTRIB_PMAP::value_type&
PBGL_DISTRIB_PMAP::cell(const key_type& key, bool request_if_missing) const
{
  // Index by key
  ghost_cells_key_index_type const& key_index
    = data->ghost_cells->template get<1>();

  // Search for the ghost cell by key, and project back to the sequence
  iterator ghost_cell
    = data->ghost_cells->template project<0>(key_index.find(key));
  if (ghost_cell == data->ghost_cells->end()) {
    value_type value;
    if (data->has_default_resolver)
      // Since we have a default resolver, use it to create a default
      // value for this ghost cell.
      value = data->get_default_value(key);
    else if (request_if_missing)
      // Request the actual value of this key from its owner
      send_oob_with_reply(data->process_group, get(data->global, key).first,
                          property_map_get, key, value);
    else
      value = value_type();

    // Create a ghost cell containing the new value
    ghost_cell
      = data->ghost_cells->push_front(std::make_pair(key, value)).first;

    // If we need to, prune the ghost cells
    if (data->max_ghost_cells > 0)
      prune_ghost_cells();
  } else if (data->max_ghost_cells > 0)
    // Put this cell at the beginning of the MRU list
    data->ghost_cells->relocate(data->ghost_cells->begin(), ghost_cell);

  return const_cast<value_type&>(ghost_cell->second);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
template<typename Reduce>
void
PBGL_DISTRIB_PMAP
::handle_message<Reduce>::operator()(process_id_type source, int tag)
{
  BOOST_ASSERT(false);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
template<typename Reduce>
void
PBGL_DISTRIB_PMAP::handle_message<Reduce>::
handle_put(int /*source*/, int /*tag*/,
           const boost::parallel::detail::untracked_pair<key_type, value_type>& req, trigger_receive_context)
{
  using boost::get;

  shared_ptr<data_t> data(data_ptr);

  owner_local_pair p = get(data->global, req.first);
  BOOST_ASSERT(p.first == process_id(data->process_group));

  detail::maybe_put(data->storage, p.second,
                    reduce(req.first,
                           get(data->storage, p.second),
                           req.second));
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
template<typename Reduce>
typename PBGL_DISTRIB_PMAP::value_type
PBGL_DISTRIB_PMAP::handle_message<Reduce>::
handle_get(int source, int /*tag*/, const key_type& key,
           trigger_receive_context)
{
  using boost::get;

  shared_ptr<data_t> data(data_ptr);
  BOOST_ASSERT(data);

  owner_local_pair p = get(data->global, key);
  return get(data->storage, p.second);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
template<typename Reduce>
void
PBGL_DISTRIB_PMAP::handle_message<Reduce>::
handle_multiget(int source, int tag, const std::vector<key_type>& keys,
                trigger_receive_context)
{
  shared_ptr<data_t> data(data_ptr);
  BOOST_ASSERT(data);

  typedef boost::parallel::detail::untracked_pair<key_type, value_type> key_value;
  std::vector<key_value> results;
  std::size_t n = keys.size();
  results.reserve(n);

  using boost::get;

  for (std::size_t i = 0; i < n; ++i) {
    local_key_type local_key = get(data->global, keys[i]).second;
    results.push_back(key_value(keys[i], get(data->storage, local_key)));
  }
  send(data->process_group, source, property_map_multiget_reply, results);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
template<typename Reduce>
void
PBGL_DISTRIB_PMAP::handle_message<Reduce>::
handle_multiget_reply
  (int source, int tag,
   const std::vector<boost::parallel::detail::untracked_pair<key_type, value_type> >& msg,
   trigger_receive_context)
{
  shared_ptr<data_t> data(data_ptr);
  BOOST_ASSERT(data);

  // Index by key
  ghost_cells_key_index_type const& key_index
    = data->ghost_cells->template get<1>();

  std::size_t n = msg.size();
  for (std::size_t i = 0; i < n; ++i) {
    // Search for the ghost cell by key, and project back to the sequence
    iterator position
      = data->ghost_cells->template project<0>(key_index.find(msg[i].first));

    if (position != data->ghost_cells->end())
      const_cast<value_type&>(position->second) = msg[i].second;
  }
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
template<typename Reduce>
void
PBGL_DISTRIB_PMAP::handle_message<Reduce>::
handle_multiput
  (int source, int tag,
   const std::vector<unsafe_pair<local_key_type, value_type> >& values,
   trigger_receive_context)
{
  using boost::get;

  shared_ptr<data_t> data(data_ptr);
  BOOST_ASSERT(data);

  std::size_t n = values.size();
  for (std::size_t i = 0; i < n; ++i) {
    local_key_type local_key = values[i].first;
    value_type local_value = get(data->storage, local_key);
    detail::maybe_put(data->storage, values[i].first,
                      reduce(values[i].first,
                             local_value,
                             values[i].second));
  }
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
template<typename Reduce>
void
PBGL_DISTRIB_PMAP::handle_message<Reduce>::
setup_triggers(process_group_type& pg)
{
  using boost::parallel::simple_trigger;

  simple_trigger(pg, property_map_put, this, &handle_message::handle_put);
  simple_trigger(pg, property_map_get, this, &handle_message::handle_get);
  simple_trigger(pg, property_map_multiget, this,
                 &handle_message::handle_multiget);
  simple_trigger(pg, property_map_multiget_reply, this,
                 &handle_message::handle_multiget_reply);
  simple_trigger(pg, property_map_multiput, this,
                 &handle_message::handle_multiput);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void
PBGL_DISTRIB_PMAP
::on_synchronize::operator()()
{
  int stage=0; // we only get called at the start now
  shared_ptr<data_t> data(data_ptr);
  BOOST_ASSERT(data);

  // Determine in which stage backward consistency messages should be sent.
  int backward_stage = -1;
  if (data->model & cm_backward) {
    if (data->model & cm_flush) backward_stage = 1;
    else backward_stage = 0;
  }

  // Flush results in first stage
  if (stage == 0 && data->model & cm_flush)
    data->flush();

  // Backward consistency
  if (stage == backward_stage && !(data->model & (cm_clear | cm_reset)))
    data->refresh_ghost_cells();

  // Optionally clear results
  if (data->model & cm_clear)
    data->clear();

  // Optionally reset results
  if (data->model & cm_reset) {
    if (data->reset) ((*data).*data->reset)();
  }
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void
PBGL_DISTRIB_PMAP::set_consistency_model(int model)
{
  data->model = model;

  bool need_on_synchronize = (model != cm_forward);

  // Backward consistency is a two-stage process.
  if (model & cm_backward) {
    // For backward consistency to work, we absolutely cannot throw
    // away any ghost cells.
    data->max_ghost_cells = 0;
  }

  // attach the on_synchronize handler.
  if (need_on_synchronize)
    data->process_group.replace_on_synchronize_handler(on_synchronize(data));
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void
PBGL_DISTRIB_PMAP::set_max_ghost_cells(std::size_t max_ghost_cells)
{
  if ((data->model & cm_backward) && max_ghost_cells > 0)
      boost::throw_exception(std::runtime_error("distributed_property_map::set_max_ghost_cells: "
                                                "cannot limit ghost-cell usage with a backward "
                                                "consistency model"));

  if (max_ghost_cells == 1)
    // It is not safe to have only 1 ghost cell; the cell() method
    // will fail.
    max_ghost_cells = 2;

  data->max_ghost_cells = max_ghost_cells;
  prune_ghost_cells();
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void PBGL_DISTRIB_PMAP::clear()
{
  data->clear();
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void PBGL_DISTRIB_PMAP::data_t::clear()
{
  ghost_cells->clear();
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void PBGL_DISTRIB_PMAP::reset()
{
  if (data->reset) ((*data).*data->reset)();
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void PBGL_DISTRIB_PMAP::flush()
{
  data->flush();
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void PBGL_DISTRIB_PMAP::data_t::refresh_ghost_cells()
{
  using boost::get;

  std::vector<std::vector<key_type> > keys;
  keys.resize(num_processes(process_group));

  // Collect the set of keys for which we will request values
  for (iterator i = ghost_cells->begin(); i != ghost_cells->end(); ++i)
    keys[get(global, i->first).first].push_back(i->first);

  // Send multiget requests to each of the other processors
  typedef typename ProcessGroup::process_size_type process_size_type;
  process_size_type n = num_processes(process_group);
  process_id_type id = process_id(process_group);
  for (process_size_type p = (id + 1) % n ; p != id ; p = (p + 1) % n) {
    if (!keys[p].empty())
      send(process_group, p, property_map_multiget, keys[p]);
  }
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void PBGL_DISTRIB_PMAP::data_t::flush()
{
  using boost::get;

  int n = num_processes(process_group);
  std::vector<std::vector<unsafe_pair<local_key_type, value_type> > > values;
  values.resize(n);

  // Collect all of the flushed values
  for (iterator i = ghost_cells->begin(); i != ghost_cells->end(); ++i) {
    std::pair<int, local_key_type> g = get(global, i->first);
    values[g.first].push_back(std::make_pair(g.second, i->second));
  }

  // Transmit flushed values
  for (int p = 0; p < n; ++p) {
    if (!values[p].empty())
      send(process_group, p, property_map_multiput, values[p]);
  }
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void PBGL_DISTRIB_PMAP::do_synchronize()
{
  if (data->model & cm_backward) {
    synchronize(data->process_group);
    return;
  }

  // Request refreshes of the values of our ghost cells
  data->refresh_ghost_cells();

  // Allows all of the multigets to get to their destinations
  synchronize(data->process_group);

  // Allows all of the multiget responses to get to their destinations
  synchronize(data->process_group);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
template<typename Resolver>
void PBGL_DISTRIB_PMAP::data_t::do_reset()
{
  Resolver* resolver = get_default_value.template target<Resolver>();
  BOOST_ASSERT(resolver);

  for (iterator i = ghost_cells->begin(); i != ghost_cells->end(); ++i)
    const_cast<value_type&>(i->second) = (*resolver)(i->first);
}

} } // end namespace boost::parallel


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

// The placement of this #include probably looks very odd relative to
// the #ifndef/#define pair below. However, this placement is
// extremely important to allow the various property map headers to be
// included in any order.
#include <boost/property_map/property_map.hpp>

#ifndef BOOST_PARALLEL_LOCAL_PROPERTY_MAP_HPP
#define BOOST_PARALLEL_LOCAL_PROPERTY_MAP_HPP

#include <boost/assert.hpp>

namespace boost {
  /** Property map that accesses an underlying, local property map
   * using a subset of the global keys.
   */
  template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
  class local_property_map
  {
    typedef typename property_traits<GlobalMap>::value_type owner_local_pair;

  public:
    typedef ProcessGroup                                   process_group_type;
    typedef typename property_traits<StorageMap>::value_type value_type;
    typedef typename property_traits<GlobalMap>::key_type key_type;
    typedef typename property_traits<StorageMap>::reference  reference;
    typedef typename property_traits<StorageMap>::category   category;

    local_property_map() { }

    local_property_map(const ProcessGroup& process_group,
                       const GlobalMap& global, const StorageMap& storage)
      : process_group_(process_group), global_(global), storage(storage) { }

    reference operator[](const key_type& key)
    {
      owner_local_pair p = get(global_, key);
      BOOST_ASSERT(p.first == process_id(process_group_));
      return storage[p.second];
    }

    GlobalMap& global() const { return global_; }
    StorageMap& base() const { return storage; }

    ProcessGroup&       process_group()       { return process_group_; }
    const ProcessGroup& process_group() const { return process_group_; }

  private:
    ProcessGroup process_group_;
    mutable GlobalMap global_;
    mutable StorageMap storage;
  };

  template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
  inline
  typename local_property_map<ProcessGroup, GlobalMap, StorageMap>::reference
  get(const local_property_map<ProcessGroup, GlobalMap, StorageMap>& pm,
      typename local_property_map<ProcessGroup, GlobalMap, StorageMap>::key_type
        const & key)

  {
    typename property_traits<GlobalMap>::value_type p = get(pm.global(), key);
    return get(pm.base(), p.second);
  }

  template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
  inline void
  put(const local_property_map<ProcessGroup, GlobalMap, StorageMap>& pm,
      typename local_property_map<ProcessGroup, GlobalMap, StorageMap>
                 ::key_type const & key,
      typename local_property_map<ProcessGroup, GlobalMap, StorageMap>
                 ::value_type const& v)
  {
    typename property_traits<GlobalMap>::value_type p = get(pm.global(), key);
    BOOST_ASSERT(p.first == process_id(pm.process_group()));
    put(pm.base(), p.second, v);
  }
} // end namespace boost
#endif // BOOST_PARALLEL_LOCAL_PROPERTY_MAP_HPP

license: mit


code:
//  (C) Copyright Jeremy Siek 1999-2001.
//  Copyright (C) 2006 Trustees of Indiana University
//  Authors: Douglas Gregor and Jeremy 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)

//  See http://www.boost.org/libs/property_map for documentation.

#ifndef BOOST_PROPERTY_MAP_PARALLEL_PROPERTY_MAPS_HPP
#define BOOST_PROPERTY_MAP_PARALLEL_PROPERTY_MAPS_HPP

// Parallel property maps moved over from <boost/property_map/property_map.hpp>
// as part of refactoring out all parallel code from sequential property map
// library.

#include <boost/assert.hpp>
#include <boost/config.hpp>
#include <boost/static_assert.hpp>
#include <cstddef>
#include <boost/detail/iterator.hpp>
#include <boost/concept_archetype.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/or.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/has_xxx.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/property_map/property_map.hpp>

#include <boost/property_map/parallel/distributed_property_map.hpp>
#include <boost/property_map/parallel/local_property_map.hpp>

namespace boost {
/** Distributed iterator property map.
 *
 * This specialization of @ref iterator_property_map builds a
 * distributed iterator property map given the local index maps
 * generated by distributed graph types that automatically have index
 * properties.
 *
 * This specialization is useful when creating external distributed
 * property maps via the same syntax used to create external
 * sequential property maps.
 */
template<typename RandomAccessIterator, typename ProcessGroup,
         typename GlobalMap, typename StorageMap,
         typename ValueType, typename Reference>
class iterator_property_map
        <RandomAccessIterator,
         local_property_map<ProcessGroup, GlobalMap, StorageMap>,
         ValueType, Reference>
  : public parallel::distributed_property_map
             <ProcessGroup,
              GlobalMap,
              iterator_property_map<RandomAccessIterator, StorageMap,
                                    ValueType, Reference> >
{
  typedef iterator_property_map<RandomAccessIterator, StorageMap,
                                ValueType, Reference> local_iterator_map;

  typedef parallel::distributed_property_map<ProcessGroup, GlobalMap,
                                             local_iterator_map> inherited;

  typedef local_property_map<ProcessGroup, GlobalMap, StorageMap>
    index_map_type;
  typedef iterator_property_map self_type;

public:
  iterator_property_map() { }

  iterator_property_map(RandomAccessIterator cc, const index_map_type& id)
    : inherited(id.process_group(), id.global(),
                local_iterator_map(cc, id.base())) { }
};

/** Distributed iterator property map.
 *
 * This specialization of @ref iterator_property_map builds a
 * distributed iterator property map given a distributed index
 * map. Only the local portion of the distributed index property map
 * is utilized.
 *
 * This specialization is useful when creating external distributed
 * property maps via the same syntax used to create external
 * sequential property maps.
 */
template<typename RandomAccessIterator, typename ProcessGroup,
         typename GlobalMap, typename StorageMap,
         typename ValueType, typename Reference>
class iterator_property_map<
        RandomAccessIterator,
        parallel::distributed_property_map<ProcessGroup,GlobalMap,StorageMap>,
        ValueType, Reference
      >
  : public parallel::distributed_property_map
             <ProcessGroup,
              GlobalMap,
              iterator_property_map<RandomAccessIterator, StorageMap,
                                    ValueType, Reference> >
{
  typedef iterator_property_map<RandomAccessIterator, StorageMap,
                                ValueType, Reference> local_iterator_map;

  typedef parallel::distributed_property_map<ProcessGroup, GlobalMap,
                                             local_iterator_map> inherited;

  typedef parallel::distributed_property_map<ProcessGroup, GlobalMap,
                                             StorageMap>
    index_map_type;

public:
  iterator_property_map() { }

  iterator_property_map(RandomAccessIterator cc, const index_map_type& id)
    : inherited(id.process_group(), id.global(),
                local_iterator_map(cc, id.base())) { }
};

namespace parallel {
// Generate an iterator property map with a specific kind of ghost
// cells
template<typename RandomAccessIterator, typename ProcessGroup,
         typename GlobalMap, typename StorageMap>
distributed_property_map<ProcessGroup,
                         GlobalMap,
                         iterator_property_map<RandomAccessIterator,
                                               StorageMap> >
make_iterator_property_map(RandomAccessIterator cc,
                           local_property_map<ProcessGroup, GlobalMap,
                                              StorageMap> index_map)
{
  typedef distributed_property_map<
            ProcessGroup, GlobalMap,
            iterator_property_map<RandomAccessIterator, StorageMap> >
    result_type;
  return result_type(index_map.process_group(), index_map.global(),
                     make_iterator_property_map(cc, index_map.base()));
}

} // end namespace parallel

/** Distributed safe iterator property map.
 *
 * This specialization of @ref safe_iterator_property_map builds a
 * distributed iterator property map given the local index maps
 * generated by distributed graph types that automatically have index
 * properties.
 *
 * This specialization is useful when creating external distributed
 * property maps via the same syntax used to create external
 * sequential property maps.
 */
template<typename RandomAccessIterator, typename ProcessGroup,
         typename GlobalMap, typename StorageMap, typename ValueType,
         typename Reference>
class safe_iterator_property_map
        <RandomAccessIterator,
         local_property_map<ProcessGroup, GlobalMap, StorageMap>,
         ValueType, Reference>
  : public parallel::distributed_property_map
             <ProcessGroup,
              GlobalMap,
              safe_iterator_property_map<RandomAccessIterator, StorageMap,
                                         ValueType, Reference> >
{
  typedef safe_iterator_property_map<RandomAccessIterator, StorageMap,
                                     ValueType, Reference> local_iterator_map;

  typedef parallel::distributed_property_map<ProcessGroup, GlobalMap,
                                             local_iterator_map> inherited;

  typedef local_property_map<ProcessGroup, GlobalMap, StorageMap> index_map_type;

public:
  safe_iterator_property_map() { }

  safe_iterator_property_map(RandomAccessIterator cc, std::size_t n,
                             const index_map_type& id)
    : inherited(id.process_group(), id.global(),
                local_iterator_map(cc, n, id.base())) { }
};

/** Distributed safe iterator property map.
 *
 * This specialization of @ref safe_iterator_property_map builds a
 * distributed iterator property map given a distributed index
 * map. Only the local portion of the distributed index property map
 * is utilized.
 *
 * This specialization is useful when creating external distributed
 * property maps via the same syntax used to create external
 * sequential property maps.
 */
template<typename RandomAccessIterator, typename ProcessGroup,
         typename GlobalMap, typename StorageMap,
         typename ValueType, typename Reference>
class safe_iterator_property_map<
        RandomAccessIterator,
        parallel::distributed_property_map<ProcessGroup,GlobalMap,StorageMap>,
        ValueType, Reference>
  : public parallel::distributed_property_map
             <ProcessGroup,
              GlobalMap,
              safe_iterator_property_map<RandomAccessIterator, StorageMap,
                                         ValueType, Reference> >
{
  typedef safe_iterator_property_map<RandomAccessIterator, StorageMap,
                                     ValueType, Reference> local_iterator_map;

  typedef parallel::distributed_property_map<ProcessGroup, GlobalMap,
                                             local_iterator_map> inherited;

  typedef parallel::distributed_property_map<ProcessGroup, GlobalMap,
                                             StorageMap>
    index_map_type;

public:
  safe_iterator_property_map() { }

  safe_iterator_property_map(RandomAccessIterator cc, std::size_t n,
                             const index_map_type& id)
    : inherited(id.process_group(), id.global(),
                local_iterator_map(cc, n, id.base())) { }
};

}

#include <boost/property_map/vector_property_map.hpp>

#endif /* BOOST_PROPERTY_MAP_PARALLEL_PROPERTY_MAPS_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_PROPERTY_MAP_PARALLEL_PROCESS_GROUP_HPP
#define BOOST_PROPERTY_MAP_PARALLEL_PROCESS_GROUP_HPP

#include <cstdlib>
#include <utility>

namespace boost { namespace parallel {

/**
 * A special type used as a flag to a process group constructor that
 * indicates that the copy of a process group will represent a new
 * distributed data structure.
 */
struct attach_distributed_object { };

/**
 * Describes the context in which a trigger is being invoked to
 * receive a message.
 */
enum trigger_receive_context {
  /// No trigger is active at this time.
  trc_none,
  /// The trigger is being invoked during synchronization, at the end
  /// of a superstep.
  trc_in_synchronization,
  /// The trigger is being invoked as an "early" receive of a message
  /// that was sent through the normal "send" operations to be
  /// received by the end of the superstep, but the process group sent
  /// the message earlier to clear its buffers.
  trc_early_receive,
  /// The trigger is being invoked for an out-of-band message, which
  /// must be handled immediately.
  trc_out_of_band,
  /// The trigger is being invoked for an out-of-band message, which
  /// must be handled immediately and has alredy been received by
  /// an MPI_IRecv call.
  trc_irecv_out_of_band
};

// Process group tags
struct process_group_tag {};
struct linear_process_group_tag : virtual process_group_tag {};
struct messaging_process_group_tag : virtual process_group_tag {};
struct immediate_process_group_tag : virtual messaging_process_group_tag {};
struct bsp_process_group_tag : virtual messaging_process_group_tag {};
struct batch_process_group_tag : virtual messaging_process_group_tag {};
struct locking_process_group_tag : virtual process_group_tag {};
struct spawning_process_group_tag : virtual process_group_tag {};

struct process_group_archetype
{
  typedef int process_id_type;
};

void wait(process_group_archetype&);
void synchronize(process_group_archetype&);
int process_id(const process_group_archetype&);
int num_processes(const process_group_archetype&);

template<typename T> void send(process_group_archetype&, int, int, const T&);

template<typename T>
process_group_archetype::process_id_type
receive(const process_group_archetype& pg,
        process_group_archetype::process_id_type source, int tag, T& value);

template<typename T>
std::pair<process_group_archetype::process_id_type, std::size_t>
receive(const process_group_archetype& pg, int tag, T values[], std::size_t n);

template<typename T>
std::pair<process_group_archetype::process_id_type, std::size_t>
receive(const process_group_archetype& pg,
        process_group_archetype::process_id_type source, int tag, T values[],
        std::size_t n);

} } // end namespace boost::parallel

namespace boost { namespace graph { namespace distributed {
  using boost::parallel::trigger_receive_context;
  using boost::parallel::trc_early_receive;
  using boost::parallel::trc_out_of_band;
  using boost::parallel::trc_irecv_out_of_band;
  using boost::parallel::trc_in_synchronization;
  using boost::parallel::trc_none;
  using boost::parallel::attach_distributed_object;
} } } // end namespace boost::graph::distributed

#endif // BOOST_PROPERTY_MAP_PARALLEL_PROCESS_GROUP_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.

#ifndef BOOST_PROPERTY_MAP_PARALLEL_SIMPLE_TRIGGER_HPP
#define BOOST_PROPERTY_MAP_PARALLEL_SIMPLE_TRIGGER_HPP

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

namespace boost { namespace parallel {

namespace detail {

/**
 * INTERNAL ONLY
 *
 * The actual function object that bridges from the normal trigger
 * interface to the simplified interface. This is the equivalent of
 * bind(pmf, self, _1, _2, _3, _4), but without the compile-time
 * overhead of bind.
 */
template<typename Class, typename T, typename Result>
class simple_trigger_t
{
public:
  simple_trigger_t(Class* self,
                   Result (Class::*pmf)(int, int, const T&,
                                        trigger_receive_context))
    : self(self), pmf(pmf) { }

  Result
  operator()(int source, int tag, const T& data,
             trigger_receive_context context) const
  {
    return (self->*pmf)(source, tag, data, context);
  }

private:
  Class* self;
  Result (Class::*pmf)(int, int, const T&, trigger_receive_context);
};

} // end namespace detail

/**
 * Simplified trigger interface that reduces the amount of code
 * required to connect a process group trigger to a handler that is
 * just a bound member function.
 *
 * INTERNAL ONLY
 */
template<typename ProcessGroup, typename Class, typename T>
inline void
simple_trigger(ProcessGroup& pg, int tag, Class* self,
               void (Class::*pmf)(int source, int tag, const T& data,
                                  trigger_receive_context context), int)
{
  pg.template trigger<T>(tag,
                         detail::simple_trigger_t<Class, T, void>(self, pmf));
}

/**
 * Simplified trigger interface that reduces the amount of code
 * required to connect a process group trigger with a reply to a
 * handler that is just a bound member function.
 *
 * INTERNAL ONLY
 */
template<typename ProcessGroup, typename Class, typename T, typename Result>
inline void
simple_trigger(ProcessGroup& pg, int tag, Class* self,
               Result (Class::*pmf)(int source, int tag, const T& data,
                                    trigger_receive_context context), long)
{
  pg.template trigger_with_reply<T>
    (tag, detail::simple_trigger_t<Class, T, Result>(self, pmf));
}

/**
 * Simplified trigger interface that reduces the amount of code
 * required to connect a process group trigger to a handler that is
 * just a bound member function.
 */
template<typename ProcessGroup, typename Class, typename T, typename Result>
inline void
simple_trigger(ProcessGroup& pg, int tag, Class* self,
               Result (Class::*pmf)(int source, int tag, const T& data,
                                    trigger_receive_context context))
{
        // We pass 0 (an int) to help VC++ disambiguate calls to simple_trigger
        // with Result=void.
        simple_trigger(pg, tag, self, pmf, 0);
}

} } // end namespace boost::parallel

namespace boost { namespace graph { namespace parallel { using boost::parallel::simple_trigger; } } }

#endif // BOOST_PROPERTY_MAP_PARALLEL_SIMPLE_TRIGGER_HPP


code:
// Copyright (C) 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 the "unsafe_serialize" routine, which transforms
// types they may not be serializable (such as void*) into
// serializable equivalents.
#ifndef BOOST_PROPERTY_MAP_UNSAFE_SERIALIZE_HPP
#define BOOST_PROPERTY_MAP_UNSAFE_SERIALIZE_HPP

#include <boost/mpi/datatype.hpp>
#include <boost/serialization/is_bitwise_serializable.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/if.hpp>
#include <boost/cstdint.hpp>
#include <boost/static_assert.hpp>
#include <boost/type_traits.hpp>
#include <utility>

BOOST_IS_BITWISE_SERIALIZABLE(void*)
namespace boost { namespace mpi {
    template<> struct is_mpi_datatype<void*> : mpl::true_ { };
} } // end namespace boost::mpi

namespace boost {
  typedef mpl::if_c<(sizeof(int) == sizeof(void*)),
                    int,
                    mpl::if_c<(sizeof(long) == sizeof(void*)),
                              long,
                              mpl::if_c<(sizeof(void*) <= sizeof(boost::intmax_t)),
                                        boost::intmax_t,
                                        void>::type
                              >::type
                    >::type ptr_serialize_type;

  BOOST_STATIC_ASSERT ((!boost::is_void<ptr_serialize_type>::value));

  template<typename T> inline T& unsafe_serialize(T& x) { return x; }

  inline ptr_serialize_type& unsafe_serialize(void*& x)
  { return reinterpret_cast<ptr_serialize_type&>(x); }

  // Force Boost.MPI to serialize a void* like a ptr_serialize_type
  namespace mpi {
    template<> inline MPI_Datatype get_mpi_datatype<void*>(void* const& x)
    {
      return get_mpi_datatype<ptr_serialize_type>();
    }
  }

  template<typename T, typename U>
  struct unsafe_pair
  {
    unsafe_pair() { }
    unsafe_pair(const T& t, const U& u) : first(t), second(u) { }
    unsafe_pair(const std::pair<T, U>& p) : first(p.first), second(p.second) { }
    T first;
    U second;

    template<typename Archiver>
    void serialize(Archiver& ar, const unsigned /*version*/)
    {
      ar & unsafe_serialize(first) & unsafe_serialize(second);
    }
  };

  template<typename T, typename U>
  bool operator<(unsafe_pair<T,U> const& x, unsafe_pair<T,U> const& y)
  {
    return std::make_pair(x.first, x.second) <
      std::make_pair(y.first, y.second);
  }

} // end namespace boost

#endif // BOOST_PROPERTY_MAP_UNSAFE_SERIALIZE_HPP


code:
// Copyright (C) Vladimir Prus 2003.
// 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)
//
// See http://www.boost.org/libs/graph/vector_property_map.html for
// documentation.
//

#ifndef BOOST_PROPERTY_MAP_PARALLEL_VECTOR_PROPERTY_MAP_HPP_VP_2003_03_04
#define BOOST_PROPERTY_MAP_PARALLEL_VECTOR_PROPERTY_MAP_HPP_VP_2003_03_04

#include <boost/property_map/property_map.hpp>
#include <boost/shared_ptr.hpp>
#include <vector>
#include <boost/property_map/parallel/distributed_property_map.hpp>
#include <boost/property_map/parallel/local_property_map.hpp>

namespace boost {

/** Distributed vector property map.
 *
 * This specialization of @ref vector_property_map builds a
 * distributed vector property map given the local index maps
 * generated by distributed graph types that automatically have index
 * properties.
 *
 * This specialization is useful when creating external distributed
 * property maps via the same syntax used to create external
 * sequential property maps.
 */
template<typename T, typename ProcessGroup, typename GlobalMap,
         typename StorageMap>
class vector_property_map<T,
                          local_property_map<ProcessGroup, GlobalMap,
                                             StorageMap> >
  : public parallel::distributed_property_map<
             ProcessGroup, GlobalMap, vector_property_map<T, StorageMap> >
{
  typedef vector_property_map<T, StorageMap> local_iterator_map;

  typedef parallel::distributed_property_map<ProcessGroup, GlobalMap,
                                             local_iterator_map> inherited;

  typedef local_property_map<ProcessGroup, GlobalMap, StorageMap> index_map_type;

public:
  vector_property_map(const index_map_type& index = index_map_type())
    : inherited(index.process_group(), index.global(),
                local_iterator_map(index.base())) { }

  vector_property_map(unsigned inital_size,
                      const index_map_type& index = index_map_type())
    : inherited(index.process_group(),  index.global(),
                local_iterator_map(inital_size, index.base())) { }
};

/** Distributed vector property map.
 *
 * This specialization of @ref vector_property_map builds a
 * distributed vector property map given the local index maps
 * generated by distributed graph types that automatically have index
 * properties.
 *
 * This specialization is useful when creating external distributed
 * property maps via the same syntax used to create external
 * sequential property maps.
 */
template<typename T, typename ProcessGroup, typename GlobalMap,
         typename StorageMap>
class vector_property_map<
        T,
        parallel::distributed_property_map<
          ProcessGroup,
          GlobalMap,
          StorageMap
        >
      >
  : public parallel::distributed_property_map<
             ProcessGroup, GlobalMap, vector_property_map<T, StorageMap> >
{
  typedef vector_property_map<T, StorageMap> local_iterator_map;

  typedef parallel::distributed_property_map<ProcessGroup, GlobalMap,
                                             local_iterator_map> inherited;

  typedef parallel::distributed_property_map<ProcessGroup, GlobalMap,
                                             StorageMap>
    index_map_type;

public:
  vector_property_map(const index_map_type& index = index_map_type())
    : inherited(index.process_group(), index.global(),
                local_iterator_map(index.base())) { }

  vector_property_map(unsigned inital_size,
                      const index_map_type& index = index_map_type())
    : inherited(index.process_group(), index.global(),
                local_iterator_map(inital_size, index.base())) { }
};

}

#endif // BOOST_PROPERTY_MAP_PARALLEL_VECTOR_PROPERTY_MAP_HPP_VP_2003_03_04


code:
//  (C) Copyright Jeremy Siek 1999-2001.
//  Copyright (C) 2006 Trustees of Indiana University
//  Authors: Douglas Gregor and Jeremy 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)

//  See http://www.boost.org/libs/property_map for documentation.

#ifndef BOOST_PROPERTY_MAP_HPP
#define BOOST_PROPERTY_MAP_HPP

#include <boost/assert.hpp>
#include <boost/config.hpp>
#include <boost/static_assert.hpp>
#include <cstddef>
#include <boost/detail/iterator.hpp>
#include <boost/concept/assert.hpp>
#include <boost/concept_check.hpp>
#include <boost/concept_archetype.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/or.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/has_xxx.hpp>
#include <boost/type_traits/is_same.hpp>

namespace boost {

  //=========================================================================
  // property_traits class

  BOOST_MPL_HAS_XXX_TRAIT_DEF(key_type)
  BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
  BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
  BOOST_MPL_HAS_XXX_TRAIT_DEF(category)

  template<class PA>
  struct is_property_map :
    boost::mpl::and_<
      has_key_type<PA>,
      has_value_type<PA>,
      has_reference<PA>,
      has_category<PA>
    >
  {};

  template <typename PA>
  struct default_property_traits {
    typedef typename PA::key_type key_type;
    typedef typename PA::value_type value_type;
    typedef typename PA::reference reference;
    typedef typename PA::category   category;
  };

  struct null_property_traits {};

  template <typename PA>
  struct property_traits :
    boost::mpl::if_<is_property_map<PA>,
      default_property_traits<PA>,
      null_property_traits>::type
  {};

#if 0
  template <typename PA>
  struct property_traits {
    typedef typename PA::key_type key_type;
    typedef typename PA::value_type value_type;
    typedef typename PA::reference reference;
    typedef typename PA::category   category;
  };
#endif

  //=========================================================================
  // property_traits category tags

  namespace detail {
    enum ePropertyMapID { READABLE_PA, WRITABLE_PA,
                          READ_WRITE_PA, LVALUE_PA, OP_BRACKET_PA,
                          RAND_ACCESS_ITER_PA, LAST_PA };
  }
  struct readable_property_map_tag { enum { id = detail::READABLE_PA }; };
  struct writable_property_map_tag { enum { id = detail::WRITABLE_PA }; };
  struct read_write_property_map_tag :
    public readable_property_map_tag,
    public writable_property_map_tag
  { enum { id = detail::READ_WRITE_PA }; };

  struct lvalue_property_map_tag : public read_write_property_map_tag
  { enum { id = detail::LVALUE_PA }; };

  //=========================================================================
  // property_traits specialization for pointers

  template <class T>
  struct property_traits<T*> {
    // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated");
    typedef T value_type;
    typedef value_type& reference;
    typedef std::ptrdiff_t key_type;
    typedef lvalue_property_map_tag category;
  };
  template <class T>
  struct property_traits<const T*> {
    // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated");
    typedef T value_type;
    typedef const value_type& reference;
    typedef std::ptrdiff_t key_type;
    typedef lvalue_property_map_tag category;
  };

#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
  // MSVC doesn't have Koenig lookup, so the user has to
  // do boost::get() anyways, and the using clause
  // doesn't really work for MSVC.
} // namespace boost
#endif

  // These need to go in global namespace because Koenig
  // lookup does not apply to T*.

  // V must be convertible to T
  template <class T, class V>
  inline void put(T* pa, std::ptrdiff_t k, const V& val) { pa[k] = val;  }

  template <class T>
  inline const T& get(const T* pa, std::ptrdiff_t k) { return pa[k]; }

#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
namespace boost {
  using ::put;
  using ::get;
#endif

  //=========================================================================
  // concept checks for property maps

  template <class PMap, class Key>
  struct ReadablePropertyMapConcept
  {
    typedef typename property_traits<PMap>::key_type key_type;
    typedef typename property_traits<PMap>::reference reference;
    typedef typename property_traits<PMap>::category Category;
    typedef boost::readable_property_map_tag ReadableTag;
    void constraints() {
      BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, ReadableTag>));

      val = get(pmap, k);
    }
    PMap pmap;
    Key k;
    typename property_traits<PMap>::value_type val;
  };
  template <typename KeyArchetype, typename ValueArchetype>
  struct readable_property_map_archetype {
    typedef KeyArchetype key_type;
    typedef ValueArchetype value_type;
    typedef convertible_to_archetype<ValueArchetype> reference;
    typedef readable_property_map_tag category;
  };
  template <typename K, typename V>
  const typename readable_property_map_archetype<K,V>::reference&
  get(const readable_property_map_archetype<K,V>&,
      const typename readable_property_map_archetype<K,V>::key_type&)
  {
    typedef typename readable_property_map_archetype<K,V>::reference R;
    return static_object<R>::get();
  }

  template <class PMap, class Key>
  struct WritablePropertyMapConcept
  {
    typedef typename property_traits<PMap>::key_type key_type;
    typedef typename property_traits<PMap>::category Category;
    typedef boost::writable_property_map_tag WritableTag;
    void constraints() {
      BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, WritableTag>));
      put(pmap, k, val);
    }
    PMap pmap;
    Key k;
    typename property_traits<PMap>::value_type val;
  };
  template <typename KeyArchetype, typename ValueArchetype>
  struct writable_property_map_archetype {
    typedef KeyArchetype key_type;
    typedef ValueArchetype value_type;
    typedef void reference;
    typedef writable_property_map_tag category;
  };
  template <typename K, typename V>
  void put(const writable_property_map_archetype<K,V>&,
           const typename writable_property_map_archetype<K,V>::key_type&,
           const typename writable_property_map_archetype<K,V>::value_type&) { }

  template <class PMap, class Key>
  struct ReadWritePropertyMapConcept
  {
    typedef typename property_traits<PMap>::category Category;
    typedef boost::read_write_property_map_tag ReadWriteTag;
    void constraints() {
      BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<PMap, Key>));
      BOOST_CONCEPT_ASSERT((WritablePropertyMapConcept<PMap, Key>));
      BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, ReadWriteTag>));
    }
  };
  template <typename KeyArchetype, typename ValueArchetype>
  struct read_write_property_map_archetype
    : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
      public writable_property_map_archetype<KeyArchetype, ValueArchetype>
  {
    typedef KeyArchetype key_type;
    typedef ValueArchetype value_type;
    typedef convertible_to_archetype<ValueArchetype> reference;
    typedef read_write_property_map_tag category;
  };

  template <class PMap, class Key>
  struct LvaluePropertyMapConcept
  {
    typedef typename property_traits<PMap>::category Category;
    typedef boost::lvalue_property_map_tag LvalueTag;
    typedef typename property_traits<PMap>::reference reference;

    void constraints() {
      BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<PMap, Key>));
      BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, LvalueTag>));

      typedef typename property_traits<PMap>::value_type value_type;
      BOOST_MPL_ASSERT((boost::mpl::or_<
                          boost::is_same<const value_type&, reference>,
                          boost::is_same<value_type&, reference> >));

      reference ref = pmap[k];
      ignore_unused_variable_warning(ref);
    }
    PMap pmap;
    Key k;
  };
  template <typename KeyArchetype, typename ValueArchetype>
  struct lvalue_property_map_archetype
    : public readable_property_map_archetype<KeyArchetype, ValueArchetype>
  {
    typedef KeyArchetype key_type;
    typedef ValueArchetype value_type;
    typedef const ValueArchetype& reference;
    typedef lvalue_property_map_tag category;
    const value_type& operator[](const key_type&) const {
      return static_object<value_type>::get();
    }
  };

  template <class PMap, class Key>
  struct Mutable_LvaluePropertyMapConcept
  {
    typedef typename property_traits<PMap>::category Category;
    typedef boost::lvalue_property_map_tag LvalueTag;
    typedef typename property_traits<PMap>::reference reference;
    void constraints() {
      BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept<PMap, Key>));
      BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, LvalueTag>));

      typedef typename property_traits<PMap>::value_type value_type;
      BOOST_MPL_ASSERT((boost::is_same<value_type&, reference>));

      reference ref = pmap[k];
      ignore_unused_variable_warning(ref);
    }
    PMap pmap;
    Key k;
  };
  template <typename KeyArchetype, typename ValueArchetype>
  struct mutable_lvalue_property_map_archetype
    : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
      public writable_property_map_archetype<KeyArchetype, ValueArchetype>
  {
    typedef KeyArchetype key_type;
    typedef ValueArchetype value_type;
    typedef ValueArchetype& reference;
    typedef lvalue_property_map_tag category;
    value_type& operator[](const key_type&) const {
      return static_object<value_type>::get();
    }
  };

  template <typename T>
  struct typed_identity_property_map;

  // A helper class for constructing a property map
  // from a class that implements operator[]

  template <class Reference, class LvaluePropertyMap>
  struct put_get_helper { };

  template <class PropertyMap, class Reference, class K>
  inline Reference
  get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
  {
    Reference v = static_cast<const PropertyMap&>(pa)[k];
    return v;
  }
  template <class PropertyMap, class Reference, class K, class V>
  inline void
  put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
  {
    static_cast<const PropertyMap&>(pa)[k] = v;
  }

  //=========================================================================
  // Adapter to turn a RandomAccessIterator into a property map

  template <class RandomAccessIterator,
    class IndexMap
#ifdef BOOST_NO_STD_ITERATOR_TRAITS
    , class T, class R
#else
    , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
    , class R = typename std::iterator_traits<RandomAccessIterator>::reference
#endif
     >
  class iterator_property_map
    : public boost::put_get_helper< R,
        iterator_property_map<RandomAccessIterator, IndexMap,
        T, R> >
  {
  public:
    typedef typename property_traits<IndexMap>::key_type key_type;
    typedef T value_type;
    typedef R reference;
    typedef boost::lvalue_property_map_tag category;

    inline iterator_property_map(
      RandomAccessIterator cc = RandomAccessIterator(),
      const IndexMap& _id = IndexMap() )
      : iter(cc), index(_id) { }
    inline R operator[](key_type v) const { return *(iter + get(index, v)) ; }
  protected:
    RandomAccessIterator iter;
    IndexMap index;
  };

#if !defined BOOST_NO_STD_ITERATOR_TRAITS
  template <class RAIter, class ID>
  inline iterator_property_map<
    RAIter, ID,
    typename std::iterator_traits<RAIter>::value_type,
    typename std::iterator_traits<RAIter>::reference>
  make_iterator_property_map(RAIter iter, ID id) {
    BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>));
    typedef iterator_property_map<
      RAIter, ID,
      typename std::iterator_traits<RAIter>::value_type,
      typename std::iterator_traits<RAIter>::reference> PA;
    return PA(iter, id);
  }
#endif
  template <class RAIter, class Value, class ID>
  inline iterator_property_map<RAIter, ID, Value, Value&>
  make_iterator_property_map(RAIter iter, ID id, Value) {
    BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>));
    typedef iterator_property_map<RAIter, ID, Value, Value&> PMap;
    return PMap(iter, id);
  }

  template <class RandomAccessIterator,
    class IndexMap
#ifdef BOOST_NO_STD_ITERATOR_TRAITS
    , class T, class R
#else
    , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
    , class R = typename std::iterator_traits<RandomAccessIterator>::reference
#endif
     >
  class safe_iterator_property_map
    : public boost::put_get_helper< R,
        safe_iterator_property_map<RandomAccessIterator, IndexMap,
        T, R> >
  {
  public:
    typedef typename property_traits<IndexMap>::key_type key_type;
    typedef T value_type;
    typedef R reference;
    typedef boost::lvalue_property_map_tag category;

    inline safe_iterator_property_map(
      RandomAccessIterator first,
      std::size_t n_ = 0,
      const IndexMap& _id = IndexMap() )
      : iter(first), n(n_), index(_id) { }
    inline safe_iterator_property_map() { }
    inline R operator[](key_type v) const {
      BOOST_ASSERT(get(index, v) < n);
      return *(iter + get(index, v)) ;
    }
    typename property_traits<IndexMap>::value_type size() const { return n; }
  protected:
    RandomAccessIterator iter;
    typename property_traits<IndexMap>::value_type n;
    IndexMap index;
  };

  template <class RAIter, class ID>
  inline safe_iterator_property_map<
    RAIter, ID,
    typename boost::detail::iterator_traits<RAIter>::value_type,
    typename boost::detail::iterator_traits<RAIter>::reference>
  make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id) {
    BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>));
    typedef safe_iterator_property_map<
      RAIter, ID,
      typename boost::detail::iterator_traits<RAIter>::value_type,
      typename boost::detail::iterator_traits<RAIter>::reference> PA;
    return PA(iter, n, id);
  }
  template <class RAIter, class Value, class ID>
  inline safe_iterator_property_map<RAIter, ID, Value, Value&>
  make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id, Value) {
    BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>));
    typedef safe_iterator_property_map<RAIter, ID, Value, Value&> PMap;
    return PMap(iter, n, id);
  }

  //=========================================================================
  // An adaptor to turn a Unique Pair Associative Container like std::map or
  // std::hash_map into an Lvalue Property Map.

  template <typename UniquePairAssociativeContainer>
  class associative_property_map
    : public boost::put_get_helper<
       typename UniquePairAssociativeContainer::value_type::second_type&,
       associative_property_map<UniquePairAssociativeContainer> >
  {
    typedef UniquePairAssociativeContainer C;
  public:
    typedef typename C::key_type key_type;
    typedef typename C::value_type::second_type value_type;
    typedef value_type& reference;
    typedef lvalue_property_map_tag category;
    associative_property_map() : m_c(0) { }
    associative_property_map(C& c) : m_c(&c) { }
    reference operator[](const key_type& k) const {
      return (*m_c)[k];
    }
  private:
    C* m_c;
  };

  template <class UniquePairAssociativeContainer>
  associative_property_map<UniquePairAssociativeContainer>
  make_assoc_property_map(UniquePairAssociativeContainer& c)
  {
    return associative_property_map<UniquePairAssociativeContainer>(c);
  }

  template <typename UniquePairAssociativeContainer>
  class const_associative_property_map
    : public boost::put_get_helper<
       const typename UniquePairAssociativeContainer::value_type::second_type&,
       const_associative_property_map<UniquePairAssociativeContainer> >
  {
    typedef UniquePairAssociativeContainer C;
  public:
    typedef typename C::key_type key_type;
    typedef typename C::value_type::second_type value_type;
    typedef const value_type& reference;
    typedef lvalue_property_map_tag category;
    const_associative_property_map() : m_c(0) { }
    const_associative_property_map(const C& c) : m_c(&c) { }
    reference operator[](const key_type& k) const {
      return m_c->find(k)->second;
    }
  private:
    C const* m_c;
  };

  template <class UniquePairAssociativeContainer>
  const_associative_property_map<UniquePairAssociativeContainer>
  make_assoc_property_map(const UniquePairAssociativeContainer& c)
  {
    return const_associative_property_map<UniquePairAssociativeContainer>(c);
  }

  //=========================================================================
  // A property map that always returns the same object by value.
  //
  template <typename ValueType, typename KeyType = void>
  class static_property_map :
      public
  boost::put_get_helper<ValueType,static_property_map<ValueType> >
  {
    ValueType value;
  public:
    typedef KeyType key_type;
    typedef ValueType value_type;
    typedef ValueType reference;
    typedef readable_property_map_tag category;
    static_property_map(ValueType v) : value(v) {}

    template<typename T>
    inline reference operator[](T) const { return value; }
  };

  template <typename KeyType, typename ValueType>
  static_property_map<ValueType, KeyType>
  make_static_property_map(const ValueType& v) {
    return static_property_map<ValueType, KeyType>(v);
  }

  //=========================================================================
  // A property map that always returns a reference to the same object.
  //
  template <typename KeyType, typename ValueType>
  class ref_property_map :
    public
      boost::put_get_helper<ValueType&,ref_property_map<KeyType,ValueType> >
  {
    ValueType* value;
  public:
    typedef KeyType key_type;
    typedef ValueType value_type;
    typedef ValueType& reference;
    typedef lvalue_property_map_tag category;
    ref_property_map(ValueType& v) : value(&v) {}
    ValueType& operator[](key_type const&) const { return *value; }
  };

  //=========================================================================
  // A generalized identity property map
  template <typename T>
  struct typed_identity_property_map
    : public boost::put_get_helper<T, typed_identity_property_map<T> >
  {
    typedef T key_type;
    typedef T value_type;
    typedef T reference;
    typedef boost::readable_property_map_tag category;

    inline value_type operator[](const key_type& v) const { return v; }
  };

//=========================================================================
  // A property map that applies the identity function to integers
  typedef typed_identity_property_map<std::size_t> identity_property_map;

  //=========================================================================
  // A property map that does not do anything, for
  // when you have to supply a property map, but don't need it.
  namespace detail {
    struct dummy_pmap_reference {
      template <class T>
      dummy_pmap_reference& operator=(const T&) { return *this; }
      operator int() { return 0; }
    };
  }
  class dummy_property_map
    : public boost::put_get_helper<detail::dummy_pmap_reference,
        dummy_property_map  >
  {
  public:
    typedef void key_type;
    typedef int value_type;
    typedef detail::dummy_pmap_reference reference;
    typedef boost::read_write_property_map_tag category;
    inline dummy_property_map() : c(0) { }
    inline dummy_property_map(value_type cc) : c(cc) { }
    inline dummy_property_map(const dummy_property_map& x)
      : c(x.c) { }
    template <class Vertex>
    inline reference operator[](Vertex) const { return reference(); }
   protected:
    value_type c;
  };

  // Convert a Readable property map into a function object
  template <typename PropMap>
  class property_map_function {
    PropMap pm;
    typedef typename property_traits<PropMap>::key_type param_type;
    public:
    explicit property_map_function(const PropMap& pm): pm(pm) {}
    typedef typename property_traits<PropMap>::value_type result_type;
    result_type operator()(const param_type& k) const {return get(pm, k);}
  };

  template <typename PropMap>
  property_map_function<PropMap>
  make_property_map_function(const PropMap& pm) {
    return property_map_function<PropMap>(pm);
  }

} // namespace boost

#ifdef BOOST_GRAPH_USE_MPI
#include <boost/property_map/parallel/parallel_property_maps.hpp>
#endif

#include <boost/property_map/vector_property_map.hpp>

#endif /* BOOST_PROPERTY_MAP_HPP */


code:
//  Copyright (C) 2009 Trustees of Indiana University
//  Authors: Jeremiah Willcock, Andrew Lumsdaine

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

//  See http://www.boost.org/libs/property_map for documentation.

#ifndef BOOST_SHARED_ARRAY_PROPERTY_MAP_HPP
#define BOOST_SHARED_ARRAY_PROPERTY_MAP_HPP

#include <boost/smart_ptr/shared_array.hpp>
#include <boost/property_map/property_map.hpp>

namespace boost {

template <class T, class IndexMap>
class shared_array_property_map
  : public boost::put_get_helper<T&, shared_array_property_map<T, IndexMap> >
{
  public:
  typedef typename property_traits<IndexMap>::key_type key_type;
  typedef T value_type;
  typedef T& reference;
  typedef boost::lvalue_property_map_tag category;

  inline shared_array_property_map(): data(), index() {}

  explicit inline shared_array_property_map(
    size_t n,
    const IndexMap& _id = IndexMap())
  : data(new T[n]), index(_id) {}

  inline T& operator[](key_type v) const {
    return data[get(index, v)];
  }

  private:
  boost::shared_array<T> data;
  IndexMap index;
};

template <class T, class IndexMap>
shared_array_property_map<T, IndexMap>
make_shared_array_property_map(size_t n, const T&, const IndexMap& index) {
  return shared_array_property_map<T, IndexMap>(n, index);
}

} // end namespace boost

#endif // BOOST_SHARED_ARRAY_PROPERTY_MAP_HPP


code:
// Copyright (C) Vladimir Prus 2003.
// 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)
//
// See http://www.boost.org/libs/graph/vector_property_map.html for
// documentation.
//

#ifndef VECTOR_PROPERTY_MAP_HPP_VP_2003_03_04
#define VECTOR_PROPERTY_MAP_HPP_VP_2003_03_04

#include <boost/property_map/property_map.hpp>
#include <boost/shared_ptr.hpp>
#include <vector>

namespace boost {
    template<typename T, typename IndexMap = identity_property_map>
    class vector_property_map
        : public boost::put_get_helper<
              typename std::iterator_traits<
                  typename std::vector<T>::iterator >::reference,
              vector_property_map<T, IndexMap> >
    {
    public:
        typedef typename property_traits<IndexMap>::key_type  key_type;
        typedef T value_type;
        typedef typename std::iterator_traits<
            typename std::vector<T>::iterator >::reference reference;
        typedef boost::lvalue_property_map_tag category;

        vector_property_map(const IndexMap& index = IndexMap())
        : store(new std::vector<T>()), index(index)
        {}

        vector_property_map(unsigned initial_size,
                            const IndexMap& index = IndexMap())
        : store(new std::vector<T>(initial_size)), index(index)
        {}

        typename std::vector<T>::iterator storage_begin()
        {
            return store->begin();
        }

        typename std::vector<T>::iterator storage_end()
        {
            return store->end();
        }

        typename std::vector<T>::const_iterator storage_begin() const
        {
            return store->begin();
        }

        typename std::vector<T>::const_iterator storage_end() const
        {
            return store->end();
        }

        IndexMap&       get_index_map()       { return index; }
        const IndexMap& get_index_map() const { return index; }

    public:
        // Copy ctor absent, default semantics is OK.
        // Assignment operator absent, default semantics is OK.
        // CONSIDER: not sure that assignment to 'index' is correct.

        reference operator[](const key_type& v) const {
            typename property_traits<IndexMap>::value_type i = get(index, v);
            if (static_cast<unsigned>(i) >= store->size()) {
                store->resize(i + 1, T());
            }
            return (*store)[i];
        }
    private:
        // Conceptually, we have a vector of infinite size. For practical
        // purposes, we start with an empty vector and grow it as needed.
        // Note that we cannot store pointer to vector here -- we cannot
        // store pointer to data, because if copy of property map resizes
        // the vector, the pointer to data will be invalidated.
        // I wonder if class 'pmap_ref' is simply needed.
        shared_ptr< std::vector<T> > store;
        IndexMap index;
    };

    template<typename T, typename IndexMap>
    vector_property_map<T, IndexMap>
    make_vector_property_map(IndexMap index)
    {
        return vector_property_map<T, IndexMap>(index);
    }
}

#ifdef BOOST_GRAPH_USE_MPI
#include <boost/property_map/parallel/vector_property_map.hpp>
#endif

#endif


code:
// ----------------------------------------------------------------------------
// Copyright (C) 2002-2006 Marcin Kalicinski
// Copyright (C) 2009 Sebastian Redl
//
// 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)
//
// For more information, see www.boost.org
// ----------------------------------------------------------------------------
#ifndef BOOST_PROPERTY_TREE_DETAIL_EXCEPTIONS_IMPLEMENTATION_HPP_INCLUDED
#define BOOST_PROPERTY_TREE_DETAIL_EXCEPTIONS_IMPLEMENTATION_HPP_INCLUDED

namespace boost { namespace property_tree
{

    namespace detail
    {

        // Helper for preparing what string in ptree_bad_path exception
        template<class P> inline
        std::string prepare_bad_path_what(const std::string &what,
                                          const P &path)
        {
            return what + " (" + path.dump() + ")";
        }

    }

    ///////////////////////////////////////////////////////////////////////////
    // ptree_error

    inline ptree_error::ptree_error(const std::string &w):
        std::runtime_error(w)
    {
    }

    inline ptree_error::~ptree_error() throw()
    {
    }

    ///////////////////////////////////////////////////////////////////////////
    // ptree_bad_data

    template<class D> inline
    ptree_bad_data::ptree_bad_data(const std::string &w, const D &d):
        ptree_error(w), m_data(d)
    {
    }

    inline ptree_bad_data::~ptree_bad_data() throw()
    {
    }

    template<class D> inline
    D ptree_bad_data::data() const
    {
        return boost::any_cast<D>(m_data);
    }

    ///////////////////////////////////////////////////////////////////////////
    // ptree_bad_path

    template<class P> inline
    ptree_bad_path::ptree_bad_path(const std::string &w, const P &p):
        ptree_error(detail::prepare_bad_path_what(w, p)), m_path(p)
    {

    }

    inline ptree_bad_path::~ptree_bad_path() throw()
    {
    }

    template<class P> inline
    P ptree_bad_path::path() const
    {
        return boost::any_cast<P>(m_path);
    }

}}

#endif


code:
// ----------------------------------------------------------------------------
// Copyright (C) 2002-2006 Marcin Kalicinski
//
// 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)
//
// For more information, see www.boost.org
// ----------------------------------------------------------------------------
#ifndef BOOST_PROPERTY_TREE_DETAIL_FILE_PARSER_ERROR_HPP_INCLUDED
#define BOOST_PROPERTY_TREE_DETAIL_FILE_PARSER_ERROR_HPP_INCLUDED

#include <boost/property_tree/ptree.hpp>
#include <string>

namespace boost { namespace property_tree
{

    //! File parse error
    class file_parser_error: public ptree_error
    {

    public:

        ///////////////////////////////////////////////////////////////////////
        // Construction & destruction

        // Construct error
        file_parser_error(const std::string &msg,
                          const std::string &file,
                          unsigned long l) :
            ptree_error(format_what(msg, file, l)),
            m_message(msg), m_filename(file), m_line(l)
        {
        }

        ~file_parser_error() throw()
            // gcc 3.4.2 complains about lack of throw specifier on compiler
            // generated dtor
        {
        }

        ///////////////////////////////////////////////////////////////////////
        // Data access

        // Get error message (without line and file - use what() to get
        // full message)
        std::string message() const
        {
            return m_message;
        }

        // Get error filename
        std::string filename() const
        {
            return m_filename;
        }

        // Get error line number
        unsigned long line() const
        {
            return m_line;
        }

    private:

        std::string m_message;
        std::string m_filename;
        unsigned long m_line;

        // Format error message to be returned by std::runtime_error::what()
        static std::string format_what(const std::string &msg,
                                       const std::string &file,
                                       unsigned long l)
        {
            std::stringstream stream;
            stream << (file.empty() ? "<unspecified file>" : file.c_str());
            if (l > 0)
                stream << '(' << l << ')';
            stream << ": " << msg;
            return stream.str();
        }

    };

} }

#endif