|
|
Boost : |
Subject: Re: [boost] [BGL] Multithread problem inserting edges and exploring the same graph
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2009-10-21 14:55:02
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk