You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@flink.apache.org by Flavio Pompermaier <po...@okkam.it> on 2014/11/26 10:32:03 UTC

Graph traversing example

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

Re: Graph traversing example

Posted by Flavio Pompermaier <po...@okkam.it>.
Ok thanks Stephen, I'll start from there!
On Nov 26, 2014 1:07 PM, "Stephan Ewen" <se...@apache.org> 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 <pompermaier@okkam.it
> > 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
>>
>
>

Re: Graph traversing example

Posted by Stephan Ewen <se...@apache.org>.
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 <po...@okkam.it>
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
>