Provides the ability to pass information between vertices of two different graphs. More...

#include <graphlab/graph/graph_vertex_join.hpp>

Public Types
typedef LeftGraph	left_graph_type
	Type of the left graph.
typedef RightGraph	right_graph_type
	Type of the right graph.
typedef right_graph_type::vertex_type	left_vertex_type
	Vertex Type of the left graph.
typedef left_graph_type::vertex_type	right_vertex_type
	Vertex Type of the right graph.
typedef right_graph_type::local_vertex_type	left_local_vertex_type
	Local Vertex Type of the left graph.
typedef left_graph_type::local_vertex_type	right_local_vertex_type
	Local Vertex Type of the right graph.
typedef right_graph_type::vertex_data_type	left_data_type
	Vertex Data Type of the left graph.
typedef left_graph_type::vertex_data_type	right_data_type
	Vertex Data Type of the right graph.

Public Member Functions
	graph_vertex_join (distributed_control &dc, left_graph_type &left, right_graph_type &right)
template<typename LeftEmitKey , typename RightEmitKey >
void	prepare_injective_join (LeftEmitKey left_emit_key, RightEmitKey right_emit_key)
	Initializes the join by associating each vertex with a key.
template<typename JoinOp >
void	left_injective_join (JoinOp join_op)
	Performs an injective join from the right graph to the left graph.
template<typename JoinOp >
void	right_injective_join (JoinOp join_op)
	Performs an injective join from the left graph to the right graph.

Public Attributes
dc_dist_object < graph_vertex_join< LeftGraph, RightGraph > >	rmi

Detailed Description

template<typename LeftGraph, typename RightGraph>
class graphlab::graph_vertex_join< LeftGraph, RightGraph >

Provides the ability to pass information between vertices of two different graphs.

Template Parameters:

LeftGraph	Type of the left graph
RightGraph	Type of the right graph

The graph_vertex_join class allows information to be passed between vertices of two different graphs.

Given two graphs g1 and g2, possibly of different types:

   typedef distributed_graph<VData1, EData1> graph_1_type;
   typedef distributed_graph<VData2, EData2> graph_2_type;
   graph_1_type g1;
   graph_2_type g2;

A graph_vertex_join object can be created:

graph_vertex_type<graph_1_type, graph_2_type> vjoin(dc, g1, g2);

The first argument is the distributed control object. The second argument shall be referred to as the graph on the "left" side of the join, and the third argument shall be referred to as the graph on the "right" side of the join.

The join operates by having each vertex in both graph emit an integer key. Vertices with the same key are then combined into the same group. The semantics of the key depends on the join operation to be performed. Right now, the only join operation supported is the Left Injective Join and the Right Injective Join (see below).

Left Injective Join

For the left injective join, vertices in the same graph must emit distinct unique keys. i.e. Each vertex in g1 must emit a key which is different from all other vertices in g1. Vertices on the right graph are then matched with vertices on the left graph with the same key. The join operation is then allowed to modify vertices on the left graph given the data on the vertices of the right graph.

To emit the keys:

vjoin.prepare_injective_join(left_emit_key, right_emit_key);

left_emit_key and right_emit_key are functions (or lambda) with the following prototype:

size_t left_emit_key(const graph_1_type::vertex_type& vertex);

size_t right_emit_key(const graph_2_type::vertex_type& vertex);

They essentially take as a constant argument, the vertex of their respective graphs, and return an integer key. If the key has value (-1) it does not participate in the join. After keys are emitted and prepared with prepare_join, to perform a left injective join:

vjoin.left_injective_join(join_op);

Where join_op is a function with the following prototype:

void join_op(graph_1_type::vertex_type& left_vertex,

const graph_2_type::vertex_data_type right_vertex_data);

Note the asymmetry in the arguments: the left vertex is passed as a vertex_type, while for the right vertex, only the vertex data is accessible. The function may make modifications on the left vertex.

The left_injective_join() function must be called by all machines. As a result, it may be used from within an engine's graphlab::iengine::add_vertex_aggregator aggregator's finalize function.

Left Injective Join Example

I have two graphs with identical structure. The left graph has data

   struct left_vertex_data {
     size_t user_id;
     std::string user_name;
     std::string email_address;
     // ... serializers omitted ...
   }
   typedef distributed_graph<left_vertex_data, some_edge_data> left_graph_type;

However, when the left graph was constructed, there was no email address information conveniently available, and thus was left blank.

And the right graph has vertex data:

   struct right_vertex_data {
     size_t user_id;
     std::string email_address;
     // ... serializers omitted ...
   }
   typedef distributed_graph<right_vertex_data, some_edge_data> right_graph_type;

which was loaded from some other source, and contains all the email address information.

I create emit functions for both graphs :

   size_t emit_user_id_field_left(const left_graph_type::vertex_type& vtype) {
     return vtype.data().user_id;
   }
   size_t emit_user_id_field_left(const right_graph_type::vertex_type& vtype) {
     return vtype.data().user_id;
   }

