robot/include/boost/graph/distributed/vertex_list_adaptor.hpp

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

#ifndef BOOST_VERTEX_LIST_ADAPTOR_HPP
#define BOOST_VERTEX_LIST_ADAPTOR_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/graph_traits.hpp>
#include <vector>
#include <boost/shared_ptr.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/parallel/parallel_property_maps.hpp>
#include <boost/graph/parallel/algorithm.hpp>
#include <boost/graph/parallel/container_traits.hpp>
#include <boost/property_map/vector_property_map.hpp>

namespace boost { namespace graph {

// --------------------------------------------------------------------------
// Global index map built from a distribution 
// --------------------------------------------------------------------------
template<typename Distribution, typename OwnerPropertyMap, 
         typename LocalPropertyMap>
class distribution_global_index_map
{
 public:
  typedef std::size_t value_type;
  typedef value_type reference;
  typedef typename property_traits<OwnerPropertyMap>::key_type key_type;
  typedef readable_property_map_tag category;

  distribution_global_index_map(const Distribution& distribution,
                                const OwnerPropertyMap& owner,
                                const LocalPropertyMap& local)
    : distribution_(distribution), owner(owner), local(local) { }

  Distribution distribution_;
  OwnerPropertyMap owner;
  LocalPropertyMap local;
};

template<typename Distribution, typename OwnerPropertyMap, 
         typename LocalPropertyMap>
inline 
typename distribution_global_index_map<Distribution, OwnerPropertyMap,
                                       LocalPropertyMap>::value_type
get(const distribution_global_index_map<Distribution, OwnerPropertyMap,
                                        LocalPropertyMap>& p,
    typename distribution_global_index_map<Distribution, OwnerPropertyMap,
                                           LocalPropertyMap>::key_type x)
{ 
  using boost::get;
  return p.distribution_.global(get(p.owner, x), get(p.local, x));
}

template<typename Graph, typename Distribution>
inline
distribution_global_index_map<
  Distribution, 
  typename property_map<Graph, vertex_owner_t>::const_type,
  typename property_map<Graph, vertex_local_t>::const_type>
make_distribution_global_index_map(const Graph& g, const Distribution& d)
{
  typedef distribution_global_index_map<
            Distribution, 
            typename property_map<Graph, vertex_owner_t>::const_type,
            typename property_map<Graph, vertex_local_t>::const_type> 
    result_type;
  return result_type(d, get(vertex_owner, g), get(vertex_local, g));
}

// --------------------------------------------------------------------------
// Global index map built from a distributed index map and list of vertices
// --------------------------------------------------------------------------
template<typename IndexMap>
class stored_global_index_map : public IndexMap
{
 public:
  typedef readable_property_map_tag category;

  stored_global_index_map(const IndexMap& index_map) : IndexMap(index_map) { 
    // When we have a global index, we need to always have the indices
    // of every key we've seen
    this->set_max_ghost_cells(0);
  }
};

// --------------------------------------------------------------------------
// Global index map support code
// --------------------------------------------------------------------------
namespace detail {
  template<typename PropertyMap, typename ForwardIterator>
  inline void 
  initialize_global_index_map(const PropertyMap&, 
                              ForwardIterator, ForwardIterator) 
  { }

  template<typename IndexMap, typename ForwardIterator>
  void 
  initialize_global_index_map(stored_global_index_map<IndexMap>& p,
                              ForwardIterator first, ForwardIterator last)
  {
    using std::distance;

    typedef typename property_traits<IndexMap>::value_type size_t;

    size_t n = distance(first, last);
    for (size_t i = 0; i < n; ++i, ++first) local_put(p, *first, i);
  }
}

// --------------------------------------------------------------------------
// Adapts a Distributed Vertex List Graph to a Vertex List Graph
// --------------------------------------------------------------------------
template<typename Graph, typename GlobalIndexMap>
class vertex_list_adaptor : public graph_traits<Graph>
{
  typedef graph_traits<Graph> inherited;

  typedef typename inherited::traversal_category base_traversal_category;
  
