---

PG_edges.hpp

#ifndef _PG_EDGES_HPP_
#define _PG_EDGES_HPP_

#include <map>

#include "PG_property.hpp"

namespace ParGraph
{
struct directed_out_edges_type {};
struct directed_in_out_edges_type {};

struct has_out_edges {};
struct has_no_out_edges {};
struct has_in_edges {};
struct has_no_in_edges {};
struct is_double_sided_edge {};
struct is_not_double_sided_edge {};

template< class Property, class EdgeKind >
struct edgelist_kind_traits {};
template< class Edge >
struct edge_traits
{
  typedef typename Edge::value_type::second_type data_type;
  typedef typename data_type::property_type property_type;
};

template< class EdgeList >
struct edgelist_traits : edgelist_kind_traits< typename EdgeList::property_type, typename EdgeList::edge_kind >
{
};

template< class P >
class DirectedOutEdges;
template< class P >
class DirectedInOutEdges;

template< class Iter >
struct user_edge_type
{
  typedef typename Iter::value_type::second_type::property_type edge_property;
  known_vertex_type source, target;
  Iter edge;

  user_edge_type() {}
  user_edge_type( known_vertex_type v1, known_vertex_type v2, Iter e ) : source(v1), target(v2), edge(e) {}
};

template< class Edge >
inline EdgeID_t get_edge_id( Edge e )
{
  return e.edge->first;
}

template< class Edge, class Graph >
inline known_vertex_type source( Edge e, const Graph &g )
{
  return e.source;
}

template< class Edge, class Graph >
inline known_vertex_type target( Edge e, const Graph &g )
{
  return e.target;
}

template< class Edge >
inline known_vertex_type get_v2( Edge e )
{
  return e.edge->second.get_v2();
}

template< class Edge >
inline EdgeID_t get_v2_id( Edge e )
{
  return get_id( e.edge->second.get_v2());
}

template< class Edge >
inline bool is_out_edge( Edge &e )
{
  return e.target == e.edge->second.get_v2();
}

template< class Edge >
inline typename Edge::edge_property &
get_edge_property( Edge &e )
{
  return e.edge->second.get_property_reference();
}

template< class PropertyWrapper >
class EdgeBase
{
  known_vertex_type other_vertex;
  PropertyWrapper prop_wrapper;

public:
  typedef typename PropertyWrapper::property_type property_type;
  EdgeBase() {}
  EdgeBase( known_vertex_type id ) : other_vertex( id ) {}
  EdgeBase( known_vertex_type id, typename PropertyWrapper::constructor_argument_type p ) :
                                                 other_vertex( id ), prop_wrapper(p) {}

  known_vertex_type get_v2() const { return other_vertex; }
  void set_v2( known_vertex_type v ) { other_vertex = v; }

  typename PropertyWrapper::property_type & get_property_reference()
        { return prop_wrapper.get_reference(); }
  const typename PropertyWrapper::property_type & get_property_reference() const
        { return prop_wrapper.get_reference(); }
// only for DoubleSidedPropertyWrapper ! :
  void join( EdgeBase< PropertyWrapper > & e2 ) 
        { prop_wrapper.join( e2.prop_wrapper ); }
  void delete_property()
        { prop_wrapper.delete_property(); }

  friend class DirectedOutEdges< typename PropertyWrapper::property_type >;
  friend class DirectedInOutEdges< typename PropertyWrapper::property_type >;
};

// ------- Edge Property Wrapper ------------------------------------

template< class Property >
struct SimpleEdgePropertyWrapper
{
  Property prop;

  typedef Property property_type;
  typedef Property & constructor_argument_type;

  SimpleEdgePropertyWrapper() {}
  SimpleEdgePropertyWrapper( Property & p ) : prop(p) {}
  Property & get_reference() { return prop; }
  const Property & get_reference() const { return prop; }
};

template< class Property >
struct DoubleSidedEdgePropertyWrapper
{
  Property * prop;

  typedef Property property_type;
  typedef Property * constructor_argument_type;

  DoubleSidedEdgePropertyWrapper() {}
  DoubleSidedEdgePropertyWrapper( Property * p ) : prop(p) {}
    //~DoubleSidedEdgePropertyWrapper() { }
  Property & get_reference() { return *prop; }
  const Property & get_reference() const { return *prop; }
  void delete_property() { delete prop; }
  void new_property() { prop = new Property; }
  static Property * static_new_property() { return new Property; }
  static Property * static_new_property( const Property & p ) { return new Property(p); }
  void join( DoubleSidedEdgePropertyWrapper<Property> & w2 )
  {
    if( prop != w2.prop )
    {
        delete w2.prop;
        w2.prop = prop;
    }
  }
};

template<>
struct DoubleSidedEdgePropertyWrapper< no_property >
{
  no_property prop;
  typedef no_property property_type;
  typedef no_property constructor_argument_type;

