code:
//
//=======================================================================
// Copyright 2009 Trustees of Indiana University
// Authors: Jeremiah J. 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)
//=======================================================================
//
#ifndef BOOST_D_ARY_HEAP_HPP
#define BOOST_D_ARY_HEAP_HPP

#include <vector>
#include <cstddef>
#include <algorithm>
#include <utility>
#include <boost/assert.hpp>
#include <boost/static_assert.hpp>
#include <boost/shared_array.hpp>
#include <boost/property_map/property_map.hpp>

// WARNING: it is not safe to copy a d_ary_heap_indirect and then modify one of
// the copies.  The class is required to be copyable so it can be passed around
// (without move support from C++11), but it deep-copies the heap contents yet
// shallow-copies the index_in_heap_map.

namespace boost {

  // Swap two elements in a property map without assuming they model
  // LvaluePropertyMap -- currently not used
  template <typename PropMap>
  inline void property_map_swap(
         PropMap prop_map,
         const typename boost::property_traits<PropMap>::key_type& ka,
         const typename boost::property_traits<PropMap>::key_type& kb) {
    typename boost::property_traits<PropMap>::value_type va = get(prop_map, ka);
    put(prop_map, ka, get(prop_map, kb));
    put(prop_map, kb, va);
  }

  namespace detail {
    template <typename Value>
    class fixed_max_size_vector {
      boost::shared_array<Value> m_data;
      std::size_t m_size;

      public:
      typedef std::size_t size_type;
      fixed_max_size_vector(std::size_t max_size)
        : m_data(new Value[max_size]), m_size(0) {}
      std::size_t size() const {return m_size;}
      bool empty() const {return m_size == 0;}
      Value& operator[](std::size_t i) {return m_data[i];}
      const Value& operator[](std::size_t i) const {return m_data[i];}
      void push_back(Value v) {m_data[m_size++] = v;}
      void pop_back() {--m_size;}
      Value& back() {return m_data[m_size - 1];}
      const Value& back() const {return m_data[m_size - 1];}
    };
  }

  // D-ary heap using an indirect compare operator (use identity_property_map
  // as DistanceMap to get a direct compare operator).  This heap appears to be
  // commonly used for Dijkstra's algorithm for its good practical performance
  // on some platforms; asymptotically, it has an O(lg N) decrease-key
  // operation while that can be done in constant time on a relaxed heap.  The
  // implementation is mostly based on the binary heap page on Wikipedia and
  // online sources that state that the operations are the same for d-ary
  // heaps.  This code is not based on the old Boost d-ary heap code.
  //
  // - d_ary_heap_indirect is a model of UpdatableQueue as is needed for
  //   dijkstra_shortest_paths.
  //
  // - Value must model Assignable.
  // - Arity must be at least 2 (optimal value appears to be 4, both in my and
  //   third-party experiments).
  // - IndexInHeapMap must be a ReadWritePropertyMap from Value to
  //   Container::size_type (to store the index of each stored value within the
  //   heap for decrease-key aka update).
  // - DistanceMap must be a ReadablePropertyMap from Value to something
  //   (typedef'ed as distance_type).
  // - Compare must be a BinaryPredicate used as a less-than operator on
  //   distance_type.
  // - Container must be a random-access, contiguous container (in practice,
  //   the operations used probably require that it is std::vector<Value>).
  //
  template <typename Value,
            std::size_t Arity,
            typename IndexInHeapPropertyMap,
            typename DistanceMap,
            typename Compare = std::less<Value>,
            typename Container = std::vector<Value> >
  class d_ary_heap_indirect {
    BOOST_STATIC_ASSERT (Arity >= 2);

    public:
    typedef typename Container::size_type size_type;
    typedef Value value_type;
    typedef typename boost::property_traits<DistanceMap>::value_type key_type;
    typedef DistanceMap key_map;

    d_ary_heap_indirect(DistanceMap distance,
                        IndexInHeapPropertyMap index_in_heap,
                        const Compare& compare = Compare(),
                        const Container& data = Container())
      : compare(compare), data(data), distance(distance),
        index_in_heap(index_in_heap) {}
    /* Implicit copy constructor */
    /* Implicit assignment operator */

    size_type size() const {
      return data.size();
    }

    bool empty() const {
      return data.empty();
    }

    void push(const Value& v) {
      size_type index = data.size();
      data.push_back(v);
      put(index_in_heap, v, index);
      preserve_heap_property_up(index);
      verify_heap();
    }

    Value& top() {
      BOOST_ASSERT (!this->empty());
      return data[0];
    }

    const Value& top() const {
      BOOST_ASSERT (!this->empty());
      return data[0];
    }

    void pop() {
      BOOST_ASSERT (!this->empty());
      put(index_in_heap, data[0], (size_type)(-1));
      if (data.size() != 1) {
        data[0] = data.back();
        put(index_in_heap, data[0], (size_type)(0));
        data.pop_back();
        preserve_heap_property_down();
        verify_heap();
      } else {
        data.pop_back();
      }
    }

    // This function assumes the key has been updated (using an external write
    // to the distance map or such)
    // See http://coding.derkeiler.com/Archive/General/comp.theory/2007-05/msg00043.html
    void update(const Value& v) { /* decrease-key */
      size_type index = get(index_in_heap, v);
      preserve_heap_property_up(index);
      verify_heap();
    }

    bool contains(const Value& v) const {
      size_type index = get(index_in_heap, v);
      return (index != (size_type)(-1));
    }

    void push_or_update(const Value& v) { /* insert if not present, else update */
      size_type index = get(index_in_heap, v);
      if (index == (size_type)(-1)) {
        index = data.size();
        data.push_back(v);
        put(index_in_heap, v, index);
      }
      preserve_heap_property_up(index);
      verify_heap();
    }

    DistanceMap keys() const {
      return distance;
    }

    private:
    Compare compare;
    Container data;
    DistanceMap distance;
    IndexInHeapPropertyMap index_in_heap;

    // The distances being compared using compare and that are stored in the
    // distance map
    typedef typename boost::property_traits<DistanceMap>::value_type distance_type;

    // Get the parent of a given node in the heap
    static size_type parent(size_type index) {
      return (index - 1) / Arity;
    }

    // Get the child_idx'th child of a given node; 0 <= child_idx < Arity
    static size_type child(size_type index, std::size_t child_idx) {
      return index * Arity + child_idx + 1;
    }

    // Swap two elements in the heap by index, updating index_in_heap
    void swap_heap_elements(size_type index_a, size_type index_b) {
      using std::swap;
      Value value_a = data[index_a];
      Value value_b = data[index_b];
      data[index_a] = value_b;
      data[index_b] = value_a;
      put(index_in_heap, value_a, index_b);
      put(index_in_heap, value_b, index_a);
    }

    // Emulate the indirect_cmp that is now folded into this heap class
    bool compare_indirect(const Value& a, const Value& b) const {
      return compare(get(distance, a), get(distance, b));
    }

    // Verify that the array forms a heap; commented out by default
    void verify_heap() const {
      // This is a very expensive test so it should be disabled even when
      // NDEBUG is not defined
#if 0
      for (size_t i = 1; i < data.size(); ++i) {
        if (compare_indirect(data[i], data[parent(i)])) {
          BOOST_ASSERT (!"Element is smaller than its parent");
        }
      }
#endif
    }

    // Starting at a node, move up the tree swapping elements to preserve the
    // heap property
    void preserve_heap_property_up(size_type index) {
      size_type orig_index = index;
      size_type num_levels_moved = 0;
      // The first loop just saves swaps that need to be done in order to avoid
      // aliasing issues in its search; there is a second loop that does the
      // necessary swap operations
      if (index == 0) return; // Do nothing on root
      Value currently_being_moved = data[index];
      distance_type currently_being_moved_dist =
        get(distance, currently_being_moved);
      for (;;) {
        if (index == 0) break; // Stop at root
        size_type parent_index = parent(index);
        Value parent_value = data[parent_index];
        if (compare(currently_being_moved_dist, get(distance, parent_value))) {
          ++num_levels_moved;
          index = parent_index;
          continue;
        } else {
          break; // Heap property satisfied
        }
      }
      // Actually do the moves -- move num_levels_moved elements down in the
      // tree, then put currently_being_moved at the top
      index = orig_index;
      for (size_type i = 0; i < num_levels_moved; ++i) {
        size_type parent_index = parent(index);
        Value parent_value = data[parent_index];
        put(index_in_heap, parent_value, index);
        data[index] = parent_value;
        index = parent_index;
      }
      data[index] = currently_being_moved;
      put(index_in_heap, currently_being_moved, index);
      verify_heap();
    }

    // From the root, swap elements (each one with its smallest child) if there
    // are any parent-child pairs that violate the heap property
    void preserve_heap_property_down() {
      if (data.empty()) return;
      size_type index = 0;
      Value currently_being_moved = data[0];
      distance_type currently_being_moved_dist =
        get(distance, currently_being_moved);
      size_type heap_size = data.size();
      Value* data_ptr = &data[0];
      for (;;) {
        size_type first_child_index = child(index, 0);
        if (first_child_index >= heap_size) break; /* No children */
        Value* child_base_ptr = data_ptr + first_child_index;
        size_type smallest_child_index = 0;
        distance_type smallest_child_dist = get(distance, child_base_ptr[smallest_child_index]);
        if (first_child_index + Arity <= heap_size) {
          // Special case for a statically known loop count (common case)
          for (size_t i = 1; i < Arity; ++i) {
            Value i_value = child_base_ptr[i];
            distance_type i_dist = get(distance, i_value);
            if (compare(i_dist, smallest_child_dist)) {
              smallest_child_index = i;
              smallest_child_dist = i_dist;
            }
          }
        } else {
          for (size_t i = 1; i < heap_size - first_child_index; ++i) {
            distance_type i_dist = get(distance, child_base_ptr[i]);
            if (compare(i_dist, smallest_child_dist)) {
              smallest_child_index = i;
              smallest_child_dist = i_dist;
            }
          }
        }
        if (compare(smallest_child_dist, currently_being_moved_dist)) {
          swap_heap_elements(smallest_child_index + first_child_index, index);
          index = smallest_child_index + first_child_index;
          continue;
        } else {
          break; // Heap property satisfied
        }
      }
      verify_heap();
    }

  };

} // namespace boost

#endif // BOOST_D_ARY_HEAP_HPP

license: mit


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_DETAIL_EDGE_HPP
#define BOOST_GRAPH_DETAIL_EDGE_HPP

#include <iosfwd>

#include <boost/functional/hash.hpp>

namespace boost {

  namespace  detail {

    template <typename Directed, typename Vertex>
    struct edge_base
    {
      inline edge_base() {}
      inline edge_base(Vertex s, Vertex d)
        : m_source(s), m_target(d) { }
      Vertex m_source;
      Vertex m_target;
    };

