You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@giraph.apache.org by Jyoti Yadav <ra...@gmail.com> on 2013/10/15 11:20:35 UTC
changes in SingleSourceShortestPath example
Hi..
If I want to run SingleSourceShortest Path example given in Giraph for all
the vertices ,then what changes I need to introduce and how ??
How master node will come to know that algorithm has successfully completed
for one vertex and it has to consider other vertex and reinitialize the
vertex values ..
Any ideas are really appreciated....
Jyoti Yadav
Re: changes in SingleSourceShortestPath example
Posted by Jyoti Yadav <ra...@gmail.com>.
Thanks Sebastian for your reply..
Would you please help me a little more??
Suppose in my algorithm,there are two parts.After all vertices have
executed first part,they need to execute other part. Is it possible??
On Wed, Oct 16, 2013 at 9:32 AM, Sebastian Schelter <ss...@apache.org> wrote:
> Hi Jyoti,
>
> you can send any kind of message you want, as you can implement
> arbitrary custom datatypes.
>
> Best,
> Sebastian
>
>
> On 16.10.2013 18:30, Jyoti Yadav wrote:
> > Hi..
> > I have one query in my mind.Which type of message we can send among
> > vertices?? Can we send String message or String+int ?? Is such
> combinations
> > are posssible?
> >
> > Any suggestions are highly appreciated...
> >
> > Regards
> > Jyoti
> >
> >
> > On Wed, Oct 16, 2013 at 6:06 AM, Claudio Martella <
> > claudio.martella@gmail.com> wrote:
> >
> >> I think a parallel BFS from all the sources is out of any possibility.
> One
> >> thing one can do is do it in parallel from k sources, maybe N times
> (with
> >> different sources each, of course), and approximate centrality from
> these
> >> trees.
> >>
> >>
> >> On Wed, Oct 16, 2013 at 8:44 AM, Silvio Di gregorio <
> >> silvio.digregorio@gmail.com> wrote:
> >>
> >>> I'm also trying to implement but with poor results. my target is the
> >>> betweenness Centrality.
> >>> The only thing that i did is generate giraph code throught Green-Marl,
> >>> but this is very far from being a running code.
> >>> Update us if there are progress.
> >>> But if complexity is quadratic in the of space it's hard to do.
> >>>
> >>>
> >>> 2013/10/16 Jyoti Yadav <ra...@gmail.com>
> >>>
> >>>> Hi Silvio..
> >>>> Thanks for your reply...
> >>>> Yes, I want to realize All-source- shortest -path..Would you please
> >>>> help me out.?
> >>>>
> >>>>
> >>>>
> >>>>
> >>>> On Tue, Oct 15, 2013 at 12:45 PM, Silvio Di gregorio <
> >>>> silvio.digregorio@gmail.com> wrote:
> >>>>
> >>>>> Do you want realize all-source-shortest path?
> >>>>> Il giorno 15/ott/2013 11:21, "Jyoti Yadav" <
> rao.jyoti26yadav@gmail.com>
> >>>>> ha scritto:
> >>>>>
> >>>>> Hi..
> >>>>>> If I want to run SingleSourceShortest Path example given in Giraph
> >>>>>> for all the vertices ,then what changes I need to introduce and how
> ??
> >>>>>> How master node will come to know that algorithm has successfully
> >>>>>> completed for one vertex and it has to consider other vertex and
> >>>>>> reinitialize the vertex values ..
> >>>>>>
> >>>>>> Any ideas are really appreciated....
> >>>>>>
> >>>>>> Jyoti Yadav
> >>>>>>
> >>>>>
> >>>>
> >>>
> >>
> >>
> >> --
> >> Claudio Martella
> >> claudio.martella@gmail.com
> >>
> >
>
>
Re: changes in SingleSourceShortestPath example
Posted by Sebastian Schelter <ss...@apache.org>.
Hi Jyoti,
you can send any kind of message you want, as you can implement
arbitrary custom datatypes.
Best,
Sebastian
On 16.10.2013 18:30, Jyoti Yadav wrote:
> Hi..
> I have one query in my mind.Which type of message we can send among
> vertices?? Can we send String message or String+int ?? Is such combinations
> are posssible?
>
> Any suggestions are highly appreciated...
>
> Regards
> Jyoti
>
>
> On Wed, Oct 16, 2013 at 6:06 AM, Claudio Martella <
> claudio.martella@gmail.com> wrote:
>
>> I think a parallel BFS from all the sources is out of any possibility. One
>> thing one can do is do it in parallel from k sources, maybe N times (with
>> different sources each, of course), and approximate centrality from these
>> trees.
>>
>>
>> On Wed, Oct 16, 2013 at 8:44 AM, Silvio Di gregorio <
>> silvio.digregorio@gmail.com> wrote:
>>
>>> I'm also trying to implement but with poor results. my target is the
>>> betweenness Centrality.
>>> The only thing that i did is generate giraph code throught Green-Marl,
>>> but this is very far from being a running code.
>>> Update us if there are progress.
>>> But if complexity is quadratic in the of space it's hard to do.
>>>
>>>
>>> 2013/10/16 Jyoti Yadav <ra...@gmail.com>
>>>
>>>> Hi Silvio..
>>>> Thanks for your reply...
>>>> Yes, I want to realize All-source- shortest -path..Would you please
>>>> help me out.?
>>>>
>>>>
>>>>
>>>>
>>>> On Tue, Oct 15, 2013 at 12:45 PM, Silvio Di gregorio <
>>>> silvio.digregorio@gmail.com> wrote:
>>>>
>>>>> Do you want realize all-source-shortest path?
>>>>> Il giorno 15/ott/2013 11:21, "Jyoti Yadav" <ra...@gmail.com>
>>>>> ha scritto:
>>>>>
>>>>> Hi..
>>>>>> If I want to run SingleSourceShortest Path example given in Giraph
>>>>>> for all the vertices ,then what changes I need to introduce and how ??
>>>>>> How master node will come to know that algorithm has successfully
>>>>>> completed for one vertex and it has to consider other vertex and
>>>>>> reinitialize the vertex values ..
>>>>>>
>>>>>> Any ideas are really appreciated....
>>>>>>
>>>>>> Jyoti Yadav
>>>>>>
>>>>>
>>>>
>>>
>>
>>
>> --
>> Claudio Martella
>> claudio.martella@gmail.com
>>
>
Re: changes in SingleSourceShortestPath example
Posted by Jyoti Yadav <ra...@gmail.com>.
Hi..
I have one query in my mind.Which type of message we can send among
vertices?? Can we send String message or String+int ?? Is such combinations
are posssible?
Any suggestions are highly appreciated...
Regards
Jyoti
On Wed, Oct 16, 2013 at 6:06 AM, Claudio Martella <
claudio.martella@gmail.com> wrote:
> I think a parallel BFS from all the sources is out of any possibility. One
> thing one can do is do it in parallel from k sources, maybe N times (with
> different sources each, of course), and approximate centrality from these
> trees.
>
>
> On Wed, Oct 16, 2013 at 8:44 AM, Silvio Di gregorio <
> silvio.digregorio@gmail.com> wrote:
>
>> I'm also trying to implement but with poor results. my target is the
>> betweenness Centrality.
>> The only thing that i did is generate giraph code throught Green-Marl,
>> but this is very far from being a running code.
>> Update us if there are progress.
>> But if complexity is quadratic in the of space it's hard to do.
>>
>>
>> 2013/10/16 Jyoti Yadav <ra...@gmail.com>
>>
>>> Hi Silvio..
>>> Thanks for your reply...
>>> Yes, I want to realize All-source- shortest -path..Would you please
>>> help me out.?
>>>
>>>
>>>
>>>
>>> On Tue, Oct 15, 2013 at 12:45 PM, Silvio Di gregorio <
>>> silvio.digregorio@gmail.com> wrote:
>>>
>>>> Do you want realize all-source-shortest path?
>>>> Il giorno 15/ott/2013 11:21, "Jyoti Yadav" <ra...@gmail.com>
>>>> ha scritto:
>>>>
>>>> Hi..
>>>>> If I want to run SingleSourceShortest Path example given in Giraph
>>>>> for all the vertices ,then what changes I need to introduce and how ??
>>>>> How master node will come to know that algorithm has successfully
>>>>> completed for one vertex and it has to consider other vertex and
>>>>> reinitialize the vertex values ..
>>>>>
>>>>> Any ideas are really appreciated....
>>>>>
>>>>> Jyoti Yadav
>>>>>
>>>>
>>>
>>
>
>
> --
> Claudio Martella
> claudio.martella@gmail.com
>
Re: changes in SingleSourceShortestPath example
Posted by Claudio Martella <cl...@gmail.com>.
I think a parallel BFS from all the sources is out of any possibility. One
thing one can do is do it in parallel from k sources, maybe N times (with
different sources each, of course), and approximate centrality from these
trees.
On Wed, Oct 16, 2013 at 8:44 AM, Silvio Di gregorio <
silvio.digregorio@gmail.com> wrote:
> I'm also trying to implement but with poor results. my target is the
> betweenness Centrality.
> The only thing that i did is generate giraph code throught Green-Marl, but
> this is very far from being a running code.
> Update us if there are progress.
> But if complexity is quadratic in the of space it's hard to do.
>
>
> 2013/10/16 Jyoti Yadav <ra...@gmail.com>
>
>> Hi Silvio..
>> Thanks for your reply...
>> Yes, I want to realize All-source- shortest -path..Would you please
>> help me out.?
>>
>>
>>
>>
>> On Tue, Oct 15, 2013 at 12:45 PM, Silvio Di gregorio <
>> silvio.digregorio@gmail.com> wrote:
>>
>>> Do you want realize all-source-shortest path?
>>> Il giorno 15/ott/2013 11:21, "Jyoti Yadav" <ra...@gmail.com>
>>> ha scritto:
>>>
>>> Hi..
>>>> If I want to run SingleSourceShortest Path example given in Giraph for
>>>> all the vertices ,then what changes I need to introduce and how ??
>>>> How master node will come to know that algorithm has successfully
>>>> completed for one vertex and it has to consider other vertex and
>>>> reinitialize the vertex values ..
>>>>
>>>> Any ideas are really appreciated....
>>>>
>>>> Jyoti Yadav
>>>>
>>>
>>
>
--
Claudio Martella
claudio.martella@gmail.com
Re: changes in SingleSourceShortestPath example
Posted by Silvio Di gregorio <si...@gmail.com>.
Hi Sebastian,
I read the article, it's very hard, at least for me, to implement the
pseudo-code algorithms of Effective Closeness and LineRank.
Do You Know any implementations in Apache Hadoop (MapReduce) or in Apache
Giraph?
2013/10/16 Silvio Di gregorio <si...@gmail.com>
> thank you very much Sebastian
>
>
> 2013/10/16 Sebastian Schelter <ss...@apache.org>
>
>> Hi,
>>
>> If you're interested in betweeness centrality, I suggest you have a look
>> at this paper [1] which proposes an algorithm called LineRank as
>> scalable substitute for betweeness centrality.
>>
>> Best,
>> Sebastian
>>
>> [1] http://www.cs.cmu.edu/~ukang/papers/CentralitySDM2011.pdf
>>
>>
>> On 16.10.2013 08:44, Silvio Di gregorio wrote:
>> > I'm also trying to implement but with poor results. my target is the
>> > betweenness Centrality.
>> > The only thing that i did is generate giraph code throught Green-Marl,
>> but
>> > this is very far from being a running code.
>> > Update us if there are progress.
>> > But if complexity is quadratic in the of space it's hard to do.
>> >
>> >
>> > 2013/10/16 Jyoti Yadav <ra...@gmail.com>
>> >
>> >> Hi Silvio..
>> >> Thanks for your reply...
>> >> Yes, I want to realize All-source- shortest -path..Would you please
>> help
>> >> me out.?
>> >>
>> >>
>> >>
>> >>
>> >> On Tue, Oct 15, 2013 at 12:45 PM, Silvio Di gregorio <
>> >> silvio.digregorio@gmail.com> wrote:
>> >>
>> >>> Do you want realize all-source-shortest path?
>> >>> Il giorno 15/ott/2013 11:21, "Jyoti Yadav" <
>> rao.jyoti26yadav@gmail.com>
>> >>> ha scritto:
>> >>>
>> >>> Hi..
>> >>>> If I want to run SingleSourceShortest Path example given in Giraph
>> for
>> >>>> all the vertices ,then what changes I need to introduce and how ??
>> >>>> How master node will come to know that algorithm has successfully
>> >>>> completed for one vertex and it has to consider other vertex and
>> >>>> reinitialize the vertex values ..
>> >>>>
>> >>>> Any ideas are really appreciated....
>> >>>>
>> >>>> Jyoti Yadav
>> >>>>
>> >>>
>> >>
>> >
>>
>>
>
Re: changes in SingleSourceShortestPath example
Posted by Silvio Di gregorio <si...@gmail.com>.
thank you very much Sebastian
2013/10/16 Sebastian Schelter <ss...@apache.org>
> Hi,
>
> If you're interested in betweeness centrality, I suggest you have a look
> at this paper [1] which proposes an algorithm called LineRank as
> scalable substitute for betweeness centrality.
>
> Best,
> Sebastian
>
> [1] http://www.cs.cmu.edu/~ukang/papers/CentralitySDM2011.pdf
>
>
> On 16.10.2013 08:44, Silvio Di gregorio wrote:
> > I'm also trying to implement but with poor results. my target is the
> > betweenness Centrality.
> > The only thing that i did is generate giraph code throught Green-Marl,
> but
> > this is very far from being a running code.
> > Update us if there are progress.
> > But if complexity is quadratic in the of space it's hard to do.
> >
> >
> > 2013/10/16 Jyoti Yadav <ra...@gmail.com>
> >
> >> Hi Silvio..
> >> Thanks for your reply...
> >> Yes, I want to realize All-source- shortest -path..Would you please
> help
> >> me out.?
> >>
> >>
> >>
> >>
> >> On Tue, Oct 15, 2013 at 12:45 PM, Silvio Di gregorio <
> >> silvio.digregorio@gmail.com> wrote:
> >>
> >>> Do you want realize all-source-shortest path?
> >>> Il giorno 15/ott/2013 11:21, "Jyoti Yadav" <rao.jyoti26yadav@gmail.com
> >
> >>> ha scritto:
> >>>
> >>> Hi..
> >>>> If I want to run SingleSourceShortest Path example given in Giraph
> for
> >>>> all the vertices ,then what changes I need to introduce and how ??
> >>>> How master node will come to know that algorithm has successfully
> >>>> completed for one vertex and it has to consider other vertex and
> >>>> reinitialize the vertex values ..
> >>>>
> >>>> Any ideas are really appreciated....
> >>>>
> >>>> Jyoti Yadav
> >>>>
> >>>
> >>
> >
>
>
Re: changes in SingleSourceShortestPath example
Posted by Sebastian Schelter <ss...@apache.org>.
Hi,
If you're interested in betweeness centrality, I suggest you have a look
at this paper [1] which proposes an algorithm called LineRank as
scalable substitute for betweeness centrality.
Best,
Sebastian
[1] http://www.cs.cmu.edu/~ukang/papers/CentralitySDM2011.pdf
On 16.10.2013 08:44, Silvio Di gregorio wrote:
> I'm also trying to implement but with poor results. my target is the
> betweenness Centrality.
> The only thing that i did is generate giraph code throught Green-Marl, but
> this is very far from being a running code.
> Update us if there are progress.
> But if complexity is quadratic in the of space it's hard to do.
>
>
> 2013/10/16 Jyoti Yadav <ra...@gmail.com>
>
>> Hi Silvio..
>> Thanks for your reply...
>> Yes, I want to realize All-source- shortest -path..Would you please help
>> me out.?
>>
>>
>>
>>
>> On Tue, Oct 15, 2013 at 12:45 PM, Silvio Di gregorio <
>> silvio.digregorio@gmail.com> wrote:
>>
>>> Do you want realize all-source-shortest path?
>>> Il giorno 15/ott/2013 11:21, "Jyoti Yadav" <ra...@gmail.com>
>>> ha scritto:
>>>
>>> Hi..
>>>> If I want to run SingleSourceShortest Path example given in Giraph for
>>>> all the vertices ,then what changes I need to introduce and how ??
>>>> How master node will come to know that algorithm has successfully
>>>> completed for one vertex and it has to consider other vertex and
>>>> reinitialize the vertex values ..
>>>>
>>>> Any ideas are really appreciated....
>>>>
>>>> Jyoti Yadav
>>>>
>>>
>>
>
Re: changes in SingleSourceShortestPath example
Posted by Silvio Di gregorio <si...@gmail.com>.
I'm also trying to implement but with poor results. my target is the
betweenness Centrality.
The only thing that i did is generate giraph code throught Green-Marl, but
this is very far from being a running code.
Update us if there are progress.
But if complexity is quadratic in the of space it's hard to do.
2013/10/16 Jyoti Yadav <ra...@gmail.com>
> Hi Silvio..
> Thanks for your reply...
> Yes, I want to realize All-source- shortest -path..Would you please help
> me out.?
>
>
>
>
> On Tue, Oct 15, 2013 at 12:45 PM, Silvio Di gregorio <
> silvio.digregorio@gmail.com> wrote:
>
>> Do you want realize all-source-shortest path?
>> Il giorno 15/ott/2013 11:21, "Jyoti Yadav" <ra...@gmail.com>
>> ha scritto:
>>
>> Hi..
>>> If I want to run SingleSourceShortest Path example given in Giraph for
>>> all the vertices ,then what changes I need to introduce and how ??
>>> How master node will come to know that algorithm has successfully
>>> completed for one vertex and it has to consider other vertex and
>>> reinitialize the vertex values ..
>>>
>>> Any ideas are really appreciated....
>>>
>>> Jyoti Yadav
>>>
>>
>
Re: changes in SingleSourceShortestPath example
Posted by Jyoti Yadav <ra...@gmail.com>.
Hi Silvio..
Thanks for your reply...
Yes, I want to realize All-source- shortest -path..Would you please help
me out.?
On Tue, Oct 15, 2013 at 12:45 PM, Silvio Di gregorio <
silvio.digregorio@gmail.com> wrote:
> Do you want realize all-source-shortest path?
> Il giorno 15/ott/2013 11:21, "Jyoti Yadav" <ra...@gmail.com>
> ha scritto:
>
> Hi..
>> If I want to run SingleSourceShortest Path example given in Giraph for
>> all the vertices ,then what changes I need to introduce and how ??
>> How master node will come to know that algorithm has successfully
>> completed for one vertex and it has to consider other vertex and
>> reinitialize the vertex values ..
>>
>> Any ideas are really appreciated....
>>
>> Jyoti Yadav
>>
>
Re: changes in SingleSourceShortestPath example
Posted by Silvio Di gregorio <si...@gmail.com>.
Do you want realize all-source-shortest path?
Il giorno 15/ott/2013 11:21, "Jyoti Yadav" <ra...@gmail.com> ha
scritto:
> Hi..
> If I want to run SingleSourceShortest Path example given in Giraph for
> all the vertices ,then what changes I need to introduce and how ??
> How master node will come to know that algorithm has successfully
> completed for one vertex and it has to consider other vertex and
> reinitialize the vertex values ..
>
> Any ideas are really appreciated....
>
> Jyoti Yadav
>