  DoubleSidedEdgePropertyWrapper() {}
  DoubleSidedEdgePropertyWrapper( const no_property & ) {}
  no_property & get_reference() { return prop; }
  const no_property & get_reference() const { return prop; }
  void delete_property() { }
  void join( DoubleSidedEdgePropertyWrapper<no_property> & ) { }
  void new_property() {}
  static no_property static_new_property() { return no_property(); }
  static no_property static_new_property( const no_property & ) { return no_property(); }
};

// --------- Edge Iterator
template< class Iter >
class InEdgeIterator
{
  known_vertex_type target;
  Iter iter;
public:
  typedef user_edge_type< Iter > value_type;
  InEdgeIterator() : iter() {}
  InEdgeIterator( known_vertex_type v, Iter _iter ) : target(v), iter(_iter) {}
  InEdgeIterator( const InEdgeIterator<Iter> & other ) : target( other.target ), iter( other.iter ) {}
  void operator++(int)
  {
    iter++;
  }
  void operator++()
  {
    iter++;
  }
  bool operator==( const InEdgeIterator<Iter> & other ) const
  {
    return iter == other.iter;
  }
  bool operator!=( const InEdgeIterator<Iter> & other ) const
  {
    return iter != other.iter;
  }
  value_type operator*() const
  {
    return value_type( iter->second.get_v2(), target, iter);
  }
  InEdgeIterator & operator=( const InEdgeIterator<Iter> & other )
  {
    iter = other.iter;
    target = other.target;
    return *this;
  }
};

template< class Iter >
class OutEdgeIterator
{
  known_vertex_type source;
  Iter iter;
public:
  typedef user_edge_type< Iter > value_type;
  OutEdgeIterator() : iter() {}
  OutEdgeIterator( known_vertex_type v, Iter _iter ) : source(v), iter(_iter) {}
  OutEdgeIterator( const OutEdgeIterator<Iter> & other ) : source( other.source ), iter( other.iter ) {}
  void operator++(int)
  {
    iter++;
  }
  void operator++()
  {
    iter++;
  }
  bool operator==( const OutEdgeIterator<Iter> & other ) const
  {
    return iter == other.iter;
  }
  bool operator!=( const OutEdgeIterator<Iter> & other ) const
  {
    return iter != other.iter;
  }
  value_type operator*() const
  {
    return value_type( source, iter->second.get_v2(), iter);
  }
  OutEdgeIterator & operator=( const OutEdgeIterator<Iter> & other )
  {
    iter = other.iter;
    source = other.source;
    return *this;
  }
};

// --------- Directed Out Edges ----------------------

template< class Property >
class DirectedOutEdges
{
public:
  typedef EdgeBase<SimpleEdgePropertyWrapper<Property> > edge_type;
  typedef std::pair< EdgeID_t, edge_type > Edge_with_ID_t;
  typedef typename std::map< const EdgeID_t, edge_type > map_type;
  typedef OutEdgeIterator< typename map_type::iterator > out_iterator;
  typedef OutEdgeIterator< typename map_type::const_iterator > const_out_iterator;
  typedef user_edge_type< typename map_type::iterator > Edge;
  typedef typename map_type::iterator mapiterator;
  typedef typename map_type::const_iterator const_mapiterator;

public:
  std::map< const EdgeID_t, edge_type > out_edges;

public:
  DirectedOutEdges() : out_edges() {}

  void clear()
  {
    out_edges.clear();
  }

/*  void _pgdist_fill_buf( AllToAllBuffer & buf ) const
  {
    typename std::map< const EdgeID_t, edge_type >::const_iterator it = out_edges.begin();
    buf.put( out_edges.size() );
    for(; it != out_edges.end() ; it++ )
    {
      buf.put( &(*it).first, 1 );
      buf.put( &(*it).second.other_vertex, 1 );
      put_property_into_buffer( (*it).second.prop_wrapper.prop, buf );
    }
  }
  void _pgdist_read_buf( AllToAllBuffer & buf )
  {
    Edge_with_ID_t tmp;
    size_t size;
    buf.get( &size, 1 );
    for( unsigned int i = 0 ; i < size ; i++ )
    {
      buf.get( &tmp.first, 1 );
      buf.get( &tmp.second.other_vertex, 1 );
      get_property_from_buffer( tmp.second.prop_wrapper.prop, buf );
      out_edges.insert( tmp );
    }
    }*/
  template< class Tag, class Graph, class DistHelper >
  void _pgdist_fill_buf( Tag t, Graph & g, DistHelper & dh, AllToAllBuffer & buf ) const
  {
    typename std::map< const EdgeID_t, edge_type >::const_iterator it = out_edges.begin();
    buf.put( out_edges.size() );
    for(; it != out_edges.end() ; it++ )
    {
      buf.put( &(*it).first, 1 );
      buf.put( get_id((*it).second.other_vertex) );
      dh.write_proc( (*it).second.other_vertex, buf );
      g.dek_known_vertex_counter((*it).second.other_vertex);
      put_property_into_buffer( (*it).second.prop_wrapper.prop, buf );
    }
  }
  template< class Tag, class Graph, class DistHelper >
  void _pgdist_read_buf( Tag t, Graph & g, DistHelper & dh, AllToAllBuffer & buf )
  {
    Edge_with_ID_t tmp;
    size_t size;
    buf.get( &size, 1 );
    for( unsigned int i = 0 ; i < size ; i++ )
    {
      buf.get( &tmp.first, 1 );
      VertexID_t v;
      buf.get( &v, 1 );
      proc_t p = dh.read_proc( buf );
      if( p == _libbase.rank() ) p = _libbase.size();
      tmp.second.other_vertex = g.ink_known_vertex_counter_and_set_processor( v, p );
      get_property_from_buffer( tmp.second.prop_wrapper.prop, buf );
      out_edges.insert( tmp );
    }
  }

  void add( EdgeID_t id, VertexID_t v )
  {
    out_edges.insert( std::make_pair( id, edge_type( v ) ) );
  }

  void add( EdgeID_t id, VertexID_t v, Property & p )
  {
    out_edges.insert( std::make_pair( id, edge_type( v, p ) ) );
  }

