---

PG_algorithm.hpp

#ifndef _PG_ALGORITHM_HPP_
#define _PG_ALGORITHM_HPP_

#include "boost/tuple/tuple.hpp"
#include <limits>

namespace ParGraph
{

template< class Graph, class Functor >
void for_each_vertex( Graph & g, Functor & f )
{
  typedef typename Graph::VertexIterator Iter;
  Iter iter, end;

  boost::tie( iter, end ) = g.get_local_vertices();
  for(; iter != end ; iter++ )
  {
    f( *iter );
  }
}

template< class Graph, class Iterator, class Functor >
void for_each_vertex( Graph & g, Iterator begin, Iterator end, Functor & f )
{
  for( Iterator iter = begin ; iter != end ; iter++ )
  {
     f( g.get_known_vertex( *iter ) );
  }
}

template< class Graph, class EdgeMap, class Functor >
void for_each_out_edge( Graph & g, EdgeMap m, Functor & f )
{
  typedef typename Graph::VertexIterator VIter;
  typedef typename EdgeMap::out_iterator EIter;
  VIter viter, vend;

  boost::tie( viter, vend ) = g.get_local_vertices();
  for(; viter != vend ; viter++ )
  {
    EIter eiter, eend;
    boost::tie( eiter, eend ) = out_edges( g, *viter, m );
    for(; eiter != eend ; eiter++ )
    {
      f( *eiter );
    }
  }
}

template< class Graph, class Iterator, class EdgeMap, class Functor >
void
for_each_adjacent_vertex( Graph &g, Iterator vset_begin, Iterator vset_end, EdgeMap emap, Functor &f )
{
  AllToAllBuffer forward_buffer;

  for( Iterator vset_it = vset_begin ; vset_it != vset_end ; vset_it++ )
  {
    typename EdgeMap::out_iterator e_it, e_end, e_next;
    typename Graph::KnownVertex v1 = *vset_it;

    boost::tie( e_it, e_end ) = out_edges( g, v1, emap );
    for( ; e_it != e_end ; e_it = e_next )
    {
      e_next = e_it; e_next++; // with this, the user is able to erase e_it without problems
      typename Graph::KnownVertex v2 = target( *e_it, g );
      if( g.is_vertex_local( v2 ) )
      {
        f.local_computation( v1, *e_it, v2 );
      }
      else
      {
        forward_buffer.set_proc( g.owning_processor( v2 ) );
        VertexID_t v = get_id(v1);
        forward_buffer.put( &v, 1 );
        EdgeID_t e = get_edge_id(*e_it);
        forward_buffer.put( &e, 1 );
        v = get_id(v2);
        forward_buffer.put( &v, 1 );
        typename Functor::first_property_type tmp_prop = 
            f.first_computation_on_v1( v1, *e_it, v2 );
        put_property_into_buffer( tmp_prop, forward_buffer );
      }
    }
  }

  forward_buffer.communicate();

  while( !forward_buffer.is_empty() )
  {
    VertexID_t v1id, v2id;
    EdgeID_t e;
    proc_t p = forward_buffer.get( &v1id, 1 );
    forward_buffer.get( &e, 1 );
    forward_buffer.get( &v2id, 1 );
    typename Functor::first_property_type tmp_prop;
    get_property_from_buffer( tmp_prop, forward_buffer );
    typename Functor::second_property_type tmp_prop2 =
        f.first_computation_on_v2( v1id, e, v2id, tmp_prop );
    forward_buffer.set_proc( p );
    forward_buffer.put( &v1id, 1 );
    forward_buffer.put( &e, 1 );
    forward_buffer.put( &v2id, 1 );
    put_property_into_buffer( tmp_prop2, forward_buffer );
  }

  forward_buffer.communicate();

  while( !forward_buffer.is_empty() )
  {
    VertexID_t v1id, v2id;
    EdgeID_t e;
    forward_buffer.get( &v1id, 1 );
    forward_buffer.get( &e, 1 );
    forward_buffer.get( &v2id, 1 );
    typename Functor::second_property_type tmp_prop2;
    get_property_from_buffer( tmp_prop2, forward_buffer );
    f.second_computation_on_v1( v1id, e, v2id, tmp_prop2 );
  }
}

template< class Set, class Type >
inline void insert( Set & s, Type v )
{
  s.insert( v );
}

template< class Type >
inline void insert( std::vector<Type> & s, Type v )
{
  s.push_back( v );
}

template< class Type >
inline void insert( std::list<Type> & s, Type v )
{
  s.push_back( v );
}

struct bfs_level_tag {};

template< class Graph, class LevelMap, class Set, class Visitors >
struct bfs_inner_part
{
  typedef typename Visitors::first_property_type first_property_type;
  typedef typename Visitors::second_property_type second_property_user_type; 
  typedef property< bfs_level_tag, typename LevelMap::value_type, second_property_user_type > second_property_type;

  Graph & g;
  LevelMap lmap;
  typename LevelMap::value_type current_level;
  Visitors & vis;
  Set * grayset;

  bfs_inner_part( Graph & _g, LevelMap _l, Visitors & _vis ) : 
      g(_g), lmap(_l), current_level(0), vis(_vis) { }

  template< class Edge >
  void local_computation( typename Graph::KnownVertex v1, Edge e, typename Graph::KnownVertex v2 )
  {
    vis.examine_edge( v1, e, v2 );
    typename LevelMap::value_type l;
    if( (l = get( lmap, v2, g )) == std::numeric_limits< typename LevelMap::value_type >::max() )
    {
      put( lmap, v2, g, current_level + 1 );
      insert( *grayset, v2 );
      vis.discover_vertex( v2 );
      vis.target_new_vertex( v1, e, v2 );
    }
    else if( l > current_level )
    {
      vis.target_next_level( v1, e, v2 );
    }
    else if( l == current_level )
    {
      vis.target_same_level( v1, e, v2 );
    }
    else
    {
      vis.target_prev_level( v1, e, v2 );
    }
  }

  template< class Edge >
  first_property_type first_computation_on_v1( typename Graph::KnownVertex v1, Edge e, typename Graph::KnownVertex v2 )
  {
    first_property_type p;
    vis.examine_edge( v1, e, v2, p );
    return p;
  }
  second_property_type first_computation_on_v2( VertexID_t v1, EdgeID_t e, VertexID_t v2id, first_property_type & first_prop )
  {
    typename Graph::KnownVertex v2 = g.get_known_vertex(v2id);
    second_property_user_type second_prop;
    typename LevelMap::value_type l;
    if( (l = get( lmap, v2, g )) == std::numeric_limits< typename LevelMap::value_type >::max() )
    {
      put( lmap, v2, g, current_level + 1 );
      insert( *grayset, v2 );
      vis.discover_vertex( v2 );
      vis.target_new_vertex( v1, e, v2id, first_prop, second_prop );
    }
    else if( l > current_level )
    {
      vis.target_next_level( v1, e, v2id, first_prop, second_prop );
    }
    else if( l == current_level )
    {
      vis.target_same_level( v1, e, v2id, first_prop, second_prop );
    }
    else vis.target_prev_level( v1, e, v2id, first_prop, second_prop );
    return second_property_type( l, second_prop );
  }
  void second_computation_on_v1( VertexID_t v1, EdgeID_t e, VertexID_t v2, second_property_type & second_prop )
  {
    typename LevelMap::value_type l = get_property_value( second_prop, bfs_level_tag() );
    if( l == std::numeric_limits< typename LevelMap::value_type >::max() )
    {
      vis.back_from_target_new_vertex( v1, e, v2, (second_property_user_type &) second_prop );
    }
    else if( l > current_level )
    {
      vis.back_from_target_next_level( v1, e, v2, (second_property_user_type &) second_prop );
    }
    else if( l == current_level )
    {
      vis.back_from_target_same_level( v1, e, v2, (second_property_user_type &) second_prop );
    }
    else
    {
      vis.back_from_target_prev_level( v1, e, v2, (second_property_user_type &) second_prop );
    }
  }
};

template< class Graph, class PMap >
struct set_each_vertex_property
{
  Graph &g;
  PMap pmap;
  typename PMap::value_type val;