 public:
  typedef typename inherited::vertex_descriptor vertex_descriptor;
  typedef typename std::vector<vertex_descriptor>::iterator vertex_iterator;
  typedef typename std::vector<vertex_descriptor>::size_type
    vertices_size_type;

  struct traversal_category 
    : public virtual base_traversal_category,
      public virtual vertex_list_graph_tag {};

  vertex_list_adaptor(const Graph& g, 
                      const GlobalIndexMap& index_map = GlobalIndexMap())
    : g(&g), index_map(index_map)
  {
    using boost::vertices;

    all_vertices_.reset(new std::vector<vertex_descriptor>());
    all_gather(process_group(), vertices(g).first, vertices(g).second,
               *all_vertices_);
    detail::initialize_global_index_map(this->index_map, 
                                        all_vertices_->begin(),
                                        all_vertices_->end());
  }

  const Graph& base() const { return *g; }

  // --------------------------------------------------------------------------
  // Distributed Container
  // --------------------------------------------------------------------------
  typedef typename boost::graph::parallel::process_group_type<Graph>::type 
    process_group_type;

  process_group_type process_group() const 
  { 
    using boost::graph::parallel::process_group;
    return process_group(*g); 
  }

  std::pair<vertex_iterator, vertex_iterator> vertices() const
  { return std::make_pair(all_vertices_->begin(), all_vertices_->end()); }

  vertices_size_type num_vertices() const { return all_vertices_->size(); }

  GlobalIndexMap get_index_map() const { return index_map; }

 private:
  const Graph* g;
  GlobalIndexMap index_map;
  shared_ptr<std::vector<vertex_descriptor> > all_vertices_;
};

template<typename Graph, typename GlobalIndexMap>
inline vertex_list_adaptor<Graph, GlobalIndexMap>
make_vertex_list_adaptor(const Graph& g, const GlobalIndexMap& index_map)
{ return vertex_list_adaptor<Graph, GlobalIndexMap>(g, index_map); }

namespace detail {
  template<typename Graph>
  class default_global_index_map
  {
    typedef typename graph_traits<Graph>::vertices_size_type value_type;
    typedef typename property_map<Graph, vertex_index_t>::const_type local_map;

  public:
    typedef vector_property_map<value_type, local_map> distributed_map;
    typedef stored_global_index_map<distributed_map> type;
  };
}

template<typename Graph>
inline 
vertex_list_adaptor<Graph, 
                    typename detail::default_global_index_map<Graph>::type>
make_vertex_list_adaptor(const Graph& g)
{ 
  typedef typename detail::default_global_index_map<Graph>::type 
    GlobalIndexMap;
  typedef typename detail::default_global_index_map<Graph>::distributed_map
    DistributedMap;
  typedef vertex_list_adaptor<Graph, GlobalIndexMap> result_type;
  return result_type(g, 
                     GlobalIndexMap(DistributedMap(num_vertices(g), 
                                                   get(vertex_index, g))));
}

// --------------------------------------------------------------------------
// Incidence Graph
// --------------------------------------------------------------------------
template<typename Graph, typename GlobalIndexMap>
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor
source(typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor e,
       const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return source(e, g.base()); }

template<typename Graph, typename GlobalIndexMap>
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor
target(typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor e,
       const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return target(e, g.base()); }

template<typename Graph, typename GlobalIndexMap>
inline
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::out_edge_iterator,
          typename vertex_list_adaptor<Graph, GlobalIndexMap>::out_edge_iterator>
out_edges(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
          const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return out_edges(v, g.base()); }

template<typename Graph, typename GlobalIndexMap>
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
out_degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
          const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return out_degree(v, g.base()); }

// --------------------------------------------------------------------------
// Bidirectional Graph
// --------------------------------------------------------------------------
template<typename Graph, typename GlobalIndexMap>
inline
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::in_edge_iterator,
          typename vertex_list_adaptor<Graph, GlobalIndexMap>::in_edge_iterator>
in_edges(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
         const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return in_edges(v, g.base()); }

template<typename Graph, typename GlobalIndexMap>
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
in_degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
          const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return in_degree(v, g.base()); }

template<typename Graph, typename GlobalIndexMap>
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
       const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return degree(v, g.base()); }

