Re: [boost] [BGL] Multithread problem inserting edges and exploring the same graph

21 Oct 2009

      Cosimo Calabrese ha scritto:
...
Jeremiah Willcock wrote:
...
That only works if both graphs are adjacency_lists and you have 
control over the graph types.  I would personally just make:
template <typename T>
struct from_first_graph {T data;};
template <typename T>
struct from_second_graph {T data;};
and then have my variants be:
boost::variant<from_first_graph<graph_traits<First>::vertex_descriptor>,
               from_second_graph<graph_traits<Second>::vertex_descriptor>
...
and the same for edge descriptors.  This will disambiguate the types 
for arbitrary graphs.
It seems a very good idea to me. I'm trying it. I'll tell you about it 
ASAP.
I'm nearly to the end of the work, but I've encountered a problem. I've 
implemented all the traversal concepts, but I'm in difficulty with the 
Property concepts, in particular on the get( property, key ) function. I 
don't understand where I'm wrong. I was inspired by the filtered_graph 
and reverse_graph adaptor, but without results.

Sure, I'm relatively new to Boost, and I haven't understand very well 
how the property lib works, applied on the BGL.

I attach 3 files:
- the union_different_iterator, that provides a union view of 2 containers;
- the union_graph, that provides a union view of 2 graphs (that uses 
union_different_iterator);
- a main module, that tests the union_graph.

Please, can anyone help me?

Thanks,
Cosimo Calabrese.

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

#include "union_graph.hpp"

using namespace boost;
using namespace std;

namespace boost 
{
	// properties installation
	enum vertex_originality_t { vertex_originality = 101 };
	enum edge_ID_t { edge_ID = 102 };
	enum edge_originality_t { edge_originality = 103 };
	BOOST_INSTALL_PROPERTY(vertex, originality);
	BOOST_INSTALL_PROPERTY(edge, ID);
	BOOST_INSTALL_PROPERTY(edge, originality);
}

typedef property< vertex_name_t, string, 
				property < vertex_originality_t, bool > > vertexs_properties;							
typedef property < edge_ID_t, long,
			property < edge_weight_t, long, 
				property < edge_originality_t, bool > > > edges_properties;
typedef adjacency_list< listS, vecS, directedS, vertexs_properties, edges_properties > Graph;
typedef property_map< Graph, edge_weight_t >::type				edge_weight_map_t;

int main()
{	
	// Setup Test
	const long NUM_VERTICES = 10;
	graph_traits<Graph>::edge_descriptor e; 
	bool inserted;

	// base hraph
	Graph baseGraph( NUM_VERTICES );
	edge_weight_map_t edge_weight_map_base = get( edge_weight, baseGraph );

	for ( long i = 0; i < NUM_VERTICES ; ++i )
	{
		// 0->1, 1->2, 2->3, ... n->n+1 ..., 9->0
		tie(e, inserted) = add_edge( i % NUM_VERTICES, (i + 1) % NUM_VERTICES, baseGraph );
		if ( inserted )
			edge_weight_map_base[ e ] = 1;
	}

	cout << "Base graph:" << endl;
	print_graph( baseGraph );
	cout << endl;

	// little graph
	Graph littleGraph( NUM_VERTICES );
	edge_weight_map_t edge_weight_map_little = get( edge_weight, littleGraph );

	tie(e, inserted) = add_edge( 0, 6, littleGraph );
	if ( inserted )
		edge_weight_map_little[ e ] = 1;

	cout << "Little graph:" << endl;
	print_graph( littleGraph );
	cout << endl;

	// union graph
	//cout << "Union graph:" << endl;
	//print_graph( make_union_graph( baseGraph, littleGraph ) );
	//cout << endl;

	// union graph, test vertex (0)
	typedef union_graph<Graph, Graph> UG;
	UG ug = make_union_graph( baseGraph, littleGraph );
	graph_traits<UG>::vertex_descriptor u = WR1<graph_traits<Graph>::vertex_descriptor>( 0 );

	// Test 1: out_edges e out_degree
	{
		graph_traits<UG>::out_edge_iterator oei, oei_end;
		for ( tie( oei, oei_end ) = out_edges( u, ug ); oei != oei_end; ++oei )
		{
			graph_traits<UG>::vertex_descriptor t = target( *oei, ug );

			cout << "Outer target: ";
			if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &t ) )
				cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( t )._data << endl;
			else
				cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( t )._data << endl;
		}
		cout << "Out degree: " << out_degree( u, ug ) << endl << endl;
	}
/*
	// Bidirectionality required for this test

	// Test 2: in_edges, in_degree e degree
	{
		graph_traits<UG>::in_edge_iterator iei, iei_end;
		for ( tie( iei, iei_end ) = in_edges( u, ug ); iei != iei_end; ++iei )
		{
			graph_traits<UG>::vertex_descriptor s = source( *iei, ug );

			if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &s ) )
				cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( s )._data << endl;
			else
				cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( s )._data << endl;
		}
		cout << "In degree: " << in_degree( u, ug ) << endl;
		cout << "Degree: " << degree( u, ug ) << endl;
	}
*/

	// Test 3: adjacent_vertices
	{
		graph_traits<UG>::adjacency_iterator ai, ai_end;
		for ( tie( ai, ai_end ) = adjacent_vertices( u, ug ); ai != ai_end; ++ai )
		{
			cout << "Adjacency: ";
			if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &*ai ) )
				cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( *ai )._data << endl;
			else
				cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( *ai )._data << endl;
		}
		cout << endl;
	}

	// Test 4: num_vertices, vertices
	{
		cout << "Num vertices: " << num_vertices( ug ) << endl;

		graph_traits<UG>::vertex_iterator vi, vi_end;
		for ( tie( vi, vi_end ) = vertices( ug ); vi != vi_end; ++vi )
		{
			cout << "Graph Vertex: ";
			boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &*vi );
			if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &*vi ) )
				cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( *vi )._data << endl;
			else
				cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( *vi )._data << endl;
		}
		cout << endl;
	}

	// Test 5: num_edges, edges, source, target
	{
		cout << "Num edges: " << num_edges( ug ) << endl;

		graph_traits<UG>::edge_iterator ei, ei_end;
		for ( tie( ei, ei_end ) = edges( ug ); ei != ei_end; ++ei )
		{
			cout << "Graph edge: ";

			graph_traits<UG>::vertex_descriptor s = source( *ei, ug );
			graph_traits<UG>::vertex_descriptor t = target( *ei, ug );

			if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &s ) )
				cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( s )._data;
			else
				cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( s )._data;

			cout << "->";

			if ( boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( &t ) )
				cout << boost::get<WR1<graph_traits<Graph>::vertex_descriptor> >( t )._data;
			else
				cout << boost::get<WR2<graph_traits<Graph>::vertex_descriptor> >( t )._data;

			cout << endl;
		}
		cout << endl;
	}

	// Test 6: edge
	{
		graph_traits<UG>::vertex_descriptor u = WR2<graph_traits<Graph>::vertex_descriptor>( 0 );
		graph_traits<UG>::vertex_descriptor v = WR1<graph_traits<Graph>::vertex_descriptor>( 6 );

		graph_traits<UG>::edge_descriptor e;
		bool exists;

		tie( e, exists ) = edge( u, v, ug );
		cout << ( exists ? "This edge exists" : "This edge doesn't exists" ) << endl << endl;
	}

	// Test 7: properties
	{		
		graph_traits<UG>::vertex_descriptor u = WR1<graph_traits<Graph>::vertex_descriptor>( 0 );

		typedef property_map< Graph, vertex_index_t >::type					vertex_index_map_t;
		vertex_index_map_t indexmap = get( vertex_index, ug );
		//get( indexmap, ug, u );
	}
}

#ifndef _UNION_DIFFERENT_ITERATOR
#define _UNION_DIFFERENT_ITERATOR

#include <boost/variant.hpp>

#include <iterator>
#include <utility>

using namespace std;

template <typename FI1, typename FI2, template <typename> class WR_A, template <typename> class WR_B>
class union_different_iterator 
	: public std::iterator< forward_iterator_tag, 
                            boost::variant< 
                              WR_A<typename iterator_traits<FI1>::value_type>,
                              WR_B<typename iterator_traits<FI2>::value_type> 
                            >
                          >
{
public:
	typedef union_different_iterator<FI1, FI2, WR_A, WR_B> self;

	typedef typename iterator_traits<FI1>::value_type value_type1;
	typedef typename iterator_traits<FI2>::value_type value_type2;

	union_different_iterator()
	{}

	union_different_iterator( FI1 begin_a, FI1 end_a, FI2 begin_b, FI2 end_b )
		: _begin_a( begin_a ), _end_a( end_a ), _curr_a( begin_a ),
		  _begin_b( begin_b ), _end_b( end_b ), _curr_b( begin_b )
	{}

	union_different_iterator( const self& other )
		: _begin_a( other._begin_a ), _end_a( other._end_a ), _curr_a( other._curr_a ),
		  _begin_b( other._begin_b ), _end_b( other._end_b ), _curr_b( other._curr_b )
	{}

	const self& operator=( const self& other )
	{
		_begin_a = other._begin_a;
		_end_a = other._end_a;
		_curr_a = other._curr_a;

		_begin_b = other._begin_b;
		_end_b = other._end_b;
		_curr_b = other._curr_b;

		return(*this);
	}

	bool operator==( const self& other ) const
	{
		return ( _curr_a == other._curr_a ) && ( _curr_b == other._curr_b );
	}

	bool operator!=( const self& other ) const
	{
		return !this->operator == ( other );
	}

	/*const*/ value_type operator*() const
	{ 
		return _curr_a == _end_a ? 
			   value_type( WR_B<value_type2>( *_curr_b ) ) : 
               value_type( WR_A<value_type1>( *_curr_a ) ) ;
	}
/*
	value_type operator*() 
	{
		return _curr_a == _end_a ? 
			   value_type( WR_B<value_type2>( *_curr_b ) ) : 
               value_type( WR_A<value_type1>( *_curr_a ) ) ;
	}
*/

/*
	const pointer operator->() const 
	{
		return _curr_a == _end_a ? _curr_b.operator->() : _curr_a.operator->();
	}

	pointer operator->() 
	{
		return _curr_a == _end_a ? _curr_b.operator->() : _curr_a.operator->();
	}
*/
	self& operator++() 
	{
		if ( _curr_a == _end_a )
			++_curr_b;
		else
			++_curr_a; 
		return *this; 
	}

	self operator++(int) 
	{
		self tmp = *this; ++( *this ); return tmp; 
	}

	self& operator--()
	{
		if (_curr_b == _begin_b )
			--_curr_a;
		else
			--_curr_b; 
		return *this; 
	}

	self operator--(int) 
	{
		self tmp = *this; --( *this ); return tmp; 
	}

	template <typename T>
	bool isTypeOf()
	{
		if ( _curr_a == _end_a )
			return boost::is_same<WR_B<T>, WR_B<value_type2> >::value;
		else
			return boost::is_same<WR_A<T>, WR_A<value_type1> >::value;

	}
private:
	FI1 _begin_a;
	FI1 _end_a;
	FI1 _curr_a;

	FI2 _begin_b;
	FI2 _end_b;
	FI2 _curr_b;
};

template <typename FI1, typename FI2, template <typename> class WR_A, template <typename> class WR_B>
inline union_different_iterator<FI1, FI2, WR_A, WR_B>
make_union_different_iterator(FI1 begin_a, FI1 end_a, FI2 begin_b, FI2 end_b) {
	return union_different_iterator<FI1, FI2, WR_A, WR_B>(begin_a, end_a, begin_b, end_b);
}

template <typename FI1, typename FI2, template <typename> class WR_A, template <typename> class WR_B>
inline union_different_iterator<FI1, FI2, WR_A, WR_B>
make_union_different_iterator( pair<FI1, FI1> range_a, pair<FI2, FI2> range_b ) {
	return union_different_iterator<FI1, FI2, WR_A, WR_B>(range_a.first, range_a.second, 
		                                                range_b.first, range_b.second);
}

template <typename FI1, typename FI2, template <typename> class WR_A, template <typename> class WR_B>
inline pair< union_different_iterator<FI1, FI2, WR_A, WR_B>,
             union_different_iterator<FI1, FI2, WR_A, WR_B> >
make_union_different_range( FI1 begin_a, FI1 end_a, FI2 begin_b, FI2 end_b ) {
	return make_pair( make_union_different_iterator<FI1, FI2, WR_A, WR_B>( begin_a, end_a, begin_b, end_b ), 
		              make_union_different_iterator<FI1, FI2, WR_A, WR_B>( end_a, end_a, end_b, end_b ) );
}

template <typename FI1, typename FI2, template <typename> class WR_A, template <typename> class WR_B>
inline pair< union_different_iterator<FI1, FI2, WR_A, WR_B>,
             union_different_iterator<FI1, FI2, WR_A, WR_B> >
make_union_different_range( pair<FI1, FI1> range_a, pair<FI2, FI2> range_b ) {
	return make_pair( make_union_different_iterator<FI1, FI2, WR_A, WR_B>( range_a, range_b ), 
		              make_union_different_iterator<FI1, FI2, WR_A, WR_B>( range_a.second, range_a.second, 
					                                                       range_b.second, range_b.second ) );
}

#endif

#ifndef BOOST_UNION_GRAPH_HPP
#define BOOST_UNION_GRAPH_HPP

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/exception.hpp>
#include <boost/variant.hpp>

#include "union_different_iterator.hpp"

  //===========================================================================
  // wrappers

template <typename T>
class WR1
{
public:
	WR1() : _data( T() ) {}
	WR1( T data ) : _data( data ) {}
	const WR1<T> operator=( const WR1<T>& other )
	{
		_data = other._data;
		return(*this);
	}
	bool operator==( const WR1<T>& other ) const
	{
		return _data == other._data;
	}
	T _data;
};

template <typename T>
class WR2
{
public:
	WR2() : _data( T() ) {}
	WR2( T data ) : _data( data ) {}
	const WR2<T> operator=( const WR2<T>& other )
	{
		_data = other._data;
		return(*this);
	}
	bool operator==( const WR2<T>& other ) const
	{
		return _data == other._data;
	}

	T _data;
};

namespace boost {

  struct not_same_num_vertices : public bad_graph {
    not_same_num_vertices()
      : bad_graph("The two graphs of an union_graph must have the same number of vertices.")
    { }
  };

  //===========================================================================
  // union_graph

  struct union_graph_tag { };

  template <typename Graph1, typename Graph2>
  class union_graph {

    typedef union_graph<Graph1, Graph2> self;
  public:
    typedef Graph1 graph_type1;
    typedef Graph2 graph_type2;

    // Constructor
	union_graph( const Graph1& g1, const Graph2& g2 ) : m_g1(g1), m_g2(g2)
	{
      // TODO: precondition: Traits::directed_category must be the same
      // TODO: precondition: Traits::Traits::traversal_category be the same
      // TODO: precondition: Traits::edge_parallel_category be the same

      if ( num_vertices( g1 ) != num_vertices( g2 ) )
        throw not_same_num_vertices();
	}

    // Graph requirements
	typedef boost::variant<WR1<typename graph_traits<Graph1>::vertex_descriptor>, 
		                   WR2<typename graph_traits<Graph2>::vertex_descriptor> > vertex_descriptor;
    typedef typename graph_traits<Graph1>::directed_category          directed_category;
    typedef typename graph_traits<Graph1>::traversal_category         traversal_category;
    typedef typename graph_traits<Graph1>::edge_parallel_category     edge_parallel_category;

    // IncidenceGraph requirements
	typedef boost::variant<WR1<typename graph_traits<Graph1>::edge_descriptor>, 
		                   WR2<typename graph_traits<Graph2>::edge_descriptor> >edge_descriptor;
	typedef union_different_iterator< typename graph_traits<Graph1>::out_edge_iterator, 
                                      typename graph_traits<Graph2>::out_edge_iterator,
									  WR1, WR2 > out_edge_iterator;
	typedef typename graph_traits<Graph1>::degree_size_type           degree_size_type;

    // AdjacencyGraph requirements
	typedef union_different_iterator< typename graph_traits<Graph1>::adjacency_iterator, 
                                      typename graph_traits<Graph2>::adjacency_iterator,
									  WR1, WR2 > adjacency_iterator;

    // BidirectionalGraph requirements    
	typedef union_different_iterator< typename graph_traits<Graph1>::in_edge_iterator, 
                                      typename graph_traits<Graph2>::in_edge_iterator,
									  WR1, WR2 > in_edge_iterator;

    // VertexListGraph requirements
	typedef union_different_iterator< typename graph_traits<Graph1>::vertex_iterator, 
                                      typename graph_traits<Graph2>::vertex_iterator,
									  WR1, WR2 > vertex_iterator;
	typedef typename graph_traits<Graph1>::vertices_size_type vertices_size_type;

    // EdgeListGraph requirements
	typedef union_different_iterator< typename graph_traits<Graph1>::edge_iterator, 
                                      typename graph_traits<Graph2>::edge_iterator,
									  WR1, WR2 > edge_iterator;

	typedef typename graph_traits<Graph1>::edges_size_type            edges_size_type;

	typedef typename ::boost::edge_property_type<Graph1>::type edge_property_type;	
	typedef typename ::boost::vertex_property_type<Graph1>::type vertex_property_type;	

    typedef union_graph_tag graph_tag;

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

    // Bundled properties support
    template<typename Descriptor>
    typename graph::detail::bundled_result<Graph1, Descriptor>::type&
    operator[](Descriptor x)
    { return const_cast<Graph1&>(this->m_g1)[x]; }

    template<typename Descriptor>
    typename graph::detail::bundled_result<Graph1, Descriptor>::type const&
    operator[](Descriptor x) const
    { return this->m_g1[x]; }

#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES

    static vertex_descriptor null_vertex()
    {
       return Graph1::null_vertex();
    }

	// private:
	const Graph1& m_g1;
	const Graph2& m_g2;
  };

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

  template<typename Graph1, typename Graph2>
  struct vertex_bundle_type<union_graph<Graph1, Graph2> > 
    : vertex_bundle_type<Graph1> { };

  template<typename Graph1, typename Graph2>
  struct edge_bundle_type<union_graph<Graph1, Graph2> > 
    : edge_bundle_type<Graph1> { };

#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES

  //===========================================================================
  // Non-member functions for the Filtered Edge Graph

  // Helper functions
  template <typename Graph1, typename Graph2>
  inline union_graph<Graph1, Graph2>
  make_union_graph(Graph1& g1, Graph2& g2) {
    return union_graph<Graph1, Graph2>(g1, g2);
  }

  template <typename Graph1, typename Graph2>
  inline union_graph<const Graph1, const Graph2>
  make_union_graph(const Graph1& g1, const Graph2& g2 ) {
    return union_graph<const Graph1, const Graph2>(g1, g2);
  }

  namespace detail
  {
    template <typename Graph1, typename Graph2>
	std::pair<typename graph_traits<Graph1>::vertex_descriptor,
              typename graph_traits<Graph2>::vertex_descriptor>
    get_corresponding_vertices(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u)
    {
      typedef union_graph<Graph1, Graph2> UG;
      typedef graph_traits<Graph1>::vertex_descriptor VD1;
      typedef graph_traits<Graph2>::vertex_descriptor VD2;

	  VD1 u1;
      VD2 u2;

      if ( boost::get<WR1<VD1> >( &u ) )
      {
        u1 = boost::get<WR1<VD1> >( u )._data;
        u2 = u1;
      }
      else
      {
        u2 = boost::get<WR2<VD2> >( u )._data;
        u1 = u2;
      }

	  return make_pair( u1, u2 );
    }
  }

  // IncidenceGraph requirements
  template <typename Graph1, typename Graph2>
  std::pair<typename union_graph<Graph1, Graph2>::out_edge_iterator,
            typename union_graph<Graph1, Graph2>::out_edge_iterator>
  out_edges(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u,
            const union_graph<Graph1, Graph2>& g)
  {
    typedef union_graph<Graph1, Graph2> UG;
	typedef graph_traits<Graph1>::vertex_descriptor VD1; 
    typedef graph_traits<Graph2>::vertex_descriptor VD2; 
	typedef graph_traits<Graph1>::out_edge_iterator OEI1;
    typedef graph_traits<Graph2>::out_edge_iterator OEI2;

	VD1 u1;
	VD2 u2;

	tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u );
	return make_union_different_range<OEI1, OEI2, WR1, WR2>( out_edges(u1, g.m_g1), out_edges(u2, g.m_g2) );
  }

  template <typename Graph1, typename Graph2>
  typename union_graph<Graph1, Graph2>::vertex_descriptor
  source(const typename union_graph<Graph1, Graph2>::edge_descriptor& e,
         const union_graph<Graph1, Graph2>& g)
  {
    typedef union_graph<Graph1, Graph2> UG;
	typedef graph_traits<Graph1>::vertex_descriptor VD1;
    typedef graph_traits<Graph2>::vertex_descriptor VD2;
	typedef graph_traits<Graph1>::edge_descriptor ED1;  
    typedef graph_traits<Graph2>::edge_descriptor ED2;  

    if ( boost::get<WR1<ED1> >( &e ) )
	{
      return graph_traits<UG>::vertex_descriptor( WR1<VD1>( source( boost::get<WR1<ED1> >( e )._data, g.m_g1 ) ) );
	}
	else
	{
      return graph_traits<UG>::vertex_descriptor( WR2<VD2>( source( boost::get<WR2<ED2> >( e )._data, g.m_g2 ) ) );
	}
  }

  template <typename Graph1, typename Graph2>
  typename union_graph<Graph1, Graph2>::vertex_descriptor
  target(const typename union_graph<Graph1, Graph2>::edge_descriptor& e,
         const union_graph<Graph1, Graph2>& g)
  {
    typedef union_graph<Graph1, Graph2> UG;
	typedef graph_traits<Graph1>::vertex_descriptor VD1;
    typedef graph_traits<Graph2>::vertex_descriptor VD2;
	typedef graph_traits<Graph1>::edge_descriptor ED1;  
    typedef graph_traits<Graph2>::edge_descriptor ED2;  

    if ( boost::get<WR1<ED1> >( &e ) )
	{
      return graph_traits<UG>::vertex_descriptor( WR1<VD1>( target( boost::get<WR1<ED1> >( e )._data, g.m_g1 ) ) );
	}
	else
	{
      return graph_traits<UG>::vertex_descriptor( WR2<VD2>( target( boost::get<WR2<ED2> >( e )._data, g.m_g2 ) ) );
	}
  }

  template <typename Graph1, typename Graph2>
  typename union_graph<Graph1, Graph2>::degree_size_type
  out_degree(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u,
             const union_graph<Graph1, Graph2>& g)
  {
    typedef union_graph<Graph1, Graph2> UG;
	typedef graph_traits<Graph1>::vertex_descriptor VD1;
    typedef graph_traits<Graph2>::vertex_descriptor VD2;

	VD1 u1;
	VD2 u2;

	tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u );
	return out_degree(u1, g.m_g1) + out_degree(u2, g.m_g2);
  }

  // BidirectionalGraph requirements
  template <typename Graph1, typename Graph2>
  std::pair<typename union_graph<Graph1, Graph2>::in_edge_iterator,
            typename union_graph<Graph1, Graph2>::in_edge_iterator>
  in_edges(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u,
           const union_graph<Graph1, Graph2>& g)
  {
    typedef union_graph<Graph1, Graph2> UG;
	typedef graph_traits<Graph1>::vertex_descriptor VD1;
    typedef graph_traits<Graph2>::vertex_descriptor VD2;
	typedef graph_traits<Graph1>::in_edge_iterator IEI1;
    typedef graph_traits<Graph2>::in_edge_iterator IEI2;

	VD1 u1;
	VD2 u2;

	tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u );
	return make_union_different_range<IEI1, IEI2, WR1, WR2>( in_edges<Graph1>(u1, g.m_g1), in_edges<Graph2>(u2, g.m_g2) );
  }

  template <typename Graph1, typename Graph2>
  typename union_graph<Graph1, Graph2>::degree_size_type
  in_degree(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u,
             const union_graph<Graph1, Graph2>& g)

  {
    typedef union_graph<Graph1, Graph2> UG;
	typedef graph_traits<Graph1>::vertex_descriptor VD1;
    typedef graph_traits<Graph2>::vertex_descriptor VD2;

	VD1 u1;
	VD2 u2;

	tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u );
	return in_degree(u1, g.m_g1) + in_degree(u2, g.m_g2);
  }

  template <typename Graph1, typename Graph2>
  typename union_graph<Graph1, Graph2>::degree_size_type
  degree(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u,
             const union_graph<Graph1, Graph2>& g)
  {
    return out_degree(u, g) + in_degree(u, g);
  }

  // AdjacencyGraph requirements
  template <typename Graph1, typename Graph2>
  std::pair<typename union_graph<Graph1, Graph2>::adjacency_iterator,
            typename union_graph<Graph1, Graph2>::adjacency_iterator>
  adjacent_vertices(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u,
                    const union_graph<Graph1, Graph2>& g)
  {
    typedef union_graph<Graph1, Graph2> UG;
	typedef graph_traits<Graph1>::vertex_descriptor VD1; 
    typedef graph_traits<Graph2>::vertex_descriptor VD2; 
	typedef graph_traits<Graph1>::adjacency_iterator AI1;
    typedef graph_traits<Graph2>::adjacency_iterator AI2;

	VD1 u1;
	VD2 u2;

	tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u );
	return make_union_different_range<AI1, AI2, WR1, WR2>( adjacent_vertices(u1, g.m_g1), adjacent_vertices(u2, g.m_g2) );
  }

  // VertexListGraph requirements
  template <typename Graph1, typename Graph2>
  typename union_graph<Graph1, Graph2>::vertices_size_type
  num_vertices(const union_graph<Graph1, Graph2>& g)
  {
    return num_vertices(g.m_g1);
  }

  template <typename Graph1, typename Graph2>
  std::pair<typename union_graph<Graph1, Graph2>::vertex_iterator,
            typename union_graph<Graph1, Graph2>::vertex_iterator>
  vertices(const union_graph<Graph1, Graph2>& g)
  {
    typedef union_graph<Graph1, Graph2> UG;
	typedef graph_traits<Graph1>::vertex_iterator VI1;
    typedef graph_traits<Graph2>::vertex_iterator VI2;

	VI2 vi2 = VI2();
	VI2 vi2_end = vi2;

    return make_union_different_range<VI1, VI2, WR1, WR2>( vertices(g.m_g1), make_pair(vi2, vi2_end) );
  }

  // EdgeListGraph requirements
  template <typename Graph1, typename Graph2>
  typename union_graph<Graph1, Graph2>::edges_size_type
  num_edges(const union_graph<Graph1, Graph2>& g)
  {
    return num_edges(g.m_g1) + num_edges(g.m_g2);
  }

  template <typename Graph1, typename Graph2>
  std::pair<typename union_graph<Graph1, Graph2>::edge_iterator,
            typename union_graph<Graph1, Graph2>::edge_iterator>
  edges(const union_graph<Graph1, Graph2>& g)
  {
    typedef union_graph<Graph1, Graph2> UG;
	typedef graph_traits<Graph1>::edge_iterator EI1;
    typedef graph_traits<Graph2>::edge_iterator EI2;

    return make_union_different_range<EI1, EI2, WR1, WR2>( edges(g.m_g1), edges(g.m_g2) );
  }

  // AdjacencyMatrix requirements
  template <typename Graph1, typename Graph2>
  std::pair<typename union_graph<Graph1, Graph2>::edge_descriptor, bool>
  edge(const typename union_graph<Graph1, Graph2>::vertex_descriptor& u,
       const typename union_graph<Graph1, Graph2>::vertex_descriptor& v,
       const union_graph<Graph1, Graph2>& g)
  {
    typedef union_graph<Graph1, Graph2> UG;
	typedef graph_traits<Graph1>::vertex_descriptor VD1;
    typedef graph_traits<Graph2>::vertex_descriptor VD2;
	typedef graph_traits<Graph1>::edge_descriptor ED1;  
    typedef graph_traits<Graph2>::edge_descriptor ED2;  

	VD1 u1, v1;
	VD2 u2, v2;

	tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u );
	tie( v1, v2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( v );

	// g1 check
	{
      ED1 e1;
      bool exists;
      tie( e1, exists ) = edge(u1, v1, g.m_g1);

      if ( exists )
        return make_pair( graph_traits<UG>::edge_descriptor( WR1<ED1>( e1 ) ), exists );
	}

	// g2 check
	{
      ED2 e2;
      bool exists;
      tie( e2, exists ) = edge(u2, v2, g.m_g2);
      return make_pair( graph_traits<UG>::edge_descriptor( WR2<ED2>( e2 ) ), exists );
	}
  }

  //===========================================================================
  // Property map

  namespace detail {
    struct union_graph_property_selector {
      template <class UnionGraph, class Property, class Tag>
      struct bind_ {
        typedef typename UnionGraph::graph_type Graph;
        typedef property_map<Graph, Tag> Map;
        typedef typename Map::type type;
        typedef typename Map::const_type const_type;
      };
    };    
  } // namespace detail

  template <>  
  struct vertex_property_selector<union_graph_tag> {
    typedef detail::union_graph_property_selector type;
  };
  template <>  
  struct edge_property_selector<union_graph_tag> {
    typedef detail::union_graph_property_selector type;
  };

  template <typename Graph1, typename Graph2, typename Property>
  typename property_map<Graph1, Property>::type
  get(Property p, union_graph<Graph1, Graph2>& g)
  {
    return get(p, const_cast<Graph1&>(g.m_g1));
  }

  template <typename Graph1, typename Graph2, typename Property>
  typename property_map<Graph1, Property>::const_type
  get(Property p, const union_graph<Graph1, Graph2>& g)
  {
    return get(p, (const Graph1&)g.m_g1);
  }

/*
  template <typename Graph1, typename Graph2, typename Property, 
            typename Key>
  typename property_map_value<Graph1, Property>::type
  get(Property p, const union_graph<Graph1, Graph2>& g, const Key& k)
  {
    return get(p, (const Graph1&)g.m_g1, k);
  }
*/

  template <typename Graph1, typename Graph2, typename Property>
  typename property_map_value<Graph1, Property>::type
  get(Property p, const union_graph<Graph1, Graph2>& g, const typename union_graph<Graph1, Graph2>::vertex_descriptor& u)
  {
	typedef graph_traits<Graph1>::vertex_descriptor VD1; 
    typedef graph_traits<Graph2>::vertex_descriptor VD2; 

	VD1 u1;
	VD2 u2;
	//tie( u1, u2 ) = detail::get_corresponding_vertices<Graph1, Graph2>( u );

    return get(p, (const Graph1&)g.m_g1, u1);
  }

  template <typename Graph1, typename Graph2, typename Property, 
            typename Key, typename Value>
  void
  put(Property p, const union_graph<Graph1, Graph2>& g, const Key& k,
      const Value& val)
  {
    put(p, const_cast<Graph1&>(g.m_g1), k, val);
  }

} // namespace boost

#endif // BOOST_UNION_GRAPH_HPP