    template <typename Directed, typename Vertex>
    class edge_desc_impl  : public edge_base<Directed,Vertex> {
      typedef edge_desc_impl                              self;
      typedef edge_base<Directed,Vertex> Base;
    public:
      typedef void                              property_type;

      inline edge_desc_impl() : m_eproperty(0) {}

      inline edge_desc_impl(Vertex s, Vertex d, const property_type* eplug)
        : Base(s,d), m_eproperty(const_cast<property_type*>(eplug)) { }

      property_type* get_property() { return m_eproperty; }
      const property_type* get_property() const { return m_eproperty; }

      //  protected:
      property_type* m_eproperty;
    };

    template <class D, class V>
    inline bool
    operator==(const detail::edge_desc_impl<D,V>& a,
               const detail::edge_desc_impl<D,V>& b)
    {
      return a.get_property() == b.get_property();
    }
    template <class D, class V>
    inline bool
    operator!=(const detail::edge_desc_impl<D,V>& a,
               const detail::edge_desc_impl<D,V>& b)
    {
      return ! (a.get_property() == b.get_property());
    }

    // Order edges according to the address of their property object
    template <class D, class V>
    inline bool
    operator<(const detail::edge_desc_impl<D,V>& a,
               const detail::edge_desc_impl<D,V>& b)
    {
      return a.get_property() < b.get_property();
    }
    template <class D, class V>
    inline bool
    operator<=(const detail::edge_desc_impl<D,V>& a,
               const detail::edge_desc_impl<D,V>& b)
    {
      return a.get_property() <= b.get_property();
    }
    template <class D, class V>
    inline bool
    operator>(const detail::edge_desc_impl<D,V>& a,
               const detail::edge_desc_impl<D,V>& b)
    {
      return a.get_property() > b.get_property();
    }
    template <class D, class V>
    inline bool
    operator>=(const detail::edge_desc_impl<D,V>& a,
               const detail::edge_desc_impl<D,V>& b)
    {
      return a.get_property() >= b.get_property();
    }

  } //namespace detail

} // namespace boost

namespace std {
  template <class Char, class Traits, class D, class V>
  std::basic_ostream<Char, Traits>&
  operator<<(std::basic_ostream<Char, Traits>& os,
             const boost::detail::edge_desc_impl<D,V>& e)
  {
    return os << "(" << e.m_source << "," << e.m_target << ")";
  }
}

// Boost's functional/hash
namespace boost {
  template<typename D, typename V>
  struct hash<boost::detail::edge_desc_impl<D, V> >
  {
    std::size_t operator()(const boost::detail::edge_desc_impl<D, V> & x) const
    { return hash_value(x.get_property()); }
  };
}

#endif // BOOST_GRAPH_DETAIL_DETAIL_EDGE_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_BFS_HPP
#define BOOST_GRAPH_PARALLEL_BFS_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/breadth_first_search.hpp>
#include <boost/graph/overloading.hpp>
#include <boost/graph/distributed/concepts.hpp>
#include <boost/graph/distributed/detail/filtered_queue.hpp>
#include <boost/graph/distributed/queue.hpp>
#include <boost/dynamic_bitset.hpp>
#include <boost/pending/queue.hpp>
#include <boost/graph/parallel/properties.hpp>
#include <boost/graph/parallel/container_traits.hpp>

namespace boost {
  namespace detail {
    /** @brief A unary predicate that decides when to push into a
     *         breadth-first search queue.
     *
     *  This predicate stores a color map that is used to determine
     *  when to push. If it is provided with a key for which the color
     *  is white, it darkens the color to gray and returns true (so
     *  that the value will be pushed appropriately); if the color is
     *  not white, it returns false so that the vertex will be
     *  ignored.
     */
    template<typename ColorMap>
    struct darken_and_push
    {
      typedef typename property_traits<ColorMap>::key_type argument_type;
      typedef bool result_type;

      explicit darken_and_push(const ColorMap& color) : color(color) { }

      bool operator()(const argument_type& value) const
      {
        typedef color_traits<typename property_traits<ColorMap>::value_type>
          Color;
        if (get(color, value) == Color::white()) {
          put(color, value, Color::gray());
          return true;
        } else {
          return false;
        }
      }

      ColorMap color;
    };

    template<typename IndexMap>
    struct has_not_been_seen
    {
      typedef bool result_type;

      has_not_been_seen() { }

      has_not_been_seen(std::size_t n, IndexMap index_map)
        : seen(n), index_map(index_map) {}

      template<typename Key>
      result_type operator()(Key key)
      {
        bool result = seen[get(index_map, key)];
        seen[get(index_map, key)] = true;
        return !result;
      }

      void swap(has_not_been_seen& other)
      {
        using std::swap;
        swap(seen, other.seen);
        swap(index_map, other.index_map);
      }

    private:
      dynamic_bitset<> seen;
      IndexMap index_map;
    };

    template<typename IndexMap>
    inline void
    swap(has_not_been_seen<IndexMap>& x, has_not_been_seen<IndexMap>& y)
    {
      x.swap(y);
    }

    template <class DistributedGraph, class ColorMap, class BFSVisitor,
              class BufferRef, class VertexIndexMap>
    inline void
    parallel_bfs_helper
      (DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       ColorMap color,
       BFSVisitor vis,
       BufferRef Q,
       VertexIndexMap)
    {
      set_property_map_role(vertex_color, color);
      color.set_consistency_model(0);
      breadth_first_search(g, s, Q.ref, vis, color);
    }

    template <class DistributedGraph, class ColorMap, class BFSVisitor,
              class VertexIndexMap>
    void parallel_bfs_helper
      (DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       ColorMap color,
       BFSVisitor vis,
       boost::param_not_found,
       VertexIndexMap vertex_index)
    {
      using boost::graph::parallel::process_group;

      typedef graph_traits<DistributedGraph> Traits;
      typedef typename Traits::vertex_descriptor Vertex;
      typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type
        process_group_type;

      set_property_map_role(vertex_color, color);
      color.set_consistency_model(0);

      // Buffer default
      typedef typename property_map<DistributedGraph, vertex_owner_t>
        ::const_type vertex_owner_map;
      typedef boost::graph::distributed::distributed_queue<
                process_group_type, vertex_owner_map, queue<Vertex>,
                detail::darken_and_push<ColorMap> > queue_t;
      queue_t Q(process_group(g),
                get(vertex_owner, g),
                detail::darken_and_push<ColorMap>(color));
      breadth_first_search(g, s, Q, vis, color);
    }

    template <class DistributedGraph, class ColorMap, class BFSVisitor,
              class P, class T, class R>
    void bfs_helper
      (DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       ColorMap color,
       BFSVisitor vis,
       const bgl_named_params<P, T, R>& params,
       boost::mpl::true_)
        {
            parallel_bfs_helper
        (g, s, color, vis, get_param(params, buffer_param_t()),
         choose_const_pmap(get_param(params, vertex_index),  g, vertex_index));
        }
  }
}

#endif // BOOST_GRAPH_PARALLEL_BFS_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

//
// Distributed graph concepts and helpers
//

#ifndef BOOST_GRAPH_DISTRIBUTED_CONCEPTS_HPP
#define BOOST_GRAPH_DISTRIBUTED_CONCEPTS_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/version.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/concept/assert.hpp>

#if BOOST_VERSION >= 103500
#  include <boost/concept/detail/concept_def.hpp>
#endif

namespace boost {

#if BOOST_VERSION >= 103500
  namespace concepts {
#endif

#if BOOST_VERSION < 103500

template <class G>
struct DistributedVertexListGraphConcept
{
  typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
  typedef typename graph_traits<G>::vertices_size_type vertices_size_type;
  typedef typename graph_traits<G>::traversal_category
    traversal_category;
  void constraints() {
    BOOST_CONCEPT_ASSERT(( GraphConcept<G> ));
    BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<vertex_iterator> ));
    BOOST_CONCEPT_ASSERT(( ConvertibleConcept<traversal_category,
      distributed_vertex_list_graph_tag> ));

#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
    // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
    // you want to use vector_as_graph, it is!  I'm sure the graph
    // library leaves these out all over the place.  Probably a
    // redesign involving specializing a template with a static
    // member function is in order :(
    using boost::vertices;
#endif
    p = vertices(g);
    v = *p.first;
    const_constraints(g);
  }
  void const_constraints(const G& cg) {
#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
    // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
    // you want to use vector_as_graph, it is!  I'm sure the graph
    // library leaves these out all over the place.  Probably a
    // redesign involving specializing a template with a static
    // member function is in order :(
    using boost::vertices;
#endif

    p = vertices(cg);
    v = *p.first;
    V = num_vertices(cg);
  }
  std::pair<vertex_iterator,vertex_iterator> p;
  typename graph_traits<G>::vertex_descriptor v;
  G g;
  vertices_size_type V;
};

template <class G>
struct DistributedEdgeListGraphConcept
{
  typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
  typedef typename graph_traits<G>::edge_iterator edge_iterator;
  typedef typename graph_traits<G>::edges_size_type edges_size_type;
  typedef typename graph_traits<G>::traversal_category
    traversal_category;
  void constraints() {
    BOOST_CONCEPT_ASSERT(( GraphConcept<G> ));
    BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<edge_iterator> ));
    BOOST_CONCEPT_ASSERT(( DefaultConstructibleConcept<edge_descriptor> ));
    BOOST_CONCEPT_ASSERT(( EqualityComparableConcept<edge_descriptor> ));
    BOOST_CONCEPT_ASSERT(( AssignableConcept<edge_descriptor> ));
    BOOST_CONCEPT_ASSERT(( ConvertibleConcept<traversal_category,
      distributed_edge_list_graph_tag> ));

    p = edges(g);
    e = *p.first;
    u = source(e, g);
    v = target(e, g);
    const_constraints(g);
  }
  void const_constraints(const G& cg) {
    p = edges(cg);
    E = num_edges(cg);
    e = *p.first;
    u = source(e, cg);
    v = target(e, cg);
  }
  std::pair<edge_iterator,edge_iterator> p;
  typename graph_traits<G>::vertex_descriptor u, v;
  typename graph_traits<G>::edge_descriptor e;
  edges_size_type E;
  G g;
};
#else
  BOOST_concept(DistributedVertexListGraph,(G))
    : Graph<G>
  {
    typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
    typedef typename graph_traits<G>::vertices_size_type vertices_size_type;
    typedef typename graph_traits<G>::traversal_category
      traversal_category;
    ~DistributedVertexListGraph() {
      BOOST_CONCEPT_ASSERT((MultiPassInputIterator<vertex_iterator>));
      BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
        distributed_vertex_list_graph_tag>));

#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
      // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
      // you want to use vector_as_graph, it is!  I'm sure the graph
      // library leaves these out all over the place.  Probably a
      // redesign involving specializing a template with a static
      // member function is in order :(
      using boost::vertices;