    //template< class M, class G >
    //friend map_type & get_out_edges( M, VertexID_t, G& );
    //friend struct WorkOnEdgeList;
};

template< class Property >
class DirectedInOutEdges
{
public:
  typedef EdgeBase<DoubleSidedEdgePropertyWrapper<Property> > edge_type;
  typedef std::pair< EdgeID_t, edge_type > Edge_with_ID_t;
  typedef typename std::map< const EdgeID_t, edge_type > map_type;
  typedef InEdgeIterator< typename map_type::iterator > in_iterator;
  typedef OutEdgeIterator< typename map_type::iterator > out_iterator;
  typedef InEdgeIterator< typename map_type::const_iterator > const_in_iterator;
  typedef OutEdgeIterator< typename map_type::const_iterator > const_out_iterator;
  typedef typename map_type::const_iterator const_mapiterator;
  typedef typename map_type::iterator mapiterator;
  typedef user_edge_type< typename map_type::iterator > Edge;

public:
  std::map< const EdgeID_t, edge_type > in_edges;
  std::map< const EdgeID_t, edge_type > out_edges;

public:
  DirectedInOutEdges() : in_edges(), out_edges() {}

  edge_type & get_edge_reference( EdgeID_t id );
  const edge_type & get_edge_reference( EdgeID_t id ) const;
  edge_type & get_inedge_reference( EdgeID_t id );
  const edge_type & get_inedge_reference( EdgeID_t id ) const;
  template< class G, class M >
  void remove_edges( G&, M );
  template< class G >
  void complete_graph_remove_edges( G& );
  template< class V, class G, class M, class F >
  void remove_edges_if( V, G&, M, F& );
  template< class G, class M >
  void remove_in_edges( G&, M );
  template< class G, class M >
  void remove_in_edges( G&, M, AllToAllBuffer& );
  void remove_edge( EdgeID_t );
  template< class G, class M >
  void remove_in_edge( Edge, G&, M );
  template< class G, class M >
  void remove_out_edge( Edge, G&, M );
  template< class G, class M >
  void remove_in_edge( mapiterator, G&, M );
  template< class G, class M >
  void remove_out_edge( mapiterator, G&, M );
  template< class G, class M >
  void remove_in_edge( Edge, G&, M, AllToAllBuffer& );
  template< class G, class M >
  void remove_out_edge( Edge, G&, M, AllToAllBuffer& );

  void clear()
  {
    in_edges.clear();
    out_edges.clear();
  }

/*  void _pgdist_fill_buf( AllToAllBuffer & buf ) const
  {
    buf.put( in_edges.size() );
    typename std::map< const EdgeID_t, edge_type >::const_iterator it = in_edges.begin();
    for(; it != in_edges.end() ; it++ )
    {
      buf.put( &(*it).first, 1 );
      buf.put( &(*it).second.other_vertex, 1 );
      put_property_into_buffer( (*it).second.get_property_reference(), buf );
    }
    buf.put( out_edges.size() );
    it = out_edges.begin();
    for(; it != out_edges.end() ; it++ )
    {
      buf.put( &(*it).first, 1 );
      buf.put( &(*it).second.other_vertex, 1 );
      put_property_into_buffer( (*it).second.get_property_reference(), buf );
    }
  }
  void _pgdist_read_buf( AllToAllBuffer & buf )
  {
    Edge_with_ID_t tmp;
    size_t size;
    buf.get( &size, 1 );
    for( size_t i = 0 ; i < size ; i++ )
    {
      buf.get( &tmp.first, 1 );
      buf.get( &tmp.second.other_vertex, 1 );
      tmp.second.prop_wrapper.new_property();
      get_property_from_buffer( tmp.second.get_property_reference(), buf );
      in_edges.insert( tmp );
    }
    buf.get( &size, 1 );
    for( size_t i = 0 ; i < size ; i++ )
    {
      buf.get( &tmp.first, 1 );
      buf.get( &tmp.second.other_vertex, 1 );
      tmp.second.prop_wrapper.new_property();
      get_property_from_buffer( tmp.second.get_property_reference(), buf );
      out_edges.insert( tmp );
    }
    }*/
  template< class Tag, class Graph, class DistHelper >
  void _pgdist_fill_buf( Tag t, Graph & g, DistHelper & dh, AllToAllBuffer & buf )
  {
    buf.put( in_edges.size() );
    mapiterator it = in_edges.begin();
    for(; it != in_edges.end() ; it++ )
    {
      buf.put( &(it->first), 1 );
      buf.put( get_id(it->second.other_vertex) );
      dh.write_proc( it->second.other_vertex, buf );
      g.dek_known_vertex_counter(it->second.other_vertex);
      put_property_into_buffer( it->second.get_property_reference(), buf );
      if( ! g.is_vertex_local( it->second.other_vertex ) )
      {
        it->second.prop_wrapper.delete_property();
      }
    }
    buf.put( out_edges.size() );
    it = out_edges.begin();
    for(; it != out_edges.end() ; it++ )
    {
      buf.put( &(it->first), 1 );
      buf.put( get_id(it->second.other_vertex) );
      dh.write_proc( it->second.other_vertex, buf );
      g.dek_known_vertex_counter(it->second.other_vertex);
      put_property_into_buffer( it->second.get_property_reference(), buf );
      if( ! g.is_vertex_local( it->second.other_vertex ) )
      {
        it->second.prop_wrapper.delete_property();
      } 
    }
  }
  template< class Tag, class Graph, class DistHelper >
  void _pgdist_read_buf( Tag t, Graph & g, DistHelper & dh, AllToAllBuffer & buf )
  {
    Edge_with_ID_t tmp;
    size_t size;
    Property trash;
    buf.get( &size, 1 );
    for( size_t i = 0 ; i < size ; i++ )
    {
      buf.get( &tmp.first, 1 );
      VertexID_t v;
      buf.get( &v, 1 );
      proc_t p = dh.read_proc( buf );
      if( p == _libbase.rank() ) p = _libbase.size();
      tmp.second.other_vertex = g.ink_known_vertex_counter_and_set_processor( v, p );
      if( g.is_vertex_local( tmp.second.other_vertex ) )
      {
        get_property_from_buffer( trash, buf );
        tmp.second.prop_wrapper.prop = get_property_value( // join with other edge
            g.get_property_reference( tmp.second.other_vertex ), t ).get_edge_reference( tmp.first ).prop_wrapper.prop;
      }
      else
      {
        tmp.second.prop_wrapper.new_property();
        get_property_from_buffer( tmp.second.get_property_reference(), buf );
      }
      in_edges.insert( tmp );
    }
    buf.get( &size, 1 );
    for( size_t i = 0 ; i < size ; i++ )
    {
      buf.get( &tmp.first, 1 );
      VertexID_t v;
      buf.get( &v, 1 );
      proc_t p = dh.read_proc( buf );
      if( p == _libbase.rank() ) p = _libbase.size();
      tmp.second.other_vertex = g.ink_known_vertex_counter_and_set_processor( v, p );
      if( g.is_vertex_local( tmp.second.other_vertex ) )
      {
        get_property_from_buffer( trash, buf );
        tmp.second.prop_wrapper.prop = get_property_value( // join with other edge
            g.get_property_reference( tmp.second.other_vertex ), t ).get_edge_reference( tmp.first ).prop_wrapper.prop;
      }
      else
      {
        tmp.second.prop_wrapper.new_property();
        get_property_from_buffer( tmp.second.get_property_reference(), buf );
      }
      out_edges.insert( tmp );
    }
  }