// --------------------------------------------------------------------------
// Adjacency Graph
// --------------------------------------------------------------------------
template<typename Graph, typename GlobalIndexMap>
inline
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::adjacency_iterator,
          typename vertex_list_adaptor<Graph, GlobalIndexMap>::adjacency_iterator>
adjacent_vertices(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
                  const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return adjacent_vertices(v, g.base()); }


// --------------------------------------------------------------------------
// Vertex List Graph
// --------------------------------------------------------------------------
template<typename Graph, typename GlobalIndexMap>
inline
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_iterator,
          typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_iterator>
vertices(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return g.vertices(); }

template<typename Graph, typename GlobalIndexMap>
inline
typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertices_size_type
num_vertices(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return g.num_vertices(); }

// --------------------------------------------------------------------------
// Edge List Graph
// --------------------------------------------------------------------------
template<typename Graph, typename GlobalIndexMap>
inline
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_iterator,
          typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_iterator>
edges(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return edges(g.base()); }

template<typename Graph, typename GlobalIndexMap>
inline
typename vertex_list_adaptor<Graph, GlobalIndexMap>::edges_size_type
num_edges(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return num_edges(g.base()); }

// --------------------------------------------------------------------------
// Property Graph
// --------------------------------------------------------------------------
template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
inline typename property_map<Graph, PropertyTag>::type
get(PropertyTag p, vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return get(p, g.base()); }

template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
inline typename property_map<Graph, PropertyTag>::const_type
get(PropertyTag p, const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return get(p, g.base()); }

template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
inline typename property_traits<
                  typename property_map<Graph, PropertyTag>::type
                >::value_type
get(PropertyTag p, const vertex_list_adaptor<Graph, GlobalIndexMap>& g,
    typename property_traits<
               typename property_map<Graph, PropertyTag>::type
             >::key_type const& x)
{ return get(p, g.base(), x); }

template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
inline void
put(PropertyTag p, vertex_list_adaptor<Graph, GlobalIndexMap>& g,
    typename property_traits<
               typename property_map<Graph, PropertyTag>::type
             >::key_type const& x,
    typename property_traits<
               typename property_map<Graph, PropertyTag>::type
             >::value_type const& v)
{ return put(p, g.base(), x, v); }

// --------------------------------------------------------------------------
// Property Graph: vertex_index property
// --------------------------------------------------------------------------
template<typename Graph, typename GlobalIndexMap>
inline GlobalIndexMap
get(vertex_index_t, const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return g.get_index_map(); }

template<typename Graph, typename GlobalIndexMap>
inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertices_size_type
get(vertex_index_t, const vertex_list_adaptor<Graph, GlobalIndexMap>& g,
    typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor x)
{ return get(g.get_index_map(), x); }

// --------------------------------------------------------------------------
// Adjacency Matrix Graph
// --------------------------------------------------------------------------
template<typename Graph, typename GlobalIndexMap>
std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor,
          bool>
edge(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor u,
     typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
     vertex_list_adaptor<Graph, GlobalIndexMap>& g)
{ return edge(u, v, g.base()); }

} } // end namespace boost::graph

namespace boost {

// --------------------------------------------------------------------------
// Property Graph: vertex_index property
// --------------------------------------------------------------------------
template<typename Graph, typename GlobalIndexMap>
class property_map<vertex_index_t, 
                   graph::vertex_list_adaptor<Graph, GlobalIndexMap> >
{
public:
  typedef GlobalIndexMap type;
  typedef type const_type;
};

template<typename Graph, typename GlobalIndexMap>
class property_map<vertex_index_t, 
                   const graph::vertex_list_adaptor<Graph, GlobalIndexMap> >
{
public:
  typedef GlobalIndexMap type;
  typedef type const_type;
};

using graph::distribution_global_index_map;
using graph::make_distribution_global_index_map;
using graph::stored_global_index_map;
using graph::make_vertex_list_adaptor;
using graph::vertex_list_adaptor;

} // end namespace boost

#endif // BOOST_VERTEX_LIST_ADAPTOR_HPP