#endif
      p = vertices(g);
      v = *p.first;
      const_constraints(g);
    }
    void const_constraints(const G& cg) {
#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
      // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
      // you want to use vector_as_graph, it is!  I'm sure the graph
      // library leaves these out all over the place.  Probably a
      // redesign involving specializing a template with a static
      // member function is in order :(
      using boost::vertices;
#endif

      p = vertices(cg);
      v = *p.first;
      V = num_vertices(cg);
    }
    std::pair<vertex_iterator,vertex_iterator> p;
    typename graph_traits<G>::vertex_descriptor v;
    G g;
    vertices_size_type V;
  };

  BOOST_concept(DistributedEdgeListGraph,(G))
    : Graph<G>
  {
    typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
    typedef typename graph_traits<G>::edge_iterator edge_iterator;
    typedef typename graph_traits<G>::edges_size_type edges_size_type;
    typedef typename graph_traits<G>::traversal_category
      traversal_category;
    ~DistributedEdgeListGraph() {
      BOOST_CONCEPT_ASSERT((MultiPassInputIterator<edge_iterator>));
      BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>));
      BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>));
      BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>));
      BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
        distributed_edge_list_graph_tag>));

      p = edges(g);
      e = *p.first;
      u = source(e, g);
      v = target(e, g);
      const_constraints(g);
    }
    void const_constraints(const G& cg) {
      p = edges(cg);
      E = num_edges(cg);
      e = *p.first;
      u = source(e, cg);
      v = target(e, cg);
    }
    std::pair<edge_iterator,edge_iterator> p;
    typename graph_traits<G>::vertex_descriptor u, v;
    typename graph_traits<G>::edge_descriptor e;
    edges_size_type E;
    G g;
  };
#endif

#if BOOST_VERSION >= 103500
  } // end namespace concepts

  using concepts::DistributedVertexListGraphConcept;
  using concepts::DistributedEdgeListGraphConcept;
#endif
} // end namespace boost

#if BOOST_VERSION >= 103500
#  include <boost/concept/detail/concept_undef.hpp>
#endif

#endif // BOOST_GRAPH_DISTRIBUTED_CONCEPTS_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
#ifndef BOOST_FILTERED_QUEUE_HPP
#define BOOST_FILTERED_QUEUE_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 <algorithm>

namespace boost {

/** Queue adaptor that filters elements pushed into the queue
 * according to some predicate.
 */
template<typename Buffer, typename Predicate>
class filtered_queue
{
 public:
  typedef Buffer                      buffer_type;
  typedef Predicate                   predicate_type;
  typedef typename Buffer::value_type value_type;
  typedef typename Buffer::size_type  size_type;

  /**
   * Constructs a new filtered queue with an initial buffer and a
   * predicate.
   *
   * @param buffer the initial buffer
   * @param pred the predicate
   */
  explicit
  filtered_queue(const buffer_type& buffer = buffer_type(),
                 const predicate_type& pred = predicate_type())
    : buffer(buffer), pred(pred) {}

  /** Push a value into the queue.
   *
   *  If the predicate returns @c true for @p x, pushes @p x into the
   *  buffer.
   */
  void push(const value_type& x)  { if (pred(x)) buffer.push(x); }

  /** Pop the front element off the buffer.
   *
   * @pre @c !empty()
   */
  void pop()                      { buffer.pop(); }

  /** Retrieve the front (top) element in the buffer.
   *
   * @pre @c !empty()
   */
  value_type& top()               { return buffer.top(); }

  /**
   * \overload
   */
  const value_type& top() const   { return buffer.top(); }

  /** Determine the number of elements in the buffer. */
  size_type size() const          { return buffer.size(); }

  /** Determine if the buffer is empty. */
  bool empty() const              { return buffer.empty(); }

  /** Get a reference to the underlying buffer. */
  buffer_type& base()             { return buffer; }
  const buffer_type& base() const { return buffer; }

  /** Swap the contents of this with @p other. */
  void swap(filtered_queue& other)
  {
    using std::swap;
    swap(buffer, other.buffer);
    swap(pred, other.pred);
  }

 private:
  buffer_type buffer;
  predicate_type pred;
};

/** Create a filtered queue. */
template<typename Buffer, typename Predicate>
inline filtered_queue<Buffer, Predicate>
make_filtered_queue(const Buffer& buffer, const Predicate& pred)
{ return filtered_queue<Buffer, Predicate>(buffer, pred); }

/** Swap a filtered_queue. */
template<typename Buffer, typename Predicate>
inline void
swap(filtered_queue<Buffer, Predicate>& x,
     filtered_queue<Buffer, Predicate>& y)
{
  x.swap(y);
}

} // end namespace boost

#endif // BOOST_FILTERED_QUEUE_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
#include <boost/optional.hpp>
#include <cassert>
#include <boost/graph/parallel/algorithm.hpp>
#include <boost/graph/parallel/process_group.hpp>
#include <functional>
#include <algorithm>
#include <boost/graph/parallel/simple_trigger.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 distributed {

template<BOOST_DISTRIBUTED_QUEUE_PARMS>
BOOST_DISTRIBUTED_QUEUE_TYPE::
distributed_queue(const ProcessGroup& process_group, const OwnerMap& owner,
                  const Buffer& buffer, bool polling)
  : process_group(process_group, attach_distributed_object()),
    owner(owner),
    buffer(buffer),
    polling(polling)
{
  if (!polling)
    outgoing_buffers.reset(
      new outgoing_buffers_t(num_processes(process_group)));

  setup_triggers();
}

template<BOOST_DISTRIBUTED_QUEUE_PARMS>
BOOST_DISTRIBUTED_QUEUE_TYPE::
distributed_queue(const ProcessGroup& process_group, const OwnerMap& owner,
                  const Buffer& buffer, const UnaryPredicate& pred,
                  bool polling)
  : process_group(process_group, attach_distributed_object()),
    owner(owner),
    buffer(buffer),
    pred(pred),
    polling(polling)
{
  if (!polling)
    outgoing_buffers.reset(
      new outgoing_buffers_t(num_processes(process_group)));

  setup_triggers();
}

template<BOOST_DISTRIBUTED_QUEUE_PARMS>
BOOST_DISTRIBUTED_QUEUE_TYPE::
distributed_queue(const ProcessGroup& process_group, const OwnerMap& owner,
                  const UnaryPredicate& pred, bool polling)
  : process_group(process_group, attach_distributed_object()),
    owner(owner),
    pred(pred),
    polling(polling)
{
  if (!polling)
    outgoing_buffers.reset(
      new outgoing_buffers_t(num_processes(process_group)));

  setup_triggers();
}

template<BOOST_DISTRIBUTED_QUEUE_PARMS>
void
BOOST_DISTRIBUTED_QUEUE_TYPE::push(const value_type& x)
{
  typename ProcessGroup::process_id_type dest = get(owner, x);
  if (outgoing_buffers)
    outgoing_buffers->at(dest).push_back(x);
  else if (dest == process_id(process_group))
    buffer.push(x);
  else
    send(process_group, get(owner, x), msg_push, x);
}

template<BOOST_DISTRIBUTED_QUEUE_PARMS>
bool
BOOST_DISTRIBUTED_QUEUE_TYPE::empty() const
{
  /* Processes will stay here until the buffer is nonempty or
     synchronization with the other processes indicates that all local
     buffers are empty (and no messages are in transit).
   */
  while (buffer.empty() && !do_synchronize()) ;

  return buffer.empty();
}

template<BOOST_DISTRIBUTED_QUEUE_PARMS>
typename BOOST_DISTRIBUTED_QUEUE_TYPE::size_type
BOOST_DISTRIBUTED_QUEUE_TYPE::size() const
{
  empty();
  return buffer.size();
}

template<BOOST_DISTRIBUTED_QUEUE_PARMS>
void BOOST_DISTRIBUTED_QUEUE_TYPE::setup_triggers()
{
  using boost::graph::parallel::simple_trigger;

  simple_trigger(process_group, msg_push, this,
                 &distributed_queue::handle_push);
  simple_trigger(process_group, msg_multipush, this,
                 &distributed_queue::handle_multipush);
}

template<BOOST_DISTRIBUTED_QUEUE_PARMS>
void
BOOST_DISTRIBUTED_QUEUE_TYPE::
handle_push(int /*source*/, int /*tag*/, const value_type& value,
            trigger_receive_context)
{
  if (pred(value)) buffer.push(value);
}

template<BOOST_DISTRIBUTED_QUEUE_PARMS>
void
BOOST_DISTRIBUTED_QUEUE_TYPE::
handle_multipush(int /*source*/, int /*tag*/,
                 const std::vector<value_type>& values,
                 trigger_receive_context)
{
  for (std::size_t i = 0; i < values.size(); ++i)
    if (pred(values[i])) buffer.push(values[i]);
}

template<BOOST_DISTRIBUTED_QUEUE_PARMS>
bool
BOOST_DISTRIBUTED_QUEUE_TYPE::do_synchronize() const
{
#ifdef PBGL_ACCOUNTING
  ++num_synchronizations;
#endif

  using boost::parallel::all_reduce;
  using std::swap;

  typedef typename ProcessGroup::process_id_type process_id_type;

  if (outgoing_buffers) {
    // Transfer all of the push requests
    process_id_type id = process_id(process_group);
    process_id_type np = num_processes(process_group);
    for (process_id_type dest = 0; dest < np; ++dest) {
      outgoing_buffer_t& outgoing = outgoing_buffers->at(dest);
      std::size_t size = outgoing.size();
      if (size != 0) {
        if (dest != id) {
          send(process_group, dest, msg_multipush, outgoing);
        } else {
          for (std::size_t i = 0; i < size; ++i)
            buffer.push(outgoing[i]);
        }
        outgoing.clear();
      }
    }
  }
  synchronize(process_group);

  unsigned local_size = buffer.size();
  unsigned global_size =
    all_reduce(process_group, local_size, std::plus<unsigned>());
  return global_size == 0;
}

} } } // end namespace boost::graph::distributed


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
#ifndef BOOST_GRAPH_DISTRIBUTED_QUEUE_HPP
#define BOOST_GRAPH_DISTRIBUTED_QUEUE_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/parallel/process_group.hpp>
#include <boost/optional.hpp>
#include <boost/shared_ptr.hpp>
#include <vector>