  // template< class M, class P, class G >
  // friend void add_edge_with_id( M, EdgeID_t, VertexID_t, VertexID_t, P&, G&, AllToAllBuffer& );
  // template< class M, class G >
  // friend void add_delayed_edges( M, G&, AllToAllBuffer& );

  // template< class M, class G >
  // friend map_type & get_out_edges( M, VertexID_t, G& );
  // friend struct WorkOnEdgeList;
};

template< class P >
typename DirectedInOutEdges<P>::edge_type &
DirectedInOutEdges<P>::get_edge_reference( EdgeID_t id )
{
  if( out_edges.find( id ) != out_edges.end() )
      return (*out_edges.find( id )).second;
  return (*in_edges.find( id )).second;
}

template< class P >
const typename DirectedInOutEdges<P>::edge_type &
DirectedInOutEdges<P>::get_edge_reference( EdgeID_t id ) const
{
  if( out_edges.find( id ) != out_edges.end() )
      return (*out_edges.find( id )).second;
  return (*in_edges.find( id )).second;
}

template< class P >
typename DirectedInOutEdges<P>::edge_type &
DirectedInOutEdges<P>::get_inedge_reference( EdgeID_t id )
{
  return (*in_edges.find( id )).second;
}

template< class P >
const typename DirectedInOutEdges<P>::edge_type &
DirectedInOutEdges<P>::get_inedge_reference( EdgeID_t id ) const
{
  return (*in_edges.find( id )).second;
}

template< class P>
template< class Graph, class EdgeMap >
void
DirectedInOutEdges<P>::remove_edges( Graph &g, EdgeMap m )
{
  mapiterator eit, eitnext;
  eit = out_edges.begin();
  for(; eit != out_edges.end() ; eit = eitnext )
  {
    eitnext = eit; eitnext++;
    remove_out_edge( eit, g, m );
  }
  mapiterator eit2, eitnext2;
  eit2 = in_edges.begin();
  for(; eit2 != in_edges.end() ; eit2 = eitnext2 )
  {
    eitnext2 = eit2; eitnext2++;
    remove_in_edge( eit2, g, m );
  }
}

template< class P>
template< class Graph >
void
DirectedInOutEdges<P>::complete_graph_remove_edges( Graph &g )
{
  mapiterator eit, eitnext;
  eit = out_edges.begin();
  for(; eit != out_edges.end() ; eit = eitnext )
  {
    eitnext = eit; eitnext++;
    (*eit).second.delete_property();
    out_edges.erase( eit );
  }
  mapiterator eit2, eitnext2;
  eit2 = in_edges.begin();
  for(; eit2 != in_edges.end() ; eit2 = eitnext2 )
  {
    eitnext2 = eit2; eitnext2++;
    if( ! g.is_vertex_local( (*eit2).second.get_v2() ) )
        (*eit2).second.delete_property();
    in_edges.erase( eit2 );
  }
}

template< class P>
template< class Vertex, class Graph, class EdgeMap, class Function >
void
DirectedInOutEdges<P>::remove_edges_if( Vertex v, Graph &g, EdgeMap m, Function & f )
{
  mapiterator eit, eitnext;
  eit = out_edges.begin();
  for(; eit != out_edges.end() ; eit = eitnext )
  {
    eitnext = eit; eitnext++;
    if( f( Edge( v, eit->second.get_v2(), eit ) ) )
    {
      remove_out_edge( eit, g, m );
    }
  }
  mapiterator eit2, eitnext2;
  eit2 = in_edges.begin();
  for(; eit2 != in_edges.end() ; eit2 = eitnext2 )
  {
    eitnext2 = eit2; eitnext2++;
    if( f( Edge( eit2->second.get_v2(), v, eit2 ) ) )
    {
      remove_in_edge( eit2, g, m );
    }
  }
}

template< class P>
void
DirectedInOutEdges<P>::remove_edge( EdgeID_t e )
{
  bool prop_deleted = false;
  mapiterator outit = out_edges.find(e);
  if( outit != out_edges.end() )
  {
    (*outit).second.prop_wrapper.delete_property();
    out_edges.erase( outit );
    prop_deleted = true;
  }
  mapiterator init = in_edges.find(e);
  if( init != in_edges.end() )
  {
    if( prop_deleted == false ) (*init).second.prop_wrapper.delete_property();
    in_edges.erase( init );
  }
}

template< class P>
template< class Graph, class EdgeMap >
void
DirectedInOutEdges<P>::remove_in_edges( Graph &g, EdgeMap m )
{
  Edge eit, eitnext;
  eit = get_in_edges( m, *this ).begin();
  for(; eit != in_edges.end() ; eit = eitnext )
  {
    eitnext = eit; eitnext++;
    remove_in_edge( eit, g, m );
  }
}

template< class P>
template< class Graph, class EdgeMap >
void
DirectedInOutEdges<P>::remove_in_edges( Graph &g, EdgeMap m, AllToAllBuffer &buf )
{
  Edge eit, eitnext;
  eit = get_in_edges( m, *this ).begin();
  for(; eit != get_in_edges( m, *this ).end() ; eit = eitnext )
  {
    eitnext = eit; eitnext++;
    remove_in_edge( eit, g, m, buf );
  }
}

template< class P>
template< class Graph, class EdgeMap >
void
DirectedInOutEdges<P>::remove_in_edge( Edge e, Graph &g, EdgeMap m )
{
  e.edge->second.delete_property();
  if( g.is_vertex_local( e.source ) )
  {
    get_out_edges( m, e.source, g ).erase( e.edge->first );
  }
  in_edges.erase( e.edge );
}

template< class P>
template< class Graph, class EdgeMap >
void
DirectedInOutEdges<P>::remove_out_edge( Edge e, Graph &g, EdgeMap m )
{
  e.edge->second.delete_property();
  if( g.is_vertex_local( e.target ) )
  {
    get_in_edges( m, e.target, g ).erase( e.edge->first );
  }
  out_edges.erase( e.edge );
}

template< class P>
template< class Graph, class EdgeMap >
void
DirectedInOutEdges<P>::remove_in_edge( mapiterator e, Graph &g, EdgeMap m )
{
  e->second.delete_property();
  if( g.is_vertex_local( e->second.get_v2() ) )
  {
    get_out_edges( m, e->second.get_v2(), g ).erase( e->first );
  }
  in_edges.erase( e );
}

template< class P>
template< class Graph, class EdgeMap >
void
DirectedInOutEdges<P>::remove_out_edge( mapiterator e, Graph &g, EdgeMap m )
{
  e->second.delete_property();
  if( g.is_vertex_local( e->second.get_v2() ) )
  {
    get_in_edges( m, e->second.get_v2(), g ).erase( e->first );
  }
  out_edges.erase( e );
}

template< class P>
template< class Graph, class EdgeMap >
void
DirectedInOutEdges<P>::remove_in_edge( Edge e, Graph &g, EdgeMap m, AllToAllBuffer & buf )
{
  e.edge->second.prop_wrapper.delete_property();

  if( g.is_vertex_local( e.source ) )
  {
    get_out_edges( m, e.source, g ).erase( e.edge->first );
  }
  else
  {
    buf.put( e.edge->first );
    buf.put( e.source );
  }
  in_edges.erase( e.edge );
}

template< class P>
template< class Graph, class EdgeMap >
void
DirectedInOutEdges<P>::remove_out_edge( Edge e, Graph &g, EdgeMap m, AllToAllBuffer & buf )
{
  (*e).second.prop_wrapper.delete_property();
  if( g.is_vertex_local( e.target ) )
  {
    get_in_edges( m, e.target, g ).erase( e.edge->first );
  }
  else
  {
    buf.put( e.edge->first );
    buf.put( e.target );
  }
  out_edges.erase( e.edge );
}

// --------------- Edge List -----------------------------

template< class Property >
struct edgelist_kind_traits<Property,directed_out_edges_type>
{
  typedef has_out_edges has_out_edges_tag;
  typedef has_no_in_edges has_in_edges_tag;
  typedef is_not_double_sided_edge is_double_sided_edge_tag;

  typedef DirectedOutEdges<Property> base;

  typedef typename base::out_iterator out_iterator;
  typedef typename base::const_iterator const_iterator;
  typedef typename base::out_iterator out_iterator;
  typedef typename base::const_out_iterator const_out_iterator;
  typedef typename base::Edge Edge;
  typedef typename base::const_Edge const_Edge;
};

template< class Property >
struct edgelist_kind_traits<Property,directed_in_out_edges_type>
{
  typedef has_out_edges has_out_edges_tag;
  typedef has_in_edges has_in_edges_tag;
  typedef is_double_sided_edge is_double_sided_edge_tag;

  typedef DirectedInOutEdges<Property> base;

  typedef typename base::in_iterator in_iterator;
  typedef typename base::out_iterator out_iterator;
  typedef typename base::const_in_iterator const_in_iterator;
  typedef typename base::const_out_iterator const_out_iterator;
  typedef typename base::Edge Edge;
};

template< class Property, class EdgeKind >
class EdgeList : public edgelist_kind_traits<Property,EdgeKind>::base
{
  typedef EdgeKind edge_kind;
  typedef Property property_type;
};

// ----------- Edge Distribution Traits --------------------

template< class P, class EdgeKind >
struct property_distribution_traits< EdgeList<P,EdgeKind> >
{
  typedef complex_distribution distribution_type;
};

// ---------- Functions -----------------------------------

template< class Map, class Graph >
void
copy_properties_out2in( Map m, Graph & g )
{
  AllToAllBuffer buf;

  typename Graph::VertexIterator v_it, v_end;
  boost::tie( v_it, v_end ) = g.get_local_vertices();

  for(; v_it != v_end ; v_it++ )
  {
    typename Map::value_type::out_iterator e_it, e_end;
    boost::tie( e_it, e_end ) = out_edges( g, *v_it, m );
    for(; e_it != e_end ; e_it++ )
    {
      if( !g.is_vertex_local( (*e_it).second.get_v2() ) )
      {
        buf.set_proc( g.owning_processor( (*e_it).second.get_v2() ) );
        buf.put( (*e_it).second.get_v2() );
        buf.put( (*e_it).first );
        put_property_into_buffer( (*e_it).second.get_property_reference(), buf );
      }
    }
  }
  buf.communicate();

  while( ! buf.is_empty() )
  {
    EdgeID_t eid;
    VertexID_t vid;
    buf.get( &vid, 1 );
    buf.get( &eid, 1 );
    get_property_from_buffer( (*get_in_edges( m, vid, g ).find( eid )).second.get_property_reference(), buf );
  }
}

template< class EdgeMap, class EdgePropertyMap, class Graph >
void
copy_property_in2out( EdgeMap m1, EdgePropertyMap m2, Graph & g )
{
  AllToAllBuffer buf;
  typename Graph::VertexIterator v_it, v_end;
  boost::tie( v_it, v_end ) = g.get_local_vertices();

  for(; v_it != v_end ; v_it++ )
  {
    typename EdgeMap::in_iterator e_it, e_end;
    boost::tie( e_it, e_end ) = in_edges( g, *v_it, m1 );
    for(; e_it != e_end ; e_it++ )
    {
      if( !g.is_vertex_local( get_v2(*e_it) ) )
      {
        buf.set_proc( g.owning_processor( get_v2(*e_it) ) );
        buf.put( get_v2_id(*e_it) );
        buf.put( get_edge_id(*e_it) );
        buf.put( get( m2, *e_it ) );
      }
    }
  }
  buf.communicate();

  while( ! buf.is_empty() )
  {
    EdgeID_t eid;
    VertexID_t vid;
    buf.get( &vid, 1 );
    buf.get( &eid, 1 );
    typename EdgePropertyMap::value_type tmp;
    buf.get( &tmp );
    put( m2, out_edge( g, vid, eid, m1 ), tmp );
  }
}

template< class Map, class Graph >
void
add_delayed_edges( Map m, Graph & g, AllToAllBuffer & delayed_buf )
{
  AllToAllBuffer asking_buf;
  typedef typename Map::edge_property_type Property;

  delayed_buf.communicate();

  while( ! delayed_buf.is_empty() )
  {
    EdgeID_t eid;
    VertexID_t v1id, v2id;
    typename DoubleSidedEdgePropertyWrapper< Property >::constructor_argument_type prop
        = DoubleSidedEdgePropertyWrapper< Property >::static_new_property();
    proc_t source_proc = delayed_buf.get( &eid, 1 );
    delayed_buf.get( &v1id, 1 );
    delayed_buf.get( &v2id, 1 );
    get_property_from_buffer( *prop, delayed_buf );
    if( g.is_vertex_local( v1id ) )
    {
      known_vertex_type v2;
      if( g.is_vertex_known( v2id ) )
           v2 = g.ink_known_vertex_counter( v2id );
      else
      {
          ask_for_position( source_proc, v2id, asking_buf );
          v2 = g.make_vertex_known( v2id, size() );
      }
      get_out_edges( m, v1id, g ).insert( 
          make_pair( eid, typename Map::value_type::edge_type(v2,prop) ));
    }
    if( g.is_vertex_local( v2id ) )
    {
      known_vertex_type v1;
      if( g.is_vertex_known( v1id ) )
           v1 = g.ink_known_vertex_counter( v1id );
      else
      {
          ask_for_position( source_proc, v1id, asking_buf );
          v1 = g.make_vertex_known( v1id, size() );
      }
      get_in_edges( m, v2id, g ).insert(
          make_pair( eid, typename Map::value_type::edge_type(v1,prop) ));
    }
  }

  do_asking_for_position( g, asking_buf );
}

template< class Map, class V1, class V2, class Graph >
EdgeID_t
add_edge( Map m, V1 v1, V2 v2, 
          Graph & g, AllToAllBuffer & delayed_buf )
{
  EdgeID_t new_ID = g.get_free_edge_id();
  add_edge_with_id_worker( m, new_ID, g.get_known_vertex(v1), g.get_known_vertex(v2), Map::edge_property_type(), g, delayed_buf );
  return new_ID;
}

template< class Map, class V1, class V2, class Property, class Graph >
EdgeID_t
add_edge( Map m, V1 v1, V2 v2, Property & prop, 
          Graph & g, AllToAllBuffer & delayed_buf )
{
  EdgeID_t new_ID = g.get_free_edge_id();
  add_edge_with_id_worker( m, new_ID, g.get_known_vertex(v1), g.get_known_vertex(v2), prop, g, delayed_buf );
  return new_ID;
}

template< class Map, class V1, class V2, class Property, class Graph >
inline void
add_edge_with_id( Map m, EdgeID_t new_ID, V1 v1, V2 v2, Property & prop, 
          Graph & g, AllToAllBuffer & delayed_buf )
{
  add_edge_with_id_worker( m, new_ID, g.get_known_vertex(v1), g.get_known_vertex(v2), prop, g, delayed_buf );
}

template< class Map, class Property, class Graph >
void
add_edge_with_id_worker( Map m, EdgeID_t new_ID, typename Graph::KnownVertex v1, 
                  typename Graph::KnownVertex v2, Property & prop, 
                  Graph & g, AllToAllBuffer & delayed_buf )
{
  bool v1_is_local;
  proc_t v1_lays_on;
  typename DoubleSidedEdgePropertyWrapper< Property >::constructor_argument_type prop_pointer;

  if( v1_is_local = g.is_vertex_local( v1 ) )
  {
    prop_pointer =
        DoubleSidedEdgePropertyWrapper< Property >::static_new_property(prop);
    get_out_edges( m, v1, g ).insert(
        make_pair( new_ID, typename Map::value_type::edge_type(v2,prop_pointer) ));

    g.ink_known_vertex_counter( v2 );
  }
  else
  {
    delayed_buf.set_proc( v1_lays_on = g.owning_processor( v1 ) );
    delayed_buf.put( new_ID );
    delayed_buf.put( get_id(v1) );
    delayed_buf.put( get_id(v2) );
    put_property_into_buffer( prop, delayed_buf );
  }

  if( g.is_vertex_local( v2 ) )
  {
    if( !v1_is_local )
    {
      prop_pointer =
         DoubleSidedEdgePropertyWrapper< Property >::static_new_property(prop);
    }
    get_in_edges( m, v2, g ).insert(
        make_pair( new_ID, typename Map::value_type::edge_type(v1,prop_pointer) ));

    g.ink_known_vertex_counter( v1 );
  }
  else if( v1_is_local || v1_lays_on != g.owning_processor( v2 ) )
  {
    // an edge is _not_ sent twice to the same proc
    delayed_buf.set_proc( g.owning_processor( v2 ) );
    delayed_buf.put( new_ID );
    delayed_buf.put( get_id(v1) );
    delayed_buf.put( get_id(v2) );
    put_property_into_buffer( prop, delayed_buf );
  }
}

template< class Map, class Graph >
EdgeID_t
add_edge( Map m, VertexID_t v1, VertexID_t v2id, Graph & g )
{
    EdgeID_t new_ID = g.get_free_edge_id();

    known_vertex_type v2 = g.ink_known_vertex_counter( v2id );
    get( m, v1, g ).add( new_ID, v2 );

    return new_ID;
}

template< class Map, class V1, class V2, class Property, class Graph >
EdgeID_t
add_edge( Map m, V1 v1, V2 v2, Property & prop, Graph & g )
{
  EdgeID_t new_ID = g.get_free_edge_id();
  add_edge_with_id( m, new_ID, v1, v2, prop, g );
  return new_ID;
}

template< class Map, class V1, class V2, class Property, class Graph >
inline void
add_edge_with_id( Map m, EdgeID_t new_ID, V1 v1, V2 v2, Property & prop, 
          Graph & g )
{
  add_edge_with_id_worker( m, new_ID, g.get_known_vertex(v1), g.get_known_vertex(v2), prop, g );
}

template< class Map, class Property, class Graph >
void
add_edge_with_id_worker( Map m, EdgeID_t new_ID, typename Graph::KnownVertex v1, 
                         typename Graph::KnownVertex v2, Property & prop, Graph & g )
{
  get( m, v1, g ).add( new_ID, v2, prop );
  g.ink_known_vertex_counter( v2 );
}

template< class Graph, class Vertex, class EdgeMap >
inline pair<typename EdgeMap::in_iterator,
    typename EdgeMap::in_iterator>
in_edges( Graph &g, Vertex v, EdgeMap m )
{
  typename Graph::VertexProperty & prop = g.get_property_reference(v);
  return make_pair( typename EdgeMap::in_iterator( v,
                        get_in_edges( m, prop ).begin()),
                    typename EdgeMap::in_iterator( v,
                        get_in_edges( m, prop ).end()) ); 
}

template< class EdgeList >
inline pair<typename EdgeList::const_mapiterator, typename EdgeList::const_mapiterator>
in_edges( const EdgeList &edges )
{
  return make_pair( typename EdgeList::const_mapiterator(
                        edges.in_edges.begin()),
                    typename EdgeList::const_mapiterator(
                        edges.in_edges.end()) );
}

template< class Graph, class Vertex, class EdgeMap >
inline typename EdgeMap::Edge
in_edge( Graph &g, Vertex v, EdgeID_t e, EdgeMap m )
{
  typename EdgeMap::mapiterator it = get_in_edges( m, v, g ).find( e );
  return typename EdgeMap::Edge( it->second.get_v2(), g.get_known_vertex(v), it );
}

template< class Graph, class Vertex, class EdgeMap >
inline pair< typename EdgeMap::Edge, bool >
in_edge_test( Graph &g, Vertex v, EdgeID_t e, EdgeMap m )
{
  typename EdgeMap::mapiterator tmp = get_in_edges( m, v, g ).find( e );
  if( tmp != get_in_edges( m, v, g ).end() )
      return make_pair( typename EdgeMap::Edge( tmp->second.get_v2(), g.get_known_vertex(v), tmp ), true );
  else
      return make_pair( typename EdgeMap::Edge( g.get_known_vertex(v), g.get_known_vertex(v), tmp ), false );  
}

template< class Graph, class Vertex, class EdgeMap >
inline pair<typename EdgeMap::out_iterator,
    typename EdgeMap::out_iterator>
out_edges( Graph &g, Vertex v, EdgeMap m )
{
  typename Graph::VertexProperty & prop = g.get_property_reference(v);
  return make_pair( typename EdgeMap::out_iterator( v,
                        get_out_edges( m, prop ).begin()),
                    typename EdgeMap::out_iterator( v,
                        get_out_edges( m, prop ).end()) ); 
}

template< class EdgeList >
inline pair<typename EdgeList::const_mapiterator, typename EdgeList::const_mapiterator>
out_edges( const EdgeList &edges )
{
  return make_pair( typename EdgeList::const_mapiterator(edges.out_edges.begin()), 
                    typename EdgeList::const_mapiterator(edges.out_edges.end()) );
}

template< class Graph, class Vertex, class EdgeMap >
inline typename EdgeMap::Edge
out_edge( Graph &g, Vertex v, EdgeID_t e, EdgeMap m )
{
  typename EdgeMap::mapiterator it = get_out_edges( m, v, g ).find( e );
  return typename EdgeMap::Edge( g.get_known_vertex(v), it->second.get_v2(), it );
}

template< class Graph, class Vertex, class EdgeMap >
inline pair< typename EdgeMap::Edge, bool >
out_edge_test( Graph &g, Vertex v, EdgeID_t e, EdgeMap m )
{
  typename EdgeMap::mapiterator tmp = get_out_edges( m, v, g ).find( e );
  if( tmp != get_out_edges( m, v, g ).end() )
      return make_pair( typename EdgeMap::Edge( g.get_known_vertex(v), tmp->second.get_v2(), tmp ), true );
  else
      return make_pair( typename EdgeMap::Edge( g.get_known_vertex(v), g.get_known_vertex(v), tmp ), false );  
}

template< class Graph, class Vertex, class EdgeMap >
inline size_t
out_degree( Graph &g, Vertex v, EdgeMap m )
{
  return get_out_edges( m, v, g ).size();
}

template< class Graph, class Vertex, class EdgeMap >
inline size_t
in_degree( Graph &g, Vertex v, EdgeMap m )
{
  return get_in_edges( m, v, g ).size();
}

template< class Graph, class EdgeMap >
void
remove_delayed_edges( Graph &g, EdgeMap m, AllToAllBuffer &buf )
{
  buf.communicate();

  while( ! buf.is_empty() )
  {
    EdgeID_t e;
    VertexID_t v;
    buf.get( &e, 1 );
    buf.get( &v, 1 );
    get( m, v, g ).remove_edge( e );
  }
}

template< class Edge, class Graph, class EdgeMap >
void
remove_edge( Edge &e, Graph &g, EdgeMap m )
{
  if( is_out_edge(e) )
  {
    get( m, source(e,g), g ).remove_out_edge( e, g, m );
  }
  else
  {
    get( m, target(e,g), g ).remove_in_edge( e, g, m );
  };
}

template< class Graph, class EdgeMap >
void
remove_edges( Graph &g, EdgeMap m )
{
  typename Graph::VertexIterator vit, vend;
  boost::tie( vit, vend ) = g.get_local_vertices();
  for(; vit != vend ; vit++ )
  {
    get( m, *vit, g ).complete_graph_remove_edges( g );
  }
}

template< class Graph, class EdgeMap, class Function >
void
remove_edges_if( Graph &g, EdgeMap m, Function &f )
{
  typename Graph::VertexIterator vit, vend;
  boost::tie( vit, vend ) = g.get_local_vertices();
  for(; vit != vend ; vit++ )
  {
    get( m, *vit, g ).remove_edges_if( *vit, g, m, f );
  }
}

template< class Graph, class Iterator, class EdgeMap >
void
remove_in_edges( Graph &g, Iterator vit, Iterator vend, EdgeMap m )
{
  for(; vit != vend ; vit++ )
  {
    get( m, *vit, g ).remove_in_edges( g, m );
  }
}

template< class Graph, class Iterator, class EdgeMap >
void
remove_in_edges( Graph &g, Iterator vit, Iterator vend, EdgeMap m, AllToAllBuffer &buf )
{
  for(; vit != vend ; vit++ )
  {
    get( m, *vit, g ).remove_in_edges( g, m, buf );
  }
}

template< class Graph, class Iterator, class EdgeMap >
void
remove_out_edges( Graph &g, Iterator vit, Iterator vend, EdgeMap m )
{
  for(; vit != vend ; vit++ )
  {
    get( m, *vit, g ).remove_out_edges( g, m );
  }
}

template< class Graph, class Iterator, class EdgeMap >
void
remove_out_edges( Graph &g, Iterator vit, Iterator vend, EdgeMap m, AllToAllBuffer &buf )
{
  for(; vit != vend ; vit++ )
  {
    get( m, *vit, g ).remove_out_edges( g, m, buf );
  }
}

}

#endif // _PG_EDGES_HPP_

---