multi-graph support in giraph

[André Kelpe <ef...@googlemail.com>]

Hi list,

in my current usage of giraph I ran into the limitation that the API is centered
around simple graphs but in many applications you are actually dealing with
multi-graphs. One simple example is a road network, where there can be n edges
between 2 vertices. For my current program I could work around the "limitation"
by using an ArrayWritable as the edge value, which contains all edges that are
connectors to a neighbour vertex. That is however not the cleanest of all
approaches.

The pregel paper describes an API, where you work with iterators to all your
outgoing edges and you then can access the vertex on the other end with a method
call (see the impl of Shortest Path in the paper). That kind of API would
totally allow having multiple edges connecting the same two vertices directly
while the current API with getEdgeValue(vertexId) does not. What is the current
view on this, is that a feature, that would be welcome? Should I open a JIRA
for the discussion? Am I overlooking something?

Thanks!

André

Re: creating non existing vertices by sending messages

[Avery Ching <ac...@apache.org>]

Thanks for the comments David.  The behavior of what happens is 
completely defined by the chosen VertexResolver, see 
(GiraphJob#setWorkerContextClass).  Developers can implement any 
behavior they want.  I believe the only reason to bypass was as a 
performance optimization.

Avery

On 2/3/12 8:34 AM, Claudio Martella wrote:
> Agreed, probably making the path configurable is the way to go.
>
> On Fri, Feb 3, 2012 at 5:30 PM, David Garcia<dg...@potomacfusion.com>  wrote:
>> I just wanted to send this out because I remember reading a discussion on
>> this topic.  Currently, graph will create a vertex in the graph if a
>> message is sent to a vertexID that doesn't exist.  Personally, I really
>> really like this behavior.  It enables me to forgo vertex creation if I
>> don't need it.  If I need the vertex, I can simply send a message to
>> create it, and process the message that was sent.  I understand that there
>> are some concerns with this. . .I would suggest making this behavior
>> configurable at job creation.  This would be an awesome compromise, and
>> would not preclude either type of behavior.
>>
>> -David
>>
>
>

Re: creating non existing vertices by sending messages

[Claudio Martella <cl...@gmail.com>]

Agreed, probably making the path configurable is the way to go.

On Fri, Feb 3, 2012 at 5:30 PM, David Garcia <dg...@potomacfusion.com> wrote:
> I just wanted to send this out because I remember reading a discussion on
> this topic.  Currently, graph will create a vertex in the graph if a
> message is sent to a vertexID that doesn't exist.  Personally, I really
> really like this behavior.  It enables me to forgo vertex creation if I
> don't need it.  If I need the vertex, I can simply send a message to
> create it, and process the message that was sent.  I understand that there
> are some concerns with this. . .I would suggest making this behavior
> configurable at job creation.  This would be an awesome compromise, and
> would not preclude either type of behavior.
>
> -David
>



-- 
   Claudio Martella
   claudio.martella@gmail.com

Re: multi-graph support in giraph

[André Kelpe <ef...@googlemail.com>]

2012/2/3 Avery Ching <ac...@apache.org>:
> We can diverge from the Pregel API as long as we have a good reason for it.
>  I do agree that while we can support multi-graphs with a user-chosen edge
> type, some built-in support that makes programming easier sounds like a good
> goal.  Andre or Claudio, feel free to open a JIRA to discuss this.
>
> We should also figure out the appropriate APIs as well that make it the most
> convenient to use.

I created https://issues.apache.org/jira/browse/GIRAPH-141 for this.

André

Re: multi-graph support in giraph

[Avery Ching <ac...@apache.org>]

We can diverge from the Pregel API as long as we have a good reason for 
it.  I do agree that while we can support multi-graphs with a 
user-chosen edge type, some built-in support that makes programming 
easier sounds like a good goal.  Andre or Claudio, feel free to open a 
JIRA to discuss this.

We should also figure out the appropriate APIs as well that make it the 
most convenient to use.

Avery

On 2/3/12 9:14 AM, Claudio Martella wrote:
> On Fri, Feb 3, 2012 at 6:07 PM, André Kelpe
> <ef...@googlemail.com>  wrote:
>> 2012/2/3 Claudio Martella<cl...@gmail.com>:
>>> Hi Andre,
>> Hi!
>>
>>> As I see it, we'd basically have to move all the API about edges from
>>> single object to Iterable (i.e. returning multiple edges for a given
>>> vertex endpoint as you suggested), and maybe also returning multiple
>>> vertices for a given edge(label).
>> If the goal of giraph is to be close to the pregel paper, then that
>> kind of API makes
>> more sense.
>  From how I see it, we've already taken a distance from Pregel in many
> API decisions. Personally I believe we don't have to stick to Pregel,
> we definitely have just to design Giraph for it's useful. For what we
> know, the API of the paper could be just the smallest subset of the
> real Pregel API that could fit clearly into the paper.
>
>
>> I am going to look into your code and see if I can
>> integrated it in the
>> copy of giraph I use internally here right now.
> Be ware that the code is not meant for general purpose but for a
> specific task. The "extended" api methods though should be quite
> general.
>
>>> The single-graph, as it's implemented now compared to multi-graph,
>>> would be a subcase of this which internally it would return
>>> getEdgeValue().iterator().next().
>> That would mean, you'd have two different kinds of vertex, one
>> compatible with single-graphs
>> and one with multi-graphs. Sounds tricky to maintain on the long run,
>> but could be an idea.
> I see the single-graph vertex as a subclass of the multi-graph vertex,
> something along with what's already going on with mutablevertex, so i
> don't see a problem in maintaining it.
>
>> André (@fs111)
>
>

Re: multi-graph support in giraph

[Claudio Martella <cl...@gmail.com>]

On Fri, Feb 3, 2012 at 6:07 PM, André Kelpe
<ef...@googlemail.com> wrote:
> 2012/2/3 Claudio Martella <cl...@gmail.com>:
>> Hi Andre,
>
> Hi!
>
>> As I see it, we'd basically have to move all the API about edges from
>> single object to Iterable (i.e. returning multiple edges for a given
>> vertex endpoint as you suggested), and maybe also returning multiple
>> vertices for a given edge(label).
>
> If the goal of giraph is to be close to the pregel paper, then that
> kind of API makes
> more sense.

>From how I see it, we've already taken a distance from Pregel in many
API decisions. Personally I believe we don't have to stick to Pregel,
we definitely have just to design Giraph for it's useful. For what we
know, the API of the paper could be just the smallest subset of the
real Pregel API that could fit clearly into the paper.


> I am going to look into your code and see if I can
> integrated it in the
> copy of giraph I use internally here right now.

Be ware that the code is not meant for general purpose but for a
specific task. The "extended" api methods though should be quite
general.

>
>> The single-graph, as it's implemented now compared to multi-graph,
>> would be a subcase of this which internally it would return
>> getEdgeValue().iterator().next().
>
> That would mean, you'd have two different kinds of vertex, one
> compatible with single-graphs
> and one with multi-graphs. Sounds tricky to maintain on the long run,
> but could be an idea.

I see the single-graph vertex as a subclass of the multi-graph vertex,
something along with what's already going on with mutablevertex, so i
don't see a problem in maintaining it.

>
> André (@fs111)



-- 
   Claudio Martella
   claudio.martella@gmail.com

Re: multi-graph support in giraph

[André Kelpe <ef...@googlemail.com>]

2012/2/3 Claudio Martella <cl...@gmail.com>:
> Hi Andre,

Hi!

> As I see it, we'd basically have to move all the API about edges from
> single object to Iterable (i.e. returning multiple edges for a given
> vertex endpoint as you suggested), and maybe also returning multiple
> vertices for a given edge(label).

If the goal of giraph is to be close to the pregel paper, then that
kind of API makes
more sense. I am going to look into your code and see if I can
integrated it in the
copy of giraph I use internally here right now.

> The single-graph, as it's implemented now compared to multi-graph,
> would be a subcase of this which internally it would return
> getEdgeValue().iterator().next().

That would mean, you'd have two different kinds of vertex, one
compatible with single-graphs
and one with multi-graphs. Sounds tricky to maintain on the long run,
but could be an idea.

André (@fs111)

Re: multi-graph support in giraph

[Owen O'Malley <om...@apache.org>]

I've certainly had multi-graph use cases in the past. I think such an
extension would be generally useful.

-- Owen

creating non existing vertices by sending messages

[David Garcia <dg...@potomacfusion.com>]

I just wanted to send this out because I remember reading a discussion on
this topic.  Currently, graph will create a vertex in the graph if a
message is sent to a vertexID that doesn't exist.  Personally, I really
really like this behavior.  It enables me to forgo vertex creation if I
don't need it.  If I need the vertex, I can simply send a message to
create it, and process the message that was sent.  I understand that there
are some concerns with this. . .I would suggest making this behavior
configurable at job creation.  This would be an awesome compromise, and
would not preclude either type of behavior.

-David

Re: multi-graph support in giraph

[Claudio Martella <cl...@gmail.com>]

Hi Andre,

I'd be also very interested in the type of extension you're proposing.
As a matter of fact I ended up implementing that kind of vertex by
myself,
you can have an example here:
https://github.com/claudiomartella/graffiti/blob/master/src/main/java/org/acaro/graffiti/processing/Vertex.java

As you can see I end up breaking most of the API adding my own
multigraph API internally.

As I see it, we'd basically have to move all the API about edges from
single object to Iterable (i.e. returning multiple edges for a given
vertex endpoint as you suggested), and maybe also returning multiple
vertices for a given edge(label).

The single-graph, as it's implemented now compared to multi-graph,
would be a subcase of this which internally it would return
getEdgeValue().iterator().next().

I'd be +1 for such an extension.

On Fri, Feb 3, 2012 at 10:44 AM, André Kelpe
<ef...@googlemail.com> wrote:
> Hi list,
>
> in my current usage of giraph I ran into the limitation that the API is centered
> around simple graphs but in many applications you are actually dealing with
> multi-graphs. One simple example is a road network, where there can be n edges
> between 2 vertices. For my current program I could work around the "limitation"
> by using an ArrayWritable as the edge value, which contains all edges that are
> connectors to a neighbour vertex. That is however not the cleanest of all
> approaches.
>
> The pregel paper describes an API, where you work with iterators to all your
> outgoing edges and you then can access the vertex on the other end with a method
> call (see the impl of Shortest Path in the paper). That kind of API would
> totally allow having multiple edges connecting the same two vertices directly
> while the current API with getEdgeValue(vertexId) does not. What is the current
> view on this, is that a feature, that would be welcome? Should I open a JIRA
> for the discussion? Am I overlooking something?
>
> Thanks!
>
> André



-- 
   Claudio Martella
   claudio.martella@gmail.com