  set_each_vertex_property(  Graph & _g, PMap map, typename PMap::value_type _val ) :
      g(_g), pmap(map), val(_val) {}
  void operator() ( typename Graph::KnownVertex v )
  {
    put( pmap, g.get_property_reference(v), val );
  }
};

template< class Visitor >
struct bfs_finish_vertex_type
{
  Visitor & vis;

  bfs_finish_vertex_type( Visitor & _v ) : vis(_v) {}

  template< class TYPE >
  void operator() ( TYPE v ) 
  {
    vis.finish_vertex( v );
  }
};

template< class Visitor >
struct bfs_examine_vertex_type
{
  Visitor & vis;

  bfs_examine_vertex_type( Visitor & _v ) : vis(_v) {}

  template< class TYPE >
  void operator() ( TYPE v ) 
  {
    vis.examine_vertex( v );
  }
};

template< class Graph, class Set, class LevelMap, class EdgeMap, class Visitors >
void breadth_first_search( Graph & g, Set &grayset, Set &next_grayset, bool * user_found,
                          LevelMap lmap, EdgeMap emap, Visitors vis )
{
  *user_found = false;
  pair< typename Graph::VertexIterator, typename Graph::VertexIterator > range =
      g.get_local_vertices();
  typename Graph::VertexIterator v_iter = range.first;
  for(; v_iter != range.second ; v_iter++ )
  {
    put( lmap, *v_iter, g, std::numeric_limits< typename LevelMap::value_type >::max() );
  }
  bfs_finish_vertex_type< Visitors >
      bfs_finish_vertex( vis );
  bfs_examine_vertex_type< Visitors >
      bfs_examine_vertex( vis );
  typename Set::iterator s_iter = grayset.begin();
  for(; s_iter != grayset.end() ; s_iter++ )
  {
    put( lmap, *s_iter, g, 0 );
    vis.discover_vertex( *s_iter );
  }
  next_grayset.clear();

  bfs_inner_part< Graph, LevelMap, Set, Visitors > ip( g, lmap, vis );

  vis.search_finished( user_found );
  bool found = PG_ReduceOr( *user_found );
  while( !found )
  {
    std::for_each( grayset.begin(), grayset.end(), bfs_examine_vertex );

    ip.grayset = &next_grayset;

    for_each_adjacent_vertex( g, grayset.begin(), grayset.end(), emap, ip );
    ip.current_level++;

    std::for_each( grayset.begin(), grayset.end(), bfs_finish_vertex );

    grayset.clear();
    grayset.swap( next_grayset );

    found = PG_ReduceAnd( grayset.empty() );
    
    vis.search_finished( user_found );
    found |= PG_ReduceOr( *user_found );
  }
}

struct true_tag {};
struct false_tag {};

template< class A, class B >
struct IsSame
{
  typedef false_tag type;
};

template< class A >
struct IsSame< A, A >
{
  typedef true_tag type;
};

template< class Visitor, class TYPE1, class TYPE2 >
void visitor_dispatch( false_tag, Visitor & vis, VertexID_t v1, EdgeID_t e, VertexID_t v2, TYPE1 & type1, TYPE2 & type2 )
{
}

template< class Visitor, class TYPE1, class TYPE2 >
void visitor_dispatch( true_tag, Visitor & vis, VertexID_t v1, EdgeID_t e, VertexID_t v2, TYPE1 & type1, TYPE2 & type2 )
{
  vis( v1, e, v2, type1, type2 );
}

template< class Visitor, class V, class E, class TYPE1 >
void visitor_dispatch( false_tag, Visitor & vis, V v1, E & e, V v2, TYPE1 & type1 )
{
}

template< class Visitor, class V, class E, class TYPE1 >
void visitor_dispatch( true_tag, Visitor & vis, V v1, E & e, V v2, TYPE1 & type1 )
{
  vis( v1, e, v2, type1 );
}

template< class Visitor, class TYPE1 >
void visitor_dispatch( false_tag, Visitor & vis, VertexID_t v1, EdgeID_t e, VertexID_t v2, TYPE1 & type1 )
{
}

template< class Visitor, class TYPE1 >
void visitor_dispatch( true_tag, Visitor & vis, VertexID_t v1, EdgeID_t e, VertexID_t v2, TYPE1 & type1 )
{
  vis( v1, e, v2, type1 );
}

template< class Visitor, class V, class E >
void visitor_dispatch( false_tag, Visitor & vis, V v1, E e, V v2 )
{
}

template< class Visitor, class V, class E >
void visitor_dispatch( true_tag, Visitor & vis, V v1, E e, V v2 )
{
  vis( v1, e, v2 );
}

template< class Visitor, class TYPE1 >
void visitor_dispatch( false_tag, Visitor & vis, TYPE1 type1 )
{
}

template< class Visitor, class TYPE1 >
void visitor_dispatch( true_tag, Visitor & vis, TYPE1 type1 )
{
  vis( type1 );
}

template< class VISITOR, class TAG, class V, class E, class TYPE1 >
void invoke_visitor( VISITOR & vis, TAG tag, V v1, E & e, V v2, TYPE1 & type1 )
{
  typedef typename VISITOR::Category Cat;
  typedef typename IsSame< Cat, TAG >::type DispatchFlag;
  visitor_dispatch( DispatchFlag(), vis, v1, e, v2, type1 );
}

template< class VISITOR, class TAG, class TYPE1 >
void invoke_visitor( VISITOR & vis, TAG tag, VertexID_t v1, EdgeID_t e, VertexID_t v2, TYPE1 & type1 )
{
  typedef typename VISITOR::Category Cat;
  typedef typename IsSame< Cat, TAG >::type DispatchFlag;
  visitor_dispatch( DispatchFlag(), vis, v1, e, v2, type1 );
}

template< class REST1, class REST2, class TAG, class V, class E, class TYPE1 >
void invoke_visitor( pair< REST1, REST2 > & vlist, TAG tag, V v1, E & e, V v2, TYPE1 & type1 )
{
  invoke_visitor( vlist.first, tag, v1, e, v2, type1 );
  invoke_visitor( vlist.second, tag, v1, e, v2, type1 );
}

template< class REST1, class REST2, class TAG, class TYPE1 >
void invoke_visitor( pair< REST1, REST2 > & vlist, TAG tag, VertexID_t v1, EdgeID_t e, VertexID_t v2, TYPE1 & type1 )
{
  invoke_visitor( vlist.first, tag, v1, e, v2, type1 );
  invoke_visitor( vlist.second, tag, v1, e, v2, type1 );
}

template< class VISITOR, class TAG, class TYPE1, class TYPE2 >
void invoke_visitor( VISITOR & vis, TAG tag, VertexID_t v1, EdgeID_t e, VertexID_t v2, TYPE1 & type1, TYPE2 & type2 )
{
  typedef typename VISITOR::Category Cat;
  typedef typename IsSame< Cat, TAG >::type DispatchFlag;
  visitor_dispatch( DispatchFlag(), vis, v1, e, v2, type1, type2 );
}

template< class REST1, class REST2, class TAG, class TYPE1, class TYPE2 >
void invoke_visitor( pair< REST1, REST2 > & vlist, TAG tag, VertexID_t v1, EdgeID_t e, VertexID_t v2, TYPE1 & type1, TYPE2 & type2 )
{
  invoke_visitor( vlist.first, tag, v1, e, v2, type1, type2 );
  invoke_visitor( vlist.second, tag, v1, e, v2, type1, type2 );
}

template< class VISITOR, class TAG, class V, class E >
void invoke_visitor( VISITOR & vis, TAG tag, V v1, E e, V v2 )
{
  typedef typename VISITOR::Category Cat;
  typedef typename IsSame< Cat, TAG >::type DispatchFlag;
  visitor_dispatch( DispatchFlag(), vis, v1, e, v2 );
}

template< class REST1, class REST2, class TAG, class V, class E >
void invoke_visitor( pair< REST1, REST2 > & vlist, TAG tag, V v1, E e, V v2 )
{
  invoke_visitor( vlist.first, tag, v1, e, v2 );
  invoke_visitor( vlist.second, tag, v1, e, v2 );
}

template< class VISITOR, class TAG, class TYPE1 >
void invoke_visitor( VISITOR & vis, TAG tag, TYPE1 type1 )
{
  typedef typename VISITOR::Category Cat;
  typedef typename IsSame< Cat, TAG >::type DispatchFlag;
  visitor_dispatch( DispatchFlag(), vis, type1 );
}

template< class REST1, class REST2, class TAG, class TYPE1 >
void invoke_visitor( pair< REST1, REST2 > & vlist, TAG tag, TYPE1 type1 )
{
  invoke_visitor( vlist.first, tag, type1 );
  invoke_visitor( vlist.second, tag, type1 );
}

struct no_visitor {};

struct on_discover_vertex {};
struct on_examine_vertex {};
struct on_finish_vertex {};

struct on_examine_edge {};
struct on_target_new_vertex {};
struct on_target_next_level {};
struct on_target_same_level {};
struct on_target_prev_level {};
struct on_back_from_target_new_vertex {};
struct on_back_from_target_next_level {};
struct on_back_from_target_same_level {};
struct on_back_from_target_prev_level {};

struct on_search_finished {};

template< class DistributionTypes, class Visitors >
class bfs_visitor
{
  Visitors vis;
public:
  bfs_visitor( Visitors & v ) : vis(v) {}