namespace boost { namespace graph { namespace distributed {

/// A unary predicate that always returns "true".
struct always_push
{
  template<typename T> bool operator()(const T&) const { return true; }
};

/** A distributed queue adaptor.
 *
 * Class template @c distributed_queue implements a distributed queue
 * across a process group. The distributed queue is an adaptor over an
 * existing (local) queue, which must model the @ref Buffer
 * concept. Each process stores a distinct copy of the local queue,
 * from which it draws or removes elements via the @ref pop and @ref
 * top members.
 *
 * The value type of the local queue must be a model of the @ref
 * GlobalDescriptor concept. The @ref push operation of the
 * distributed queue passes (via a message) the value to its owning
 * processor. Thus, the elements within a particular local queue are
 * guaranteed to have the process owning that local queue as an owner.
 *
 * Synchronization of distributed queues occurs in the @ref empty and
 * @ref size functions, which will only return "empty" values (true or
 * 0, respectively) when the entire distributed queue is empty. If the
 * local queue is empty but the distributed queue is not, the
 * operation will block until either condition changes. When the @ref
 * size function of a nonempty queue returns, it returns the size of
 * the local queue. These semantics were selected so that sequential
 * code that processes elements in the queue via the following idiom
 * can be parallelized via introduction of a distributed queue:
 *
 *   distributed_queue<...> Q;
 *   Q.push(x);
 *   while (!Q.empty()) {
 *     // do something, that may push a value onto Q
 *   }
 *
 * In the parallel version, the initial @ref push operation will place
 * the value @c x onto its owner's queue. All processes will
 * synchronize at the call to empty, and only the process owning @c x
 * will be allowed to execute the loop (@ref Q.empty() returns
 * false). This iteration may in turn push values onto other remote
 * queues, so when that process finishes execution of the loop body
 * and all processes synchronize again in @ref empty, more processes
 * may have nonempty local queues to execute. Once all local queues
 * are empty, @ref Q.empty() returns @c false for all processes.
 *
 * The distributed queue can receive messages at two different times:
 * during synchronization and when polling @ref empty. Messages are
 * always received during synchronization, to ensure that accurate
 * local queue sizes can be determines. However, whether @ref empty
 * should poll for messages is specified as an option to the
 * constructor. Polling may be desired when the order in which
 * elements in the queue are processed is not important, because it
 * permits fewer synchronization steps and less communication
 * overhead. However, when more strict ordering guarantees are
 * required, polling may be semantically incorrect. By disabling
 * polling, one ensures that parallel execution using the idiom above
 * will not process an element at a later "level" before an earlier
 * "level".
 *
 * The distributed queue nearly models the @ref Buffer
 * concept. However, the @ref push routine does not necessarily
 * increase the result of @c size() by one (although the size of the
 * global queue does increase by one).
 */
template<typename ProcessGroup, typename OwnerMap, typename Buffer,
         typename UnaryPredicate = always_push>
class distributed_queue
{
  typedef distributed_queue self_type;

  enum {
    /** Message indicating a remote push. The message contains a
     * single value x of type value_type that is to be pushed on the
     * receiver's queue.
     */
    msg_push,
    /** Push many elements at once. */
    msg_multipush
  };

 public:
  typedef ProcessGroup                     process_group_type;
  typedef Buffer                           buffer_type;
  typedef typename buffer_type::value_type value_type;
  typedef typename buffer_type::size_type  size_type;

  /** Construct a new distributed queue.
   *
   * Build a new distributed queue that communicates over the given @p
   * process_group, whose local queue is initialized via @p buffer and
   * which may or may not poll for messages.
   */
  explicit
  distributed_queue(const ProcessGroup& process_group,
                    const OwnerMap& owner,
                    const Buffer& buffer,
                    bool polling = false);

  /** Construct a new distributed queue.
   *
   * Build a new distributed queue that communicates over the given @p
   * process_group, whose local queue is initialized via @p buffer and
   * which may or may not poll for messages.
   */
  explicit
  distributed_queue(const ProcessGroup& process_group = ProcessGroup(),
                    const OwnerMap& owner = OwnerMap(),
                    const Buffer& buffer = Buffer(),
                    const UnaryPredicate& pred = UnaryPredicate(),
                    bool polling = false);

  /** Construct a new distributed queue.
   *
   * Build a new distributed queue that communicates over the given @p
   * process_group, whose local queue is default-initalized and which
   * may or may not poll for messages.
   */
  distributed_queue(const ProcessGroup& process_group, const OwnerMap& owner,
                    const UnaryPredicate& pred, bool polling = false);

  /** Virtual destructor required with virtual functions.
   *
   */
  virtual ~distributed_queue() {}

  /** Push an element onto the distributed queue.
   *
   * The element will be sent to its owner process to be added to that
   * process's local queue. If polling is enabled for this queue and
   * the owner process is the current process, the value will be
   * immediately pushed onto the local queue.
   *
   * Complexity: O(1) messages of size O(sizeof(value_type)) will be
   * transmitted.
   */
  void push(const value_type& x);

  /** Pop an element off the local queue.
   *
   * @p @c !empty()
   */
  void pop() { buffer.pop(); }

  /**
   * Return the element at the top of the local queue.
   *
   * @p @c !empty()
   */
  value_type& top() { return buffer.top(); }

  /**
   * \overload
   */
  const value_type& top() const { return buffer.top(); }

  /** Determine if the queue is empty.
   *
   * When the local queue is nonempty, returns @c true. If the local
   * queue is empty, synchronizes with all other processes in the
   * process group until either (1) the local queue is nonempty
   * (returns @c true) (2) the entire distributed queue is empty
   * (returns @c false).
   */
  bool empty() const;

  /** Determine the size of the local queue.
   *
   * The behavior of this routine is equivalent to the behavior of
   * @ref empty, except that when @ref empty returns true this
   * function returns the size of the local queue and when @ref empty
   * returns false this function returns zero.
   */
  size_type size() const;

  // private:
  /** Synchronize the distributed queue and determine if all queues
   * are empty.
   *
   * \returns \c true when all local queues are empty, or false if at least
   * one of the local queues is nonempty.
   * Defined as virtual for derived classes like depth_limited_distributed_queue.
   */
  virtual bool do_synchronize() const;

 private:
  // Setup triggers
  void setup_triggers();

  // Message handlers
  void
  handle_push(int source, int tag, const value_type& value,
              trigger_receive_context);

  void
  handle_multipush(int source, int tag, const std::vector<value_type>& values,
                   trigger_receive_context);

  mutable ProcessGroup process_group;
  OwnerMap owner;
  mutable Buffer buffer;
  UnaryPredicate pred;
  bool polling;

  typedef std::vector<value_type> outgoing_buffer_t;
  typedef std::vector<outgoing_buffer_t> outgoing_buffers_t;
  shared_ptr<outgoing_buffers_t> outgoing_buffers;
};

/// Helper macro containing the normal names for the template
/// parameters to distributed_queue.
#define BOOST_DISTRIBUTED_QUEUE_PARMS                           \
  typename ProcessGroup, typename OwnerMap, typename Buffer,    \
  typename UnaryPredicate

/// Helper macro containing the normal template-id for
/// distributed_queue.
#define BOOST_DISTRIBUTED_QUEUE_TYPE                                    \
  distributed_queue<ProcessGroup, OwnerMap, Buffer, UnaryPredicate>

/** Synchronize all processes involved with the given distributed queue.
 *
 * This function will synchronize all of the local queues for a given
 * distributed queue, by ensuring that no additional messages are in
 * transit. It is rarely required by the user, because most
 * synchronization of distributed queues occurs via the @c empty or @c
 * size methods.
 */
template<BOOST_DISTRIBUTED_QUEUE_PARMS>
inline void
synchronize(const BOOST_DISTRIBUTED_QUEUE_TYPE& Q)
{ Q.do_synchronize(); }

/// Construct a new distributed queue.
template<typename ProcessGroup, typename OwnerMap, typename Buffer>
inline distributed_queue<ProcessGroup, OwnerMap, Buffer>
make_distributed_queue(const ProcessGroup& process_group,
                       const OwnerMap& owner,
                       const Buffer& buffer,
                       bool polling = false)
{
  typedef distributed_queue<ProcessGroup, OwnerMap, Buffer> result_type;
  return result_type(process_group, owner, buffer, polling);
}

} } } // end namespace boost::graph::distributed

#include <boost/graph/distributed/detail/queue.ipp>

#undef BOOST_DISTRIBUTED_QUEUE_TYPE
#undef BOOST_DISTRIBUTED_QUEUE_PARMS

#endif // BOOST_GRAPH_DISTRIBUTED_QUEUE_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
//           Jeremiah Willcock
//           Andrew Lumsdaine

// Distributed version of the two-bit color map
#ifndef BOOST_DISTRIBUTED_TWO_BIT_COLOR_MAP_HPP
#define BOOST_DISTRIBUTED_TWO_BIT_COLOR_MAP_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/two_bit_color_map.hpp>
#include <boost/property_map/parallel/distributed_property_map.hpp>
#include <boost/property_map/parallel/local_property_map.hpp>

namespace boost {

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
class two_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
  : public parallel::distributed_property_map<ProcessGroup, GlobalMap,
                                              two_bit_color_map<StorageMap> >
{
  typedef two_bit_color_map<StorageMap> local_map;

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

  typedef local_property_map<ProcessGroup, GlobalMap, StorageMap>
    index_map_type;

public:
  two_bit_color_map(std::size_t inital_size,
                    const index_map_type& index = index_map_type())
    : inherited(index.process_group(),  index.global(),
                local_map(inital_size, index.base())) { }

  inherited&       base()       { return *this; }
  const inherited& base() const { return *this; }
};

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
inline two_bit_color_type
get(two_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
      const& pm,
    typename property_traits<GlobalMap>::key_type key)
{
  return get(pm.base(), key);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
inline void
put(two_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
      const& pm,
    typename property_traits<GlobalMap>::key_type key,
    two_bit_color_type value)
{
  put(pm.base(), key, value);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
class two_bit_color_map<parallel::distributed_property_map<
                          ProcessGroup, GlobalMap, StorageMap> >
  : public parallel::distributed_property_map<
             ProcessGroup, GlobalMap, two_bit_color_map<StorageMap> >
{
  typedef two_bit_color_map<StorageMap> local_map;

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

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

public:
  two_bit_color_map(std::size_t inital_size,
                    const index_map_type& index = index_map_type())
    : inherited(index.process_group(),  index.global(),
                local_map(inital_size, index.base())) { }

  inherited&       base()       { return *this; }
  const inherited& base() const { return *this; }
};

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
inline two_bit_color_type
get(two_bit_color_map<
      parallel::distributed_property_map<
        ProcessGroup, GlobalMap, two_bit_color_map<StorageMap> > > const& pm,
    typename property_traits<GlobalMap>::key_type key)
{
  return get(pm.base(), key);
}

template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
inline void
put(two_bit_color_map<
      parallel::distributed_property_map<
        ProcessGroup, GlobalMap, two_bit_color_map<StorageMap> > > const& pm,
    typename property_traits<GlobalMap>::key_type key,
    two_bit_color_type value)
{
  put(pm.base(), key, value);
}

} // end namespace boost

#endif // BOOST_DISTRIBUTED_TWO_BIT_COLOR_MAP_HPP


code:
//
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Copyright 2009, Andrew Sutton
//
// 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_CONCEPTS_HPP
#define BOOST_GRAPH_CONCEPTS_HPP

#include <boost/config.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/numeric_values.hpp>
#include <boost/graph/buffer_concepts.hpp>
#include <boost/concept_check.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/mpl/not.hpp>
#include <boost/static_assert.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/concept/assert.hpp>

#include <boost/concept/detail/concept_def.hpp>
namespace boost
{
// dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
// you want to use vector_as_graph, it is!  I'm sure the graph
// library leaves these out all over the place.  Probably a
// redesign involving specializing a template with a static
// member function is in order :(
//
// It is needed in order to allow us to write using boost::vertices as
// needed for ADL when using vector_as_graph below.
#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)            \
 && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
# define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
#endif

#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
template <class T>
typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&);
#endif

    namespace concepts {
    BOOST_concept(MultiPassInputIterator,(T)) {
        BOOST_CONCEPT_USAGE(MultiPassInputIterator) {
            BOOST_CONCEPT_ASSERT((InputIterator<T>));
        }
    };

    BOOST_concept(Graph,(G))
    {
        typedef typename graph_traits<G>::vertex_descriptor vertex_descriptor;
        typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
        typedef typename graph_traits<G>::directed_category directed_category;
        typedef typename graph_traits<G>::edge_parallel_category edge_parallel_category;
        typedef typename graph_traits<G>::traversal_category traversal_category;

        BOOST_CONCEPT_USAGE(Graph)
        {
            BOOST_CONCEPT_ASSERT((DefaultConstructible<vertex_descriptor>));
            BOOST_CONCEPT_ASSERT((EqualityComparable<vertex_descriptor>));
            BOOST_CONCEPT_ASSERT((Assignable<vertex_descriptor>));
        }
        G g;
    };

    BOOST_concept(IncidenceGraph,(G))
        : Graph<G>
    {
        typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
        typedef typename graph_traits<G>::out_edge_iterator out_edge_iterator;
        typedef typename graph_traits<G>::degree_size_type degree_size_type;
        typedef typename graph_traits<G>::traversal_category traversal_category;

        BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<out_edge_iterator, void> >::value));
        BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<degree_size_type, void> >::value));

        BOOST_CONCEPT_USAGE(IncidenceGraph) {
            BOOST_CONCEPT_ASSERT((MultiPassInputIterator<out_edge_iterator>));
            BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>));
            BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>));
            BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>));
            BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
                                    incidence_graph_tag>));

            p = out_edges(u, g);
            n = out_degree(u, g);
            e = *p.first;
            u = source(e, g);
            v = target(e, g);
            const_constraints(g);
        }
        void const_constraints(const G& cg) {
            p = out_edges(u, cg);
            n = out_degree(u, cg);
            e = *p.first;
            u = source(e, cg);
            v = target(e, cg);
        }
        std::pair<out_edge_iterator, out_edge_iterator> p;
        typename graph_traits<G>::vertex_descriptor u, v;
        typename graph_traits<G>::edge_descriptor e;
        typename graph_traits<G>::degree_size_type n;
        G g;
    };

    BOOST_concept(BidirectionalGraph,(G))
        : IncidenceGraph<G>
    {
        typedef typename graph_traits<G>::in_edge_iterator
        in_edge_iterator;
        typedef typename graph_traits<G>::traversal_category
        traversal_category;

        BOOST_CONCEPT_USAGE(BidirectionalGraph) {
        BOOST_CONCEPT_ASSERT((MultiPassInputIterator<in_edge_iterator>));
        BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
            bidirectional_graph_tag>));

        BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<in_edge_iterator, void> >::value));

        p = in_edges(v, g);
        n = in_degree(v, g);
        n = degree(v, g);
        e = *p.first;
        const_constraints(g);
        }
        void const_constraints(const G& cg) {
        p = in_edges(v, cg);
        n = in_degree(v, cg);
        n = degree(v, cg);
        e = *p.first;
        }
        std::pair<in_edge_iterator, in_edge_iterator> p;
        typename graph_traits<G>::vertex_descriptor v;
        typename graph_traits<G>::edge_descriptor e;
        typename graph_traits<G>::degree_size_type n;
        G g;
    };

    BOOST_concept(AdjacencyGraph,(G))
        : Graph<G>
    {
        typedef typename graph_traits<G>::adjacency_iterator
        adjacency_iterator;
        typedef typename graph_traits<G>::traversal_category
        traversal_category;

        BOOST_CONCEPT_USAGE(AdjacencyGraph) {
        BOOST_CONCEPT_ASSERT((MultiPassInputIterator<adjacency_iterator>));
        BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
            adjacency_graph_tag>));

        BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<adjacency_iterator, void> >::value));

        p = adjacent_vertices(v, g);
        v = *p.first;
        const_constraints(g);
        }
        void const_constraints(const G& cg) {
        p = adjacent_vertices(v, cg);
        }
        std::pair<adjacency_iterator,adjacency_iterator> p;
        typename graph_traits<G>::vertex_descriptor v;
        G g;
    };

    BOOST_concept(VertexListGraph,(G))
        : Graph<G>
    {
        typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
        typedef typename graph_traits<G>::vertices_size_type vertices_size_type;
        typedef typename graph_traits<G>::traversal_category
        traversal_category;

        BOOST_CONCEPT_USAGE(VertexListGraph) {
        BOOST_CONCEPT_ASSERT((MultiPassInputIterator<vertex_iterator>));
        BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
            vertex_list_graph_tag>));

        BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<vertex_iterator, void> >::value));
        BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<vertices_size_type, void> >::value));

#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
        // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
        // you want to use vector_as_graph, it is!  I'm sure the graph
        // library leaves these out all over the place.  Probably a
        // redesign involving specializing a template with a static
        // member function is in order :(
        using boost::vertices;
#endif
        p = vertices(g);
        v = *p.first;
        const_constraints(g);
        }
        void const_constraints(const G& cg) {
#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
        // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
        // you want to use vector_as_graph, it is!  I'm sure the graph
        // library leaves these out all over the place.  Probably a
        // redesign involving specializing a template with a static
        // member function is in order :(
        using boost::vertices;
#endif

        p = vertices(cg);
        v = *p.first;
        V = num_vertices(cg);
        }
        std::pair<vertex_iterator,vertex_iterator> p;
        typename graph_traits<G>::vertex_descriptor v;
        G g;
        vertices_size_type V;
    };

    BOOST_concept(EdgeListGraph,(G))
        : Graph<G>
    {
        typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
        typedef typename graph_traits<G>::edge_iterator edge_iterator;
        typedef typename graph_traits<G>::edges_size_type edges_size_type;
        typedef typename graph_traits<G>::traversal_category
        traversal_category;

        BOOST_CONCEPT_USAGE(EdgeListGraph) {
        BOOST_CONCEPT_ASSERT((MultiPassInputIterator<edge_iterator>));
        BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>));
        BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>));
        BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>));
        BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
            edge_list_graph_tag>));

        BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<edge_iterator, void> >::value));
        BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<edges_size_type, void> >::value));

        p = edges(g);
        e = *p.first;
        u = source(e, g);
        v = target(e, g);
        const_constraints(g);
        }
        void const_constraints(const G& cg) {
        p = edges(cg);
        E = num_edges(cg);
        e = *p.first;
        u = source(e, cg);
        v = target(e, cg);
        }
        std::pair<edge_iterator,edge_iterator> p;
        typename graph_traits<G>::vertex_descriptor u, v;
        typename graph_traits<G>::edge_descriptor e;
        edges_size_type E;
        G g;
    };

    BOOST_concept(VertexAndEdgeListGraph,(G))
        : VertexListGraph<G>
        , EdgeListGraph<G>
    {
    };

    // Where to put the requirement for this constructor?
    //      G g(n_vertices);
    // Not in mutable graph, then LEDA graph's can't be models of
    // MutableGraph.
    BOOST_concept(EdgeMutableGraph,(G))
    {
        typedef typename graph_traits<G>::edge_descriptor edge_descriptor;

        BOOST_CONCEPT_USAGE(EdgeMutableGraph) {
        p = add_edge(u, v, g);
        remove_edge(u, v, g);
        remove_edge(e, g);
        clear_vertex(v, g);
        }
        G g;
        edge_descriptor e;
        std::pair<edge_descriptor, bool> p;
        typename graph_traits<G>::vertex_descriptor u, v;
    };

    BOOST_concept(VertexMutableGraph,(G))
    {

        BOOST_CONCEPT_USAGE(VertexMutableGraph) {
        v = add_vertex(g);
        remove_vertex(v, g);
        }
        G g;
        typename graph_traits<G>::vertex_descriptor u, v;
    };

    BOOST_concept(MutableGraph,(G))
        : EdgeMutableGraph<G>
        , VertexMutableGraph<G>
    {
    };

    template <class edge_descriptor>
    struct dummy_edge_predicate {
        bool operator()(const edge_descriptor&) const {
        return false;
        }
    };

    BOOST_concept(MutableIncidenceGraph,(G))
        : MutableGraph<G>
    {
        BOOST_CONCEPT_USAGE(MutableIncidenceGraph) {
        remove_edge(iter, g);
        remove_out_edge_if(u, p, g);
        }
        G g;
        typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
        dummy_edge_predicate<edge_descriptor> p;
        typename boost::graph_traits<G>::vertex_descriptor u;
        typename boost::graph_traits<G>::out_edge_iterator iter;
    };

    BOOST_concept(MutableBidirectionalGraph,(G))
        : MutableIncidenceGraph<G>
    {
        BOOST_CONCEPT_USAGE(MutableBidirectionalGraph)
        {
            remove_in_edge_if(u, p, g);
        }
        G g;
        typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
        dummy_edge_predicate<edge_descriptor> p;
        typename boost::graph_traits<G>::vertex_descriptor u;
    };

    BOOST_concept(MutableEdgeListGraph,(G))
        : EdgeMutableGraph<G>
    {
        BOOST_CONCEPT_USAGE(MutableEdgeListGraph) {
        remove_edge_if(p, g);
        }
        G g;
        typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
        dummy_edge_predicate<edge_descriptor> p;
    };

    BOOST_concept(VertexMutablePropertyGraph,(G))
        : VertexMutableGraph<G>
    {
        BOOST_CONCEPT_USAGE(VertexMutablePropertyGraph) {
        v = add_vertex(vp, g);
        }
        G g;
        typename graph_traits<G>::vertex_descriptor v;
        typename vertex_property_type<G>::type vp;
    };

    BOOST_concept(EdgeMutablePropertyGraph,(G))
        : EdgeMutableGraph<G>
    {
        typedef typename graph_traits<G>::edge_descriptor edge_descriptor;

        BOOST_CONCEPT_USAGE(EdgeMutablePropertyGraph) {
        p = add_edge(u, v, ep, g);
        }
        G g;
        std::pair<edge_descriptor, bool> p;
        typename graph_traits<G>::vertex_descriptor u, v;
        typename edge_property_type<G>::type ep;
    };

    BOOST_concept(AdjacencyMatrix,(G))
        : Graph<G>
    {
        typedef typename graph_traits<G>::edge_descriptor edge_descriptor;

        BOOST_CONCEPT_USAGE(AdjacencyMatrix) {
        p = edge(u, v, g);
        const_constraints(g);
        }
        void const_constraints(const G& cg) {
        p = edge(u, v, cg);
        }
        typename graph_traits<G>::vertex_descriptor u, v;
        std::pair<edge_descriptor, bool> p;
        G g;
    };

    BOOST_concept(ReadablePropertyGraph,(G)(X)(Property))
        : Graph<G>
    {
        typedef typename property_map<G, Property>::const_type const_Map;

        BOOST_CONCEPT_USAGE(ReadablePropertyGraph)
        {
        BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<const_Map, X>));

        const_constraints(g);
        }
        void const_constraints(const G& cg) {
        const_Map pmap = get(Property(), cg);
        pval = get(Property(), cg, x);
        ignore_unused_variable_warning(pmap);
        }
        G g;
        X x;
        typename property_traits<const_Map>::value_type pval;
    };

    BOOST_concept(PropertyGraph,(G)(X)(Property))
        : ReadablePropertyGraph<G, X, Property>
    {
        typedef typename property_map<G, Property>::type Map;
        BOOST_CONCEPT_USAGE(PropertyGraph) {
        BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept<Map, X>));

        Map pmap = get(Property(), g);
        pval = get(Property(), g, x);
        put(Property(), g, x, pval);
        ignore_unused_variable_warning(pmap);
        }
        G g;
        X x;
        typename property_traits<Map>::value_type pval;
    };

    BOOST_concept(LvaluePropertyGraph,(G)(X)(Property))
        : ReadablePropertyGraph<G, X, Property>
    {
        typedef typename property_map<G, Property>::type Map;
        typedef typename property_map<G, Property>::const_type const_Map;

        BOOST_CONCEPT_USAGE(LvaluePropertyGraph) {
        BOOST_CONCEPT_ASSERT((LvaluePropertyMapConcept<const_Map, X>));

        pval = get(Property(), g, x);
        put(Property(), g, x, pval);
        }
        G g;
        X x;
        typename property_traits<Map>::value_type pval;
    };

    // The *IndexGraph concepts are "semantic" graph concpepts. These can be
    // applied to describe any graph that has an index map that can be accessed
    // using the get(*_index, g) method. For example, adjacency lists with
    // VertexSet == vecS are implicitly models of this concept.
    //
    // NOTE: We could require an associated type vertex_index_type, but that
    // would mean propagating that type name into graph_traits and all of the
    // other graph implementations. Much easier to simply call it unsigned.

    BOOST_concept(VertexIndexGraph,(Graph))
    {
        BOOST_CONCEPT_USAGE(VertexIndexGraph)
        {
            typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
            typedef typename property_map<Graph, vertex_index_t>::type Map;
            typedef unsigned Index; // This could be Graph::vertex_index_type
            Map m = get(vertex_index, g);
            Index x = get(vertex_index, g, Vertex());
            ignore_unused_variable_warning(m);
            ignore_unused_variable_warning(x);

            // This is relaxed
            renumber_vertex_indices(g);

            const_constraints(g);
        }
        void const_constraints(const Graph& g_)
        {
            typedef typename property_map<Graph, vertex_index_t>::const_type Map;
            Map m = get(vertex_index, g_);
            ignore_unused_variable_warning(m);
        }
    private:
        Graph g;
    };

    BOOST_concept(EdgeIndexGraph,(Graph))
    {
        BOOST_CONCEPT_USAGE(EdgeIndexGraph)
        {
            typedef typename graph_traits<Graph>::edge_descriptor Edge;
            typedef typename property_map<Graph, edge_index_t>::type Map;
            typedef unsigned Index; // This could be Graph::vertex_index_type
            Map m = get(edge_index, g);
            Index x = get(edge_index, g, Edge());
            ignore_unused_variable_warning(m);
            ignore_unused_variable_warning(x);

            // This is relaxed
            renumber_edge_indices(g);

            const_constraints(g);
        }
        void const_constraints(const Graph& g_)
        {
            typedef typename property_map<Graph, edge_index_t>::const_type Map;
            Map m = get(edge_index, g_);
            ignore_unused_variable_warning(m);
        }
    private:
        Graph g;
    };

    BOOST_concept(ColorValue,(C))
        : EqualityComparable<C>
        , DefaultConstructible<C>
    {
        BOOST_CONCEPT_USAGE(ColorValue) {
        c = color_traits<C>::white();
        c = color_traits<C>::gray();
        c = color_traits<C>::black();
        }
        C c;
    };

    BOOST_concept(BasicMatrix,(M)(I)(V))
    {
        BOOST_CONCEPT_USAGE(BasicMatrix) {
        V& elt = A[i][j];
        const_constraints(A);
        ignore_unused_variable_warning(elt);
        }
        void const_constraints(const M& cA) {
        const V& elt = cA[i][j];
        ignore_unused_variable_warning(elt);
        }
        M A;
        I i, j;
    };

    // The following concepts describe aspects of numberic values and measure
    // functions. We're extending the notion of numeric values to include
    // emulation for zero and infinity.

    BOOST_concept(NumericValue,(Numeric))
    {
        BOOST_CONCEPT_USAGE(NumericValue)
        {
            BOOST_CONCEPT_ASSERT(( DefaultConstructible<Numeric> ));
            BOOST_CONCEPT_ASSERT(( CopyConstructible<Numeric> ));
            numeric_values<Numeric>::zero();
            numeric_values<Numeric>::infinity();
        }
    };

    BOOST_concept(DegreeMeasure,(Measure)(Graph))
    {
        BOOST_CONCEPT_USAGE(DegreeMeasure)
        {
            typedef typename Measure::degree_type Degree;
            typedef typename Measure::vertex_type Vertex;

            Degree d = m(Vertex(), g);
            ignore_unused_variable_warning(d);
        }
    private:
        Measure m;
        Graph g;
    };

    BOOST_concept(DistanceMeasure,(Measure)(Graph))
    {
        BOOST_CONCEPT_USAGE(DistanceMeasure)
        {
            typedef typename Measure::distance_type Distance;
            typedef typename Measure::result_type Result;
            Result r = m(Distance(), g);
            ignore_unused_variable_warning(r);
        }
    private:
        Measure m;
        Graph g;
    };

} /* namespace concepts */

using boost::concepts::MultiPassInputIteratorConcept;

// Graph concepts
using boost::concepts::GraphConcept;
using boost::concepts::IncidenceGraphConcept;
using boost::concepts::BidirectionalGraphConcept;
using boost::concepts::AdjacencyGraphConcept;
using boost::concepts::VertexListGraphConcept;
using boost::concepts::EdgeListGraphConcept;
using boost::concepts::VertexAndEdgeListGraphConcept;
using boost::concepts::EdgeMutableGraphConcept;
using boost::concepts::VertexMutableGraphConcept;
using boost::concepts::MutableGraphConcept;
using boost::concepts::MutableIncidenceGraphConcept;
using boost::concepts::MutableBidirectionalGraphConcept;
using boost::concepts::MutableEdgeListGraphConcept;
using boost::concepts::VertexMutablePropertyGraphConcept;
using boost::concepts::EdgeMutablePropertyGraphConcept;
using boost::concepts::AdjacencyMatrixConcept;
using boost::concepts::ReadablePropertyGraphConcept;
using boost::concepts::PropertyGraphConcept;
using boost::concepts::LvaluePropertyGraphConcept;
using boost::concepts::VertexIndexGraphConcept;
using boost::concepts::EdgeIndexGraphConcept;

// Utility concepts
using boost::concepts::ColorValueConcept;
using boost::concepts::BasicMatrixConcept;
using boost::concepts::NumericValueConcept;
using boost::concepts::DistanceMeasureConcept;
using boost::concepts::DegreeMeasureConcept;

} /* namespace boost */
#include <boost/concept/detail/concept_undef.hpp>

#endif /* BOOST_GRAPH_CONCEPTS_H */


code:
// Copyright (C) 2009 Andrew Sutton
//
// 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)

#ifndef BOOST_GRAPH_MUTABILITY_TRAITS_HPP
#define BOOST_GRAPH_MUTABILITY_TRAITS_HPP

#include <boost/config.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/type_traits/is_same.hpp>

namespace boost {

// The mutabiltiy categories classify graphs by their mutating operations
// on the edge and vertex sets. This is a substantially more refined
// categorization than the MutableGraph and MutablePropertyGraph denote.
// Currently, this framework is only used in the graph tests to help
// dispatch test to the correct places. However, there are probably some
// constructive or destructive algorithms (i.e., graph generators) that
// may use these to describe requirements on graph inputs.

struct add_vertex_tag { };
struct add_vertex_property_tag : virtual add_vertex_tag { };
struct add_edge_tag { };
struct add_edge_property_tag : virtual add_edge_tag { };
struct remove_vertex_tag { };
struct remove_edge_tag { };

struct mutable_vertex_graph_tag
    : virtual add_vertex_tag, virtual remove_vertex_tag
{ };
struct mutable_vertex_property_graph_tag
    : virtual add_vertex_property_tag, virtual remove_vertex_tag
{ };

struct mutable_edge_graph_tag
    : virtual add_edge_tag, virtual remove_edge_tag
{ };
struct mutable_edge_property_graph_tag
    : virtual add_edge_property_tag, virtual remove_edge_tag
{ };

struct mutable_graph_tag
    : virtual mutable_vertex_graph_tag
    , virtual mutable_edge_graph_tag
{ };
struct mutable_property_graph_tag
    : virtual mutable_vertex_property_graph_tag
    , virtual mutable_edge_property_graph_tag
{ };

// Some graphs just don't like to be torn down. Note this only restricts
// teardown to the set of vertices, not the vertex set.
// TODO: Find a better name for this tag.
struct add_only_property_graph_tag
    : virtual add_vertex_property_tag
    , virtual mutable_edge_property_graph_tag
{ };

/**
 * The graph_mutability_traits provide methods for determining the
 * interfaces supported by graph classes for adding and removing vertices
 * and edges.
 */
template <typename Graph>
struct graph_mutability_traits {
    typedef typename Graph::mutability_category category;
};

template <typename Graph>
struct graph_has_add_vertex
    : mpl::bool_<
        is_convertible<
            typename graph_mutability_traits<Graph>::category,
            add_vertex_tag
        >::value
    >
{ };

template <typename Graph>
struct graph_has_add_vertex_with_property
    : mpl::bool_<
        is_convertible<
            typename graph_mutability_traits<Graph>::category,
            add_vertex_property_tag
        >::value
    >
{ };

template <typename Graph>
struct graph_has_remove_vertex
    : mpl::bool_<
        is_convertible<
            typename graph_mutability_traits<Graph>::category,
            remove_vertex_tag
        >::value
    >
{ };

template <typename Graph>
struct graph_has_add_edge
    : mpl::bool_<
        is_convertible<
            typename graph_mutability_traits<Graph>::category,
            add_edge_tag
        >::value
    >
{ };

template <typename Graph>
struct graph_has_add_edge_with_property
    : mpl::bool_<
        is_convertible<
            typename graph_mutability_traits<Graph>::category,
            add_edge_property_tag
        >::value
    >
{ };

template <typename Graph>
struct graph_has_remove_edge
    : mpl::bool_<
        is_convertible<
            typename graph_mutability_traits<Graph>::category,
            remove_edge_tag
        >::value
    >
{ };

template <typename Graph>
struct is_mutable_vertex_graph
    : mpl::and_<
        graph_has_add_vertex<Graph>,
        graph_has_remove_vertex<Graph>
    >
{ };

template <typename Graph>
struct is_mutable_vertex_property_graph
    : mpl::and_<
        graph_has_add_vertex_with_property<Graph>,
        graph_has_remove_vertex<Graph>
    >
{ };

template <typename Graph>
struct is_mutable_edge_graph
    : mpl::and_<
        graph_has_add_edge<Graph>,
        graph_has_remove_edge<Graph>
    >
{ };

template <typename Graph>
struct is_mutable_edge_property_graph
    : mpl::and_<
        graph_has_add_edge_with_property<Graph>,
        graph_has_remove_edge<Graph>
    >
{ };

template <typename Graph>
struct is_mutable_graph
    : mpl::and_<
        is_mutable_vertex_graph<Graph>,
        is_mutable_edge_graph<Graph>
    >
{ };

template <typename Graph>
struct is_mutable_property_graph
    : mpl::and_<
        is_mutable_vertex_property_graph<Graph>,
        is_mutable_edge_property_graph<Graph>
    >
{ };

template <typename Graph>
struct is_add_only_property_graph
    : mpl::bool_<
        is_convertible<
            typename graph_mutability_traits<Graph>::category,
            add_only_property_graph_tag
        >::value
    >
{ };

/** @name Mutability Traits Specializations */
//@{

//@}

} // namespace boost

#endif


code:
//=======================================================================
// Copyright 2002 Indiana University.
// 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_SELECTORS_HPP
#define BOOST_GRAPH_SELECTORS_HPP

#include <boost/mpl/bool.hpp>

namespace boost {

  //===========================================================================
  // Selectors for the Directed template parameter of adjacency_list
  // and adjacency_matrix.

  struct directedS { enum { is_directed = true, is_bidir = false };
    typedef mpl::true_ is_directed_t;
    typedef mpl::false_ is_bidir_t;
  };
  struct undirectedS {
    enum { is_directed = false, is_bidir = false };
    typedef mpl::false_ is_directed_t;
    typedef mpl::false_ is_bidir_t;
  };
  struct bidirectionalS {
    enum { is_directed = true, is_bidir = true };
    typedef mpl::true_ is_directed_t;
    typedef mpl::true_ is_bidir_t;
  };

} // namespace boost

#endif // BOOST_GRAPH_SELECTORS_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_TRAITS_HPP
#define BOOST_GRAPH_TRAITS_HPP

#include <boost/config.hpp>
#include <iterator>
#include <utility> /* Primarily for std::pair */
#include <boost/tuple/tuple.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/not.hpp>
#include <boost/mpl/has_xxx.hpp>
#include <boost/mpl/void.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/iterator/iterator_categories.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/pending/property.hpp>
#include <boost/detail/workaround.hpp>

namespace boost {

    namespace detail {
#define BOOST_GRAPH_MEMBER_OR_VOID(name) \
      BOOST_MPL_HAS_XXX_TRAIT_DEF(name) \
      template <typename T> struct BOOST_JOIN(get_member_, name) {typedef typename T::name type;}; \
      template <typename T> struct BOOST_JOIN(get_opt_member_, name): \
        boost::mpl::eval_if_c< \
          BOOST_JOIN(has_, name)<T>::value, \
          BOOST_JOIN(get_member_, name)<T>, \
          boost::mpl::identity<void> > \
        {};
      BOOST_GRAPH_MEMBER_OR_VOID(adjacency_iterator)
      BOOST_GRAPH_MEMBER_OR_VOID(out_edge_iterator)
      BOOST_GRAPH_MEMBER_OR_VOID(in_edge_iterator)
      BOOST_GRAPH_MEMBER_OR_VOID(vertex_iterator)
      BOOST_GRAPH_MEMBER_OR_VOID(edge_iterator)
      BOOST_GRAPH_MEMBER_OR_VOID(vertices_size_type)
      BOOST_GRAPH_MEMBER_OR_VOID(edges_size_type)
      BOOST_GRAPH_MEMBER_OR_VOID(degree_size_type)
    }

    template <typename G>
    struct graph_traits {
#define BOOST_GRAPH_PULL_OPT_MEMBER(name) \
        typedef typename detail::BOOST_JOIN(get_opt_member_, name)<G>::type name;

        typedef typename G::vertex_descriptor      vertex_descriptor;
        typedef typename G::edge_descriptor        edge_descriptor;
        BOOST_GRAPH_PULL_OPT_MEMBER(adjacency_iterator)
        BOOST_GRAPH_PULL_OPT_MEMBER(out_edge_iterator)
        BOOST_GRAPH_PULL_OPT_MEMBER(in_edge_iterator)
        BOOST_GRAPH_PULL_OPT_MEMBER(vertex_iterator)
        BOOST_GRAPH_PULL_OPT_MEMBER(edge_iterator)

        typedef typename G::directed_category      directed_category;
        typedef typename G::edge_parallel_category edge_parallel_category;
        typedef typename G::traversal_category     traversal_category;

        BOOST_GRAPH_PULL_OPT_MEMBER(vertices_size_type)
        BOOST_GRAPH_PULL_OPT_MEMBER(edges_size_type)
        BOOST_GRAPH_PULL_OPT_MEMBER(degree_size_type)
#undef BOOST_GRAPH_PULL_OPT_MEMBER

        static inline vertex_descriptor null_vertex();
    };

    template <typename G>
    inline typename graph_traits<G>::vertex_descriptor
    graph_traits<G>::null_vertex()
    { return G::null_vertex(); }

    // directed_category tags
    struct directed_tag { };
    struct undirected_tag { };
    struct bidirectional_tag : public directed_tag { };

    namespace detail {
        inline bool is_directed(directed_tag) { return true; }
        inline bool is_directed(undirected_tag) { return false; }
    }

    /** Return true if the given graph is directed. */
    template <typename Graph>
    bool is_directed(const Graph&) {
        typedef typename graph_traits<Graph>::directed_category Cat;
        return detail::is_directed(Cat());
    }

    /** Return true if the given graph is undirected. */
    template <typename Graph>
    bool is_undirected(const Graph& g) {
        return !is_directed(g);
    }

    /** @name Directed/Undirected Graph Traits */
    //@{
    namespace graph_detail {
        template <typename Tag>
        struct is_directed_tag
            : mpl::bool_<is_convertible<Tag, directed_tag>::value>
        { };
    } // namespace graph_detail

    template <typename Graph>
    struct is_directed_graph
        : graph_detail::is_directed_tag<
            typename graph_traits<Graph>::directed_category
        >
    { };

    template <typename Graph>
    struct is_undirected_graph
        : mpl::not_< is_directed_graph<Graph> >
    { };
    //@}

    // edge_parallel_category tags
    struct allow_parallel_edge_tag { };
    struct disallow_parallel_edge_tag { };

    namespace detail {
        inline bool allows_parallel(allow_parallel_edge_tag) { return true; }
        inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }
    }

    template <typename Graph>
    bool allows_parallel_edges(const Graph&) {
        typedef typename graph_traits<Graph>::edge_parallel_category Cat;
        return detail::allows_parallel(Cat());
    }

    /** @name Parallel Edges Traits */
    //@{
    /**
     * The is_multigraph metafunction returns true if the graph allows
     * parallel edges. Technically, a multigraph is a simple graph that
     * allows parallel edges, but since there are no traits for the allowance
     * or disallowance of loops, this is a moot point.
     */
    template <typename Graph>
    struct is_multigraph
        : mpl::bool_<
            is_same<
                typename graph_traits<Graph>::edge_parallel_category,
                allow_parallel_edge_tag
            >::value
        >
    { };
    //@}

    // traversal_category tags
    struct incidence_graph_tag { };
    struct adjacency_graph_tag { };
    struct bidirectional_graph_tag : virtual incidence_graph_tag { };
    struct vertex_list_graph_tag { };
    struct edge_list_graph_tag { };
    struct adjacency_matrix_tag { };

    // Parallel traversal_category tags
    struct distributed_graph_tag { };
    struct distributed_vertex_list_graph_tag { };
    struct distributed_edge_list_graph_tag { };
#define BOOST_GRAPH_SEQUENTIAL_TRAITS_DEFINES_DISTRIBUTED_TAGS // Disable these from external versions of PBGL

    /** @name Traversal Category Traits
     * These traits classify graph types by their supported methods of
     * vertex and edge traversal.
     */
    //@{
    template <typename Graph>
    struct is_incidence_graph
        : mpl::bool_<
            is_convertible<
                typename graph_traits<Graph>::traversal_category,
                incidence_graph_tag
            >::value
        >
    { };

    template <typename Graph>
    struct is_bidirectional_graph
        : mpl::bool_<
            is_convertible<
                typename graph_traits<Graph>::traversal_category,
                bidirectional_graph_tag
            >::value
        >
    { };

    template <typename Graph>
    struct is_vertex_list_graph
        : mpl::bool_<
            is_convertible<
                typename graph_traits<Graph>::traversal_category,
                vertex_list_graph_tag
            >::value
        >
    { };

    template <typename Graph>
    struct is_edge_list_graph
        : mpl::bool_<
            is_convertible<
                typename graph_traits<Graph>::traversal_category,
                edge_list_graph_tag
            >::value
        >
    { };

    template <typename Graph>
    struct is_adjacency_matrix
        : mpl::bool_<
            is_convertible<
                typename graph_traits<Graph>::traversal_category,
                adjacency_matrix_tag
            >::value
        >
    { };
    //@}

    /** @name Directed Graph Traits
     * These metafunctions are used to fully classify directed vs. undirected
     * graphs. Recall that an undirected graph is also bidirectional, but it
     * cannot be both undirected and directed at the same time.
     */
    //@{
    template <typename Graph>
    struct is_directed_unidirectional_graph
        : mpl::and_<
            is_directed_graph<Graph>, mpl::not_< is_bidirectional_graph<Graph> >
        >
    { };

    template <typename Graph>
    struct is_directed_bidirectional_graph
        : mpl::and_<
            is_directed_graph<Graph>, is_bidirectional_graph<Graph>
        >
    { };
    //@}

    //?? not the right place ?? Lee
    typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;

    namespace detail {
      BOOST_MPL_HAS_XXX_TRAIT_DEF(graph_property_type)
      BOOST_MPL_HAS_XXX_TRAIT_DEF(edge_property_type)
      BOOST_MPL_HAS_XXX_TRAIT_DEF(vertex_property_type)

      template <typename G> struct get_graph_property_type {typedef typename G::graph_property_type type;};
      template <typename G> struct get_edge_property_type {typedef typename G::edge_property_type type;};
      template <typename G> struct get_vertex_property_type {typedef typename G::vertex_property_type type;};
    }

    template <typename G>
    struct graph_property_type
      : boost::mpl::eval_if<detail::has_graph_property_type<G>,
                            detail::get_graph_property_type<G>,
                            no_property> {};
    template <typename G>
    struct edge_property_type
      : boost::mpl::eval_if<detail::has_edge_property_type<G>,
                            detail::get_edge_property_type<G>,
                            no_property> {};
    template <typename G>
    struct vertex_property_type
      : boost::mpl::eval_if<detail::has_vertex_property_type<G>,
                            detail::get_vertex_property_type<G>,
                            no_property> {};

    template<typename G>
    struct graph_bundle_type {
      typedef typename G::graph_bundled type;
    };

    template<typename G>
    struct vertex_bundle_type {
      typedef typename G::vertex_bundled type;
    };

    template<typename G>
    struct edge_bundle_type {
      typedef typename G::edge_bundled type;
    };

    namespace graph { namespace detail {
        template<typename Graph, typename Descriptor>
        class bundled_result {
            typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
            typedef typename mpl::if_c<(is_same<Descriptor, Vertex>::value),
                                        vertex_bundle_type<Graph>,
                                        edge_bundle_type<Graph> >::type bundler;
        public:
            typedef typename bundler::type type;
        };

        template<typename Graph>
        class bundled_result<Graph, graph_bundle_t> {
            typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
            typedef graph_bundle_type<Graph> bundler;
        public:
            typedef typename bundler::type type;
        };

    } } // namespace graph::detail

    namespace graph_detail {
      // A helper metafunction for determining whether or not a type is
      // bundled.
      template <typename T>
      struct is_no_bundle : mpl::bool_<is_same<T, no_property>::value>
      { };
    } // namespace graph_detail

    /** @name Graph Property Traits
     * These metafunctions (along with those above), can be used to access the
     * vertex and edge properties (bundled or otherwise) of vertices and
     * edges.
     */
    //@{
    template<typename Graph>
    struct has_graph_property
      : mpl::not_<
        typename detail::is_no_property<
          typename graph_property_type<Graph>::type
        >::type
      >::type
    { };

    template<typename Graph>
    struct has_bundled_graph_property
      : mpl::not_<
        graph_detail::is_no_bundle<typename graph_bundle_type<Graph>::type>
      >
    { };

    template <typename Graph>
    struct has_vertex_property
        : mpl::not_<
            typename detail::is_no_property<typename vertex_property_type<Graph>::type>
        >::type
    { };

    template <typename Graph>
    struct has_bundled_vertex_property
        : mpl::not_<
            graph_detail::is_no_bundle<typename vertex_bundle_type<Graph>::type>
        >
    { };

    template <typename Graph>
    struct has_edge_property
        : mpl::not_<
            typename detail::is_no_property<typename edge_property_type<Graph>::type>
        >::type
    { };

    template <typename Graph>
    struct has_bundled_edge_property
        : mpl::not_<
            graph_detail::is_no_bundle<typename edge_bundle_type<Graph>::type>
        >
    { };
    //@}

} // namespace boost

// Since pair is in namespace std, Koenig lookup will find source and
// target if they are also defined in namespace std.  This is illegal,
// but the alternative is to put source and target in the global
// namespace which causes name conflicts with other libraries (like
// SUIF).
namespace std {

  /* Some helper functions for dealing with pairs as edges */
  template <class T, class G>
  T source(pair<T,T> p, const G&) { return p.first; }

  template <class T, class G>
  T target(pair<T,T> p, const G&) { return p.second; }

}

#if defined(__GNUC__) && defined(__SGI_STL_PORT)
// For some reason g++ with STLport does not see the above definition
// of source() and target() unless we bring them into the boost
// namespace.
namespace boost {
  using std::source;
  using std::target;
}
#endif

#endif // BOOST_GRAPH_TRAITS_HPP


code:
//=======================================================================
// Copyright 2001 Indiana University
// Author: 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_ITERATION_MACROS_HPP
#define BOOST_GRAPH_ITERATION_MACROS_HPP

#include <utility>

#define BGL_CAT(x,y) x ## y
#define BGL_RANGE(linenum) BGL_CAT(bgl_range_,linenum)
#define BGL_FIRST(linenum) (BGL_RANGE(linenum).first)
#define BGL_LAST(linenum) (BGL_RANGE(linenum).second)

/*
  BGL_FORALL_VERTICES_T(v, g, graph_t)  // This is on line 9
  expands to the following, but all on the same line

  for (typename boost::graph_traits<graph_t>::vertex_iterator
           bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;
       bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)
    for (typename boost::graph_traits<graph_t>::vertex_descriptor v;
         bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;
         ++bgl_first_9)

  The purpose of having two for-loops is just to provide a place to
  declare both the iterator and value variables. There is really only
  one loop. The stopping condition gets executed two more times than it
  usually would be, oh well. The reason for the bgl_first_9 = bgl_last_9
  in the outer for-loop is in case the user puts a break statement
  in the inner for-loop.

  The other macros work in a similar fashion.

  Use the _T versions when the graph type is a template parameter or
  dependent on a template parameter. Otherwise use the non _T versions.

  -----------------------
  6/9/09 THK

  The above contains two calls to the vertices function. I modified these
  macros to expand to

    for (std::pair<typename boost::graph_traits<graph_t>::vertex_iterator,
                   typename boost::graph_traits<graph_t>::vertex_iterator> bgl_range_9 = vertices(g);
       bgl_range_9.first != bgl_range_9.second;
       bgl_range_9.first = bgl_range_9.second)
    for (typename boost::graph_traits<graph_t>::vertex_descriptor v;
         bgl_range_9.first != bgl_range_9.second ? (v = *bgl_range_9.first, true) : false;
         ++bgl_range_9.first)

 */

#define BGL_FORALL_VERTICES_T(VNAME, GNAME, GraphType) \
for (std::pair<typename boost::graph_traits<GraphType>::vertex_iterator, \
               typename boost::graph_traits<GraphType>::vertex_iterator> BGL_RANGE(__LINE__) = vertices(GNAME); \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
  for (typename boost::graph_traits<GraphType>::vertex_descriptor VNAME; \
    BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (VNAME = *BGL_FIRST(__LINE__), true):false; \
     ++BGL_FIRST(__LINE__))

#define BGL_FORALL_VERTICES(VNAME, GNAME, GraphType) \
for (std::pair<boost::graph_traits<GraphType>::vertex_iterator, \
               boost::graph_traits<GraphType>::vertex_iterator> BGL_RANGE(__LINE__) = vertices(GNAME); \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
  for (boost::graph_traits<GraphType>::vertex_descriptor VNAME; \
    BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (VNAME = *BGL_FIRST(__LINE__), true):false; \
     ++BGL_FIRST(__LINE__))

#define BGL_FORALL_EDGES_T(ENAME, GNAME, GraphType) \
for (std::pair<typename boost::graph_traits<GraphType>::edge_iterator, \
               typename boost::graph_traits<GraphType>::edge_iterator> BGL_RANGE(__LINE__) = edges(GNAME); \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
  for (typename boost::graph_traits<GraphType>::edge_descriptor ENAME; \
    BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true):false; \
     ++BGL_FIRST(__LINE__))

#define BGL_FORALL_EDGES(ENAME, GNAME, GraphType) \
for (std::pair<boost::graph_traits<GraphType>::edge_iterator, \
               boost::graph_traits<GraphType>::edge_iterator> BGL_RANGE(__LINE__) = edges(GNAME); \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
  for (boost::graph_traits<GraphType>::edge_descriptor ENAME; \
     BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true):false; \
     ++BGL_FIRST(__LINE__))

#define BGL_FORALL_ADJ_T(UNAME, VNAME, GNAME, GraphType) \
for (std::pair<typename boost::graph_traits<GraphType>::adjacency_iterator, \
               typename boost::graph_traits<GraphType>::adjacency_iterator> BGL_RANGE(__LINE__) = adjacent_vertices(UNAME, GNAME); \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (typename boost::graph_traits<GraphType>::vertex_descriptor VNAME; \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (VNAME = *BGL_FIRST(__LINE__), true) : false; \
   ++BGL_FIRST(__LINE__))

#define BGL_FORALL_ADJ(UNAME, VNAME, GNAME, GraphType) \
for (std::pair<boost::graph_traits<GraphType>::adjacency_iterator, \
               boost::graph_traits<GraphType>::adjacency_iterator> BGL_RANGE(__LINE__) = adjacent_vertices(UNAME, GNAME); \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (boost::graph_traits<GraphType>::vertex_descriptor VNAME; \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (VNAME = *BGL_FIRST(__LINE__), true) : false; \
   ++BGL_FIRST(__LINE__))

#define BGL_FORALL_OUTEDGES_T(UNAME, ENAME, GNAME, GraphType) \
for (std::pair<typename boost::graph_traits<GraphType>::out_edge_iterator, \
               typename boost::graph_traits<GraphType>::out_edge_iterator> BGL_RANGE(__LINE__) = out_edges(UNAME, GNAME); \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (typename boost::graph_traits<GraphType>::edge_descriptor ENAME; \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true) : false; \
   ++BGL_FIRST(__LINE__))

#define BGL_FORALL_OUTEDGES(UNAME, ENAME, GNAME, GraphType) \
for (std::pair<boost::graph_traits<GraphType>::out_edge_iterator, \
               boost::graph_traits<GraphType>::out_edge_iterator> BGL_RANGE(__LINE__) = out_edges(UNAME, GNAME); \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (boost::graph_traits<GraphType>::edge_descriptor ENAME; \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true) : false; \
   ++BGL_FIRST(__LINE__))

#define BGL_FORALL_INEDGES_T(UNAME, ENAME, GNAME, GraphType) \
for (std::pair<typename boost::graph_traits<GraphType>::in_edge_iterator, \
               typename boost::graph_traits<GraphType>::in_edge_iterator> BGL_RANGE(__LINE__) = in_edges(UNAME, GNAME); \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (typename boost::graph_traits<GraphType>::edge_descriptor ENAME; \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true) : false; \
   ++BGL_FIRST(__LINE__))

#define BGL_FORALL_INEDGES(UNAME, ENAME, GNAME, GraphType) \
for (std::pair<boost::graph_traits<GraphType>::in_edge_iterator, \
               boost::graph_traits<GraphType>::in_edge_iterator> BGL_RANGE(__LINE__) = in_edges(UNAME, GNAME); \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (boost::graph_traits<GraphType>::edge_descriptor ENAME; \
  BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true) : false; \
   ++BGL_FIRST(__LINE__))

#endif // BOOST_GRAPH_ITERATION_MACROS_HPP