Graph traversing example

[Flavio Pompermaier]

Hi all,

I have problems in figuring out how to solve the following use case.

I have a set of Tuple3 like:

A, type, t1

A, hasStatus, B

B, type, t2 

B, atTime1, C

B, atTime2, D

C, type, t3

C, name, c

D, type, t3

D, name, d

D, someAttr, d

Now I want to be able to find whether exists a path for A->(? type==t3) and, if true, attach them to A group. In this case it should output something like:

GROUP_KEY, TUPLES

A,                    [type, t1] [type3, (C,[type, t3],[name, c]), (D, [type, t3],[name, d] [someAttr, d])]

B,                    [type, t1] [atTime1, C] [atTime2, D]

C,                    [type, t3] [name, c]

D,                    [type, t3] [name, d] [someAttr, d]

Is there any example that does something similar?

Thanks in advance,

Flavio

[Stephan Ewen]

This looks like a "transitive closure" or "reachability" style problem, you can probably model it similar to that.

Have a look at the examples, there is "ConnectedComponents" and "TransitiveClosure". You can start from there...

On Wed, Nov 26, 2014 at 10:32 AM, Flavio Pompermaier <[hidden email]> wrote:

Hi all,

I have problems in figuring out how to solve the following use case.

I have a set of Tuple3 like:

A, type, t1

A, hasStatus, B

B, type, t2 

B, atTime1, C

B, atTime2, D

C, type, t3

C, name, c

D, type, t3

D, name, d

D, someAttr, d

Now I want to be able to find whether exists a path for A->(? type==t3) and, if true, attach them to A group. In this case it should output something like:

GROUP_KEY, TUPLES

A,                    [type, t1] [type3, (C,[type, t3],[name, c]), (D, [type, t3],[name, d] [someAttr, d])]

B,                    [type, t1] [atTime1, C] [atTime2, D]

C,                    [type, t3] [name, c]

D,                    [type, t3] [name, d] [someAttr, d]

Is there any example that does something similar?

Thanks in advance,

Flavio

[Flavio Pompermaier]

Ok thanks Stephen, I'll start from there!

On Nov 26, 2014 1:07 PM, "Stephan Ewen" <[hidden email]> wrote:

This looks like a "transitive closure" or "reachability" style problem, you can probably model it similar to that.

Have a look at the examples, there is "ConnectedComponents" and "TransitiveClosure". You can start from there...

On Wed, Nov 26, 2014 at 10:32 AM, Flavio Pompermaier <[hidden email]> wrote:

Hi all,

I have problems in figuring out how to solve the following use case.

I have a set of Tuple3 like:

A, type, t1

A, hasStatus, B

B, type, t2 

B, atTime1, C

B, atTime2, D

C, type, t3

C, name, c

D, type, t3

D, name, d

D, someAttr, d

Now I want to be able to find whether exists a path for A->(? type==t3) and, if true, attach them to A group. In this case it should output something like:

GROUP_KEY, TUPLES

A,                    [type, t1] [type3, (C,[type, t3],[name, c]), (D, [type, t3],[name, d] [someAttr, d])]

B,                    [type, t1] [atTime1, C] [atTime2, D]

C,                    [type, t3] [name, c]

D,                    [type, t3] [name, d] [someAttr, d]

Is there any example that does something similar?

Thanks in advance,

Flavio