  typedef typename DistributionTypes::first_type first_property_type;
  typedef typename DistributionTypes::second_type second_property_type;

  template< class V >
  void discover_vertex( V v )
  {
    invoke_visitor( vis, on_discover_vertex(), v );
  }
  template< class V >
  void examine_vertex( V v )
  {
    invoke_visitor( vis, on_examine_vertex(), v );
  }
  template< class V >
  void finish_vertex( V v )
  {
    invoke_visitor( vis, on_finish_vertex(), v );
  }
  template< class V, class E >
  void examine_edge( V v1, E e, V v2 )
  {
    invoke_visitor( vis, on_examine_edge(), v1, e, v2 );
  }
  template< class V, class E >
  void examine_edge( V v1, E e, V v2,
                     first_property_type & p )
  {
    invoke_visitor( vis, on_examine_edge(), v1, e, v2, p );
  }
  template< class V, class E >
  void target_new_vertex( V v1, E e, V v2 )
  {
    invoke_visitor( vis, on_target_new_vertex(), v1, e, v2 );
  }
  void target_new_vertex( VertexID_t v1, EdgeID_t e, VertexID_t v2,
                     first_property_type & p1, second_property_type & p2 )
  {
    invoke_visitor( vis, on_target_new_vertex(), v1, e, v2, p1, p2 );
  }
  template< class V, class E >
  void target_next_level( V v1, E e, V v2 )
  {
    invoke_visitor( vis, on_target_next_level(), v1, e, v2 );
  }
  void target_next_level( VertexID_t v1, EdgeID_t e, VertexID_t v2,
                     first_property_type & p1, second_property_type & p2 )
  {
    invoke_visitor( vis, on_target_next_level(), v1, e, v2, p1, p2 );
  }
  template< class V, class E >
  void target_same_level( V v1, E e, V v2 )
  {
    invoke_visitor( vis, on_target_same_level(), v1, e, v2 );
  }
  void target_same_level( VertexID_t v1, EdgeID_t e, VertexID_t v2,
                     first_property_type & p1, second_property_type & p2 )
  {
    invoke_visitor( vis, on_target_same_level(), v1, e, v2, p1, p2 );
  }
  template< class V, class E >
  void target_prev_level( V v1, E e, V v2 )
  {
    invoke_visitor( vis, on_target_prev_level(), v1, e, v2 );
  }
  void target_prev_level( VertexID_t v1, EdgeID_t e, VertexID_t v2,
                     first_property_type & p1, second_property_type & p2 )
  {
    invoke_visitor( vis, on_target_prev_level(), v1, e, v2, p1, p2 );
  }
  void back_from_target_new_vertex( VertexID_t v1, EdgeID_t e, VertexID_t v2,
                               second_property_type & p2 )
  {
    invoke_visitor( vis, on_back_from_target_new_vertex(), v1, e, v2, p2 );
  }
  void back_from_target_next_level( VertexID_t v1, EdgeID_t e, VertexID_t v2,
                               second_property_type & p2 )
  {
    invoke_visitor( vis, on_back_from_target_next_level(), v1, e, v2, p2 );
  }
  void back_from_target_same_level( VertexID_t v1, EdgeID_t e, VertexID_t v2,
                              second_property_type & p2 )
  {
    invoke_visitor( vis, on_back_from_target_same_level(), v1, e, v2, p2 );
  }
  void back_from_target_prev_level( VertexID_t v1, EdgeID_t e, VertexID_t v2,
                               second_property_type & p2 )
  {
    invoke_visitor( vis, on_back_from_target_prev_level(), v1, e, v2, p2 );
  }
  void search_finished( bool * flag )
  {
    invoke_visitor( vis, on_search_finished(), flag );
  }
};

template< class First, class Second >
struct bfs_distribution_types
{
  typedef First first_type;
  typedef Second second_type;
};

template< class DistTypes, class Visitors >
inline bfs_visitor< DistTypes, Visitors >
make_bfs_visitor( DistTypes, Visitors vlist )
{
  return bfs_visitor< DistTypes, Visitors >( vlist );
}

template< class Category >
struct bfs_next_category_traits {};

template< >
struct bfs_next_category_traits< on_target_new_vertex >
{
    typedef on_back_from_target_new_vertex Category;
};

template< >
struct bfs_next_category_traits< on_target_next_level >
{
    typedef on_back_from_target_next_level Category;
};

template< >
struct bfs_next_category_traits< on_target_same_level >
{
    typedef on_back_from_target_same_level Category;
};

template< >
struct bfs_next_category_traits< on_target_prev_level >
{
    typedef on_back_from_target_prev_level Category;
};

template< class Set >
struct bfs_is_vertex_inside_targetset {
  typedef on_discover_vertex Category;

  Set & t_set;
  bool *t_found;
  bfs_is_vertex_inside_targetset( Set & s, bool * f ) : t_set(s), t_found(f) { }

  template< class Vertex >
  void operator() ( Vertex v )
  {
    if( t_set.find( v ) != t_set.end() ) *t_found = true;
  }
};

template< class Cat, class Graph, class EdgeMap, class EdgePropertyMap >
struct bfs_set_edgeproperty_both_sides
{
  typedef Cat Category;

  struct bfs_set_edgeproperty_other_side
  {
    typedef typename bfs_next_category_traits<Cat>::Category Category;

    Graph & g;
    const typename EdgePropertyMap::value_type value;

    bfs_set_edgeproperty_other_side( Graph &_g, typename EdgePropertyMap::value_type val ) : g(_g), value(val) {}

    void operator() ( VertexID_t v1, EdgeID_t e, VertexID_t v2,  no_property & ) const
    {
      put( EdgePropertyMap(), out_edge( g, v1, e, EdgeMap() ), value );
    }
  };

  bfs_set_edgeproperty_other_side f2;

  bfs_set_edgeproperty_both_sides( Graph &_g, typename EdgePropertyMap::value_type val ) : f2(_g, val) {}

  void operator() ( Vertex v1, typename EdgeMap::Edge e, Vertex v2 ) const
  {
    put( EdgePropertyMap(), e, f2.value );
  }
  void operator() ( VertexID_t v1, EdgeID_t e, VertexID_t v2, no_property &,  no_property & ) const
  {
    put( EdgePropertyMap(), in_edge( f2.g, v2, e, EdgeMap() ), f2.value );
  }

  pair< bfs_set_edgeproperty_both_sides< Cat, Graph, EdgeMap, EdgePropertyMap >, bfs_set_edgeproperty_other_side >
  get_functors()
  {
      return make_pair( *this, f2 );
  }
};

template< class EdgeMap >
struct bfs_distribute_use_ingoing_edges
{
  template< class Graph, class Vertex >
  void operator() ( Graph & g, Vertex v, size_t * incount )
  {
    for( size_t i = 0 ; i < size() ; i++ ) incount[i] = 0;

    typename EdgeMap::in_iterator eit, eend;
    boost::tie( eit, eend ) = in_edges( g, v, EdgeMap() );
    for(; eit != eend ; eit++ )
    {
      incount[ g.owning_processor( source(*eit,g) ) ]++;
    }
  }
};

template< class G, class S, class RankFunctor >
struct bfs_distribute
{
  typedef on_search_finished Category;

  G &g;
  S &m_set;
  bfs_distribute( G & _g, S & s ) : g(_g), m_set(s) {}

  void operator()( bool * )
  {
    if( size() == 1 ) return;

    RankFunctor f;
    typename S::iterator vit = m_set.begin(), vend = m_set.end();
    size_t * procrank = new size_t[size()], levelsize = 0;
    AllGatherBuffer buf;

    for(; vit != vend ; vit++, levelsize++ )
    {
      f( g, *vit, procrank );
      buf.put( get_id( *vit ) );
      buf.put( procrank, size() );
    }

    buf.communicate();
    levelsize = PG_ReduceAdd( levelsize );
    
    size_t bestsize = levelsize / size();
    int maxoverflow = levelsize % size();
    size_t * procsize = new size_t[size()];
    for( size_t i = 0 ; i < size() ; i++ ) procsize[i] = 0;
    std::map< typename G::KnownVertex, proc_t > movements;

    while( ! buf.is_empty() )
    {
      VertexID_t v;
      buf.get( &v );
      buf.get( procrank, size() );
      proc_t target_proc = 0; size_t best_procrank = 0;
      for( size_t i = 0 ; i < size() ; i++ )
      {
        if( procrank[i] >= best_procrank && ( procsize[i] < bestsize ||
                                (procsize[i] == bestsize && maxoverflow-- > 0 ) ) )
        {
          best_procrank = procrank[i];
          target_proc = i;
        }
      }
      procsize[ target_proc ]++;
      if( target_proc != rank() && g.is_vertex_local( v ) )
          movements.insert( make_pair( g.get_known_vertex(v), target_proc ) );
    }
    //if( _libbase.rank() == 0 )
    //for(size_t i =0;i<_libbase.size();i++)
    //std::cout<<"P"<<i<<" hat "<<procsize[i]<<" Knoten"<<std::endl;

    delete[] procrank; delete[] procsize;

    g.do_distribution( movements, g.use_standard_distribution() );
  }
};

template< class Graph, class Set, class LevelMap, class EdgeMap >
void bfs_do_distribution( Graph &g, Set &grayset1, Set &grayset2, LevelMap lmap, EdgeMap emap )
{
  bool found = false;
  bfs_distribute< Graph, Set, 
      bfs_distribute_use_ingoing_edges< EdgeMap > > vis( g, grayset1 );

  breadth_first_search( g, grayset1, grayset2, &found, lmap, emap,
                        make_bfs_visitor( bfs_distribution_types< no_property, no_property >(), vis ) );
}

}

#endif // _PG_ALGORITHM_HPP_

---