Create a join object and prepare the join:

   graph_vertex_join<left_graph_type, right_graph_type> vjoin(dc, 
                                                              left_graph, 
                                                              right_graph);
   vjoin.prepare_injective_join(emit_user_id_field_left, 
                                emit_user_id_field_right);

To copy the email address field from the right graph to the left graph:

   void join_email_address(left_graph_type::vertex_type& left_vertex,
                           const right_vertex_data& rvtx) {
     left_vertex.data().email_address = rvtx.email_address; 
   }
   
   vjoin.left_injective_join(join_email_address);

Right Injective Join

The right injective join is similar to the left injective join, but with types reversed.

Definition at line 171 of file graph_vertex_join.hpp.

Member Function Documentation

template<typename LeftGraph , typename RightGraph >

template<typename JoinOp >

void graphlab::graph_vertex_join< LeftGraph, RightGraph >::left_injective_join ( JoinOp join_op )

inline

Performs an injective join from the right graph to the left graph.

Template Parameters:

JoinOp The type of the joinop function. It should not be necessary to specify this. C++ type inference should be able to infer this automatically.

Parameters:

join_op The joining function. May be a function pointer or a lambda matching the prototype void join_op(LeftGraph::vertex_type& left_vertex, const RightGraph::vertex_data_type right_vertex_data);

prepare_injective_join() must be called before hand. All machines must call this function. join_op will be called on each left vertex with the data on a right vertex which emitted the same key in prepare_injective_join(). The join_op function is allowed to modify the vertex data on the left graph.

Definition at line 304 of file graph_vertex_join.hpp.

template<typename LeftGraph , typename RightGraph >

template<typename LeftEmitKey , typename RightEmitKey >

void graphlab::graph_vertex_join< LeftGraph, RightGraph >::prepare_injective_join	(	LeftEmitKey	left_emit_key,
		RightEmitKey	right_emit_key
	)

inline

Initializes the join by associating each vertex with a key.

Template Parameters:

LeftEmitKey	Type of the left_emit_key parameter. It should not be necessary to specify this. C++ type inference should be able to infer this automatically.
RightEmitKey	Type of the right_emit_key parameter. It should not be necessary to specify this. C++ type inference should be able to infer this automatically.

Parameters:

left_emit_key	A function which takes a vertex_type from the left graph and emits an integral key value. Can be a lambda, of the prototype: size_t left_emit_key(const LeftGraph::vertex_type& vertex);
right_emit_key	A function which takes a vertex_type from the right graph and emits an integral key value. Can be a lambda, of the prototype: size_t right_emit_key(const RightGraph::vertex_type& vertex);

The semantics of the key depend on the actual join operation performed. This function must be called by all machines.

left_emit_key and right_emit_key are functions (or lambda) with the following prototype:

size_t left_emit_key(const graph_1_type::vertex_type& vertex);

size_t right_emit_key(const graph_2_type::vertex_type& vertex);

They essentially take as a constant argument, the vertex of their respective graphs, and return an integer key. If a vertex emits the key (size_t)(-1) it does not participate in the join.

prepare_injective_join() only needs to be called once. After which an arbitrary number of left_injective_join() and right_injective_join() calls may be made.

If after a join, a new join is to be performed on the same graph using new data, or new emit functions, prepare_injective_join() can be called again to recompute the join.

Definition at line 255 of file graph_vertex_join.hpp.

template<typename LeftGraph , typename RightGraph >

template<typename JoinOp >

void graphlab::graph_vertex_join< LeftGraph, RightGraph >::right_injective_join ( JoinOp join_op )

inline

Performs an injective join from the left graph to the right graph.

Template Parameters:

JoinOp The type of the joinop function. It should not be necessary to specify this. C++ type inference should be able to infer this automatically.

Parameters:

join_op The joining function. May be a function pointer or a lambda matching the prototype void join_op(RightGraph::vertex_type& right_vertex, const LeftGraph::vertex_data_type left_vertex_data);

prepare_injective_join() must be called before hand. All machines must call this function. join_op will be called on each rght vertex with the data on a left vertex which emitted the same key in prepare_injective_join(). The join_op function is allowed to modify the vertex data on the right graph.

Definition at line 330 of file graph_vertex_join.hpp.

The documentation for this class was generated from the following file:

graphlab/graph/graph_vertex_join.hpp

Public Types

Public Member Functions

Public Attributes

Detailed Description

template<typename LeftGraph, typename RightGraph> class graphlab::graph_vertex_join< LeftGraph, RightGraph >

Left Injective Join

Left Injective Join Example

Right Injective Join

Member Function Documentation

template<typename LeftGraph, typename RightGraph>
class graphlab::graph_vertex_join< LeftGraph, RightGraph >