You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@giraph.apache.org by Rana Althunyan <ra...@gmail.com> on 2014/03/21 22:47:16 UTC
push-relabel flow algorithm
Hello experts,
I really need your help. I am new to Giraph. I have project on pregel paper, and I need to implement One algorithm via Apache Giraph.The algorithm is push-relabel flow algorithm. Actually when I started to adapt the algorithm to fit to Giraph I found some problems. I will list them.
1- Because any type of data structure are not allowed in Giraph how can I store excess flow and distance value for each vertex.
2- When the excess value becomes zero for any vertex, I wanna keep vertex flow during future supersteps even if the vertex received messages.
3- The last point, when I want to send a flow to a vertex, i need store two values of residual graph the remaining value from the edge capacity and the amount of flow that we use so far. How can I do that. How can I keep these two values for each vertex in the graph.
these following questions may are easy for you ..
4- How can I determine the last vertex as a sink.
5- How can I get the number of all vertexes from the input file .
I know I have written many question.I searched a lot in the Internet, but I did not find any discussion regards to this algorithm
sorry and thank you.I appreciate any help or recommendations
Rana
Re: push-relabel flow algorithm
Posted by Rana Althunyan <ra...@gmail.com>.
Hey,
yah yah I got your point. Thank you so so much for your super help.
I will come her and show you my work if I succeed .
Thank you again
On Mar 25, 2014, at 1:12 PM, Pascal Jäger <pa...@pascaljaeger.de> wrote:
> Hey,
>
> I think you can do both.
> you can encode and decode your values to a json formatted text every time you write them to or read them from your value classes.
> I personally added some logic to my VertexValue, thus I don’t encode my data.
>
> So for the latter you will need to write custom input formats because you now need to create an instance of your edge and/or vertex value class.
> The input format is the place where you can do this.
>
> Take the LongLongNullTextInputFormat in giraph.io.formats.
> Replace the NullWritable with you custom EdgeValue and adjust the
> protected Iterable<Edge<LongWritable, NullWritable>> getEdges(String[] tokens)
>
> to
>
> protected Iterable<Edge<LongWritable, CustomEdgeValue>> getEdges(String[] tokens)
>
> and change the body to create you your custom value.
>
> You can also look at the Okapi Files. They also provide nice implementations:
> http://grafos.ml or
> https://github.com/grafos-ml/okapi
>
> Hope that helps
>
> Pascal
>
> Am 25.03.2014 um 17:28 schrieb Rana Althunyan <ra...@gmail.com>:
>
>> Hi again Pascal
>> That is realy very helpful. I don’t know how can I thank you.
>>
>> I have another question, do I need to create a new custom input format? I do not think so.
>> I can use jason format because the other edge values i will set them in compute function. do you agree with me.
>>
>> Thank you so so much
>> Rana
>> On Mar 25, 2014, at 2:42 AM, Pascal Jäger <pa...@pascaljaeger.de> wrote:
>>
>>> Hi Rana,
>>>
>>> all you need to do is writing your own EdgeValue and VertexValue class by implementing the Writable Interface.
>>> You can use any field you like. Just make sure you write or read them in the Writeable methods.
>>>
>>> Here’s VertexValue I use (There may be better ways for writing list, but it works just fine)
>>>
>>> http://pastebin.com/VpMVFuuc
>>>
>>> In your compute method get the VertexValue with vertex.getValue() and apply your changes. That’s it.
>>> Whatever you write into it in step one, you will be able to read or modify in step two.
>>>
>>> Regards
>>>
>>> Pascal
>>>
>>>
>>> Am 25.03.2014 um 07:14 schrieb Rana Althunyan <ra...@gmail.com>:
>>>
>>>> Hello Pankaj Malhotra,
>>>>
>>>> Yes, I need to assign more than values to the edge. I need the edge has [flow, capacity, distinction, source]
>>>> You says I need to create a new class type for edge, How can I pass it to json class and how can I make json class read my new edge object.
>>>>
>>>> I need to submit my code next week, so any answer or recommendation will definitely help.
>>>>
>>>> thanks
>>>> Rana
>>>>
>>>> On Mar 24, 2014, at 7:29 AM, Pankaj Malhotra <pa...@gmail.com> wrote:
>>>>
>>>>> If I get your point-1 right, you want to have a vertex class type other than the ones available, for example: Text. If this is what you want, you can have a class having as many fields as you want. Then convert the objects of that class to Json objects using Gson for example. Then, you can use the Json string to set the fields of the Text class.
>>>>>
>>>>>
>>>>> On 22 March 2014 04:50, Rana Althunyan <ra...@gmail.com> wrote:
>>>>> Hello experts,
>>>>> > I really need your help. I am new to Giraph. I have project on pregel paper, and I need to implement One algorithm via Apache Giraph.The algorithm is push-relabel flow algorithm. Actually when I started to adapt the algorithm to fit to Giraph I found some problems. I will list them.
>>>>> >
>>>>> > 1- Because any type of data structure are not allowed in Giraph how can I store excess flow and distance value for each vertex.
>>>>> > 2- When the excess value becomes zero for any vertex, I wanna keep vertex flow during future supersteps even if the vertex received messages.
>>>>> > 3- The last point, when I want to send a flow to a vertex, i need store two values of residual graph the remaining value from the edge capacity and the amount of flow that we use so far. How can I do that. How can I keep these two values for each vertex in the graph.
>>>>> >
>>>>> > these following questions may are easy for you ..
>>>>> > 4- How can I determine the last vertex as a sink.
>>>>> > 5- How can I get the number of all vertexes from the input file .
>>>>> >
>>>>> > I know I have written many question.I searched a lot in the Internet, but I did not find any discussion regards to this algorithm
>>>>> >
>>>>> > sorry and thank you.I appreciate any help or recommendations
>>>>> > Rana
>>>>>
>>>>>
>>>>
>>>
>>
>
Re: push-relabel flow algorithm
Posted by Pascal Jäger <pa...@pascaljaeger.de>.
Hey,
I think you can do both.
you can encode and decode your values to a json formatted text every time you write them to or read them from your value classes.
I personally added some logic to my VertexValue, thus I don’t encode my data.
So for the latter you will need to write custom input formats because you now need to create an instance of your edge and/or vertex value class.
The input format is the place where you can do this.
Take the LongLongNullTextInputFormat in giraph.io.formats.
Replace the NullWritable with you custom EdgeValue and adjust the
protected Iterable<Edge<LongWritable, NullWritable>> getEdges(String[] tokens)
to
protected Iterable<Edge<LongWritable, CustomEdgeValue>> getEdges(String[] tokens)
and change the body to create you your custom value.
You can also look at the Okapi Files. They also provide nice implementations:
http://grafos.ml or
https://github.com/grafos-ml/okapi
Hope that helps
Pascal
Am 25.03.2014 um 17:28 schrieb Rana Althunyan <ra...@gmail.com>>:
Hi again Pascal
That is realy very helpful. I don’t know how can I thank you.
I have another question, do I need to create a new custom input format? I do not think so.
I can use jason format because the other edge values i will set them in compute function. do you agree with me.
Thank you so so much
Rana
On Mar 25, 2014, at 2:42 AM, Pascal Jäger <pa...@pascaljaeger.de>> wrote:
Hi Rana,
all you need to do is writing your own EdgeValue and VertexValue class by implementing the Writable Interface.
You can use any field you like. Just make sure you write or read them in the Writeable methods.
Here’s VertexValue I use (There may be better ways for writing list, but it works just fine)
http://pastebin.com/VpMVFuuc
In your compute method get the VertexValue with vertex.getValue() and apply your changes. That’s it.
Whatever you write into it in step one, you will be able to read or modify in step two.
Regards
Pascal
Am 25.03.2014 um 07:14 schrieb Rana Althunyan <ra...@gmail.com>>:
Hello Pankaj Malhotra,
Yes, I need to assign more than values to the edge. I need the edge has [flow, capacity, distinction, source]
You says I need to create a new class type for edge, How can I pass it to json class and how can I make json class read my new edge object.
I need to submit my code next week, so any answer or recommendation will definitely help.
thanks
Rana
On Mar 24, 2014, at 7:29 AM, Pankaj Malhotra <pa...@gmail.com>> wrote:
If I get your point-1 right, you want to have a vertex class type other than the ones available, for example: Text. If this is what you want, you can have a class having as many fields as you want. Then convert the objects of that class to Json objects using Gson for example. Then, you can use the Json string to set the fields of the Text class.
On 22 March 2014 04:50, Rana Althunyan <ra...@gmail.com>> wrote:
Hello experts,
> I really need your help. I am new to Giraph. I have project on pregel paper, and I need to implement One algorithm via Apache Giraph.The algorithm is push-relabel flow algorithm. Actually when I started to adapt the algorithm to fit to Giraph I found some problems. I will list them.
>
> 1- Because any type of data structure are not allowed in Giraph how can I store excess flow and distance value for each vertex.
> 2- When the excess value becomes zero for any vertex, I wanna keep vertex flow during future supersteps even if the vertex received messages.
> 3- The last point, when I want to send a flow to a vertex, i need store two values of residual graph the remaining value from the edge capacity and the amount of flow that we use so far. How can I do that. How can I keep these two values for each vertex in the graph.
>
> these following questions may are easy for you ..
> 4- How can I determine the last vertex as a sink.
> 5- How can I get the number of all vertexes from the input file .
>
> I know I have written many question.I searched a lot in the Internet, but I did not find any discussion regards to this algorithm
>
> sorry and thank you.I appreciate any help or recommendations
> Rana
Re: push-relabel flow algorithm
Posted by Rana Althunyan <ra...@gmail.com>.
Hi again Pascal
That is realy very helpful. I don’t know how can I thank you.
I have another question, do I need to create a new custom input format? I do not think so.
I can use jason format because the other edge values i will set them in compute function. do you agree with me.
Thank you so so much
Rana
On Mar 25, 2014, at 2:42 AM, Pascal Jäger <pa...@pascaljaeger.de> wrote:
> Hi Rana,
>
> all you need to do is writing your own EdgeValue and VertexValue class by implementing the Writable Interface.
> You can use any field you like. Just make sure you write or read them in the Writeable methods.
>
> Here’s VertexValue I use (There may be better ways for writing list, but it works just fine)
>
> http://pastebin.com/VpMVFuuc
>
> In your compute method get the VertexValue with vertex.getValue() and apply your changes. That’s it.
> Whatever you write into it in step one, you will be able to read or modify in step two.
>
> Regards
>
> Pascal
>
>
> Am 25.03.2014 um 07:14 schrieb Rana Althunyan <ra...@gmail.com>:
>
>> Hello Pankaj Malhotra,
>>
>> Yes, I need to assign more than values to the edge. I need the edge has [flow, capacity, distinction, source]
>> You says I need to create a new class type for edge, How can I pass it to json class and how can I make json class read my new edge object.
>>
>> I need to submit my code next week, so any answer or recommendation will definitely help.
>>
>> thanks
>> Rana
>>
>> On Mar 24, 2014, at 7:29 AM, Pankaj Malhotra <pa...@gmail.com> wrote:
>>
>>> If I get your point-1 right, you want to have a vertex class type other than the ones available, for example: Text. If this is what you want, you can have a class having as many fields as you want. Then convert the objects of that class to Json objects using Gson for example. Then, you can use the Json string to set the fields of the Text class.
>>>
>>>
>>> On 22 March 2014 04:50, Rana Althunyan <ra...@gmail.com> wrote:
>>> Hello experts,
>>> > I really need your help. I am new to Giraph. I have project on pregel paper, and I need to implement One algorithm via Apache Giraph.The algorithm is push-relabel flow algorithm. Actually when I started to adapt the algorithm to fit to Giraph I found some problems. I will list them.
>>> >
>>> > 1- Because any type of data structure are not allowed in Giraph how can I store excess flow and distance value for each vertex.
>>> > 2- When the excess value becomes zero for any vertex, I wanna keep vertex flow during future supersteps even if the vertex received messages.
>>> > 3- The last point, when I want to send a flow to a vertex, i need store two values of residual graph the remaining value from the edge capacity and the amount of flow that we use so far. How can I do that. How can I keep these two values for each vertex in the graph.
>>> >
>>> > these following questions may are easy for you ..
>>> > 4- How can I determine the last vertex as a sink.
>>> > 5- How can I get the number of all vertexes from the input file .
>>> >
>>> > I know I have written many question.I searched a lot in the Internet, but I did not find any discussion regards to this algorithm
>>> >
>>> > sorry and thank you.I appreciate any help or recommendations
>>> > Rana
>>>
>>>
>>
>
Re: push-relabel flow algorithm
Posted by Pascal Jäger <pa...@pascaljaeger.de>.
Hi Rana,
all you need to do is writing your own EdgeValue and VertexValue class by implementing the Writable Interface.
You can use any field you like. Just make sure you write or read them in the Writeable methods.
Here’s VertexValue I use (There may be better ways for writing list, but it works just fine)
http://pastebin.com/VpMVFuuc
In your compute method get the VertexValue with vertex.getValue() and apply your changes. That’s it.
Whatever you write into it in step one, you will be able to read or modify in step two.
Regards
Pascal
Am 25.03.2014 um 07:14 schrieb Rana Althunyan <ra...@gmail.com>>:
Hello Pankaj Malhotra,
Yes, I need to assign more than values to the edge. I need the edge has [flow, capacity, distinction, source]
You says I need to create a new class type for edge, How can I pass it to json class and how can I make json class read my new edge object.
I need to submit my code next week, so any answer or recommendation will definitely help.
thanks
Rana
On Mar 24, 2014, at 7:29 AM, Pankaj Malhotra <pa...@gmail.com>> wrote:
If I get your point-1 right, you want to have a vertex class type other than the ones available, for example: Text. If this is what you want, you can have a class having as many fields as you want. Then convert the objects of that class to Json objects using Gson for example. Then, you can use the Json string to set the fields of the Text class.
On 22 March 2014 04:50, Rana Althunyan <ra...@gmail.com>> wrote:
Hello experts,
> I really need your help. I am new to Giraph. I have project on pregel paper, and I need to implement One algorithm via Apache Giraph.The algorithm is push-relabel flow algorithm. Actually when I started to adapt the algorithm to fit to Giraph I found some problems. I will list them.
>
> 1- Because any type of data structure are not allowed in Giraph how can I store excess flow and distance value for each vertex.
> 2- When the excess value becomes zero for any vertex, I wanna keep vertex flow during future supersteps even if the vertex received messages.
> 3- The last point, when I want to send a flow to a vertex, i need store two values of residual graph the remaining value from the edge capacity and the amount of flow that we use so far. How can I do that. How can I keep these two values for each vertex in the graph.
>
> these following questions may are easy for you ..
> 4- How can I determine the last vertex as a sink.
> 5- How can I get the number of all vertexes from the input file .
>
> I know I have written many question.I searched a lot in the Internet, but I did not find any discussion regards to this algorithm
>
> sorry and thank you.I appreciate any help or recommendations
> Rana
Re: push-relabel flow algorithm
Posted by Rana Althunyan <ra...@gmail.com>.
Hello Pankaj Malhotra,
Yes, I need to assign more than values to the edge. I need the edge has [flow, capacity, distinction, source]
You says I need to create a new class type for edge, How can I pass it to json class and how can I make json class read my new edge object.
I need to submit my code next week, so any answer or recommendation will definitely help.
thanks
Rana
On Mar 24, 2014, at 7:29 AM, Pankaj Malhotra <pa...@gmail.com> wrote:
> If I get your point-1 right, you want to have a vertex class type other than the ones available, for example: Text. If this is what you want, you can have a class having as many fields as you want. Then convert the objects of that class to Json objects using Gson for example. Then, you can use the Json string to set the fields of the Text class.
>
>
> On 22 March 2014 04:50, Rana Althunyan <ra...@gmail.com> wrote:
> Hello experts,
> > I really need your help. I am new to Giraph. I have project on pregel paper, and I need to implement One algorithm via Apache Giraph.The algorithm is push-relabel flow algorithm. Actually when I started to adapt the algorithm to fit to Giraph I found some problems. I will list them.
> >
> > 1- Because any type of data structure are not allowed in Giraph how can I store excess flow and distance value for each vertex.
> > 2- When the excess value becomes zero for any vertex, I wanna keep vertex flow during future supersteps even if the vertex received messages.
> > 3- The last point, when I want to send a flow to a vertex, i need store two values of residual graph the remaining value from the edge capacity and the amount of flow that we use so far. How can I do that. How can I keep these two values for each vertex in the graph.
> >
> > these following questions may are easy for you ..
> > 4- How can I determine the last vertex as a sink.
> > 5- How can I get the number of all vertexes from the input file .
> >
> > I know I have written many question.I searched a lot in the Internet, but I did not find any discussion regards to this algorithm
> >
> > sorry and thank you.I appreciate any help or recommendations
> > Rana
>
>
Re: push-relabel flow algorithm
Posted by Pankaj Malhotra <pa...@gmail.com>.
If I get your point-1 right, you want to have a vertex class type other
than the ones available, for example: Text. If this is what you want, you
can have a class having as many fields as you want. Then convert the
objects of that class to Json objects using Gson for example. Then, you can
use the Json string to set the fields of the Text class.
On 22 March 2014 04:50, Rana Althunyan <ra...@gmail.com> wrote:
> Hello experts,
> > I really need your help. I am new to Giraph. I have project on pregel
> paper, and I need to implement One algorithm via Apache Giraph.The
> algorithm is push-relabel flow algorithm. Actually when I started to adapt
> the algorithm to fit to Giraph I found some problems. I will list them.
> >
> > 1- Because any type of data structure are not allowed in Giraph how can
> I store excess flow and distance value for each vertex.
> > 2- When the excess value becomes zero for any vertex, I wanna keep
> vertex flow during future supersteps even if the vertex received messages.
> > 3- The last point, when I want to send a flow to a vertex, i need store
> two values of residual graph the remaining value from the edge capacity
> and the amount of flow that we use so far. How can I do that. How can I
> keep these two values for each vertex in the graph.
> >
> > these following questions may are easy for you ..
> > 4- How can I determine the last vertex as a sink.
> > 5- How can I get the number of all vertexes from the input file .
> >
> > I know I have written many question.I searched a lot in the Internet,
> but I did not find any discussion regards to this algorithm
> >
> > sorry and thank you.I appreciate any help or recommendations
> > Rana
>
>
Fwd: push-relabel flow algorithm
Posted by Rana Althunyan <ra...@gmail.com>.
Hello experts,
> I really need your help. I am new to Giraph. I have project on pregel paper, and I need to implement One algorithm via Apache Giraph.The algorithm is push-relabel flow algorithm. Actually when I started to adapt the algorithm to fit to Giraph I found some problems. I will list them.
>
> 1- Because any type of data structure are not allowed in Giraph how can I store excess flow and distance value for each vertex.
> 2- When the excess value becomes zero for any vertex, I wanna keep vertex flow during future supersteps even if the vertex received messages.
> 3- The last point, when I want to send a flow to a vertex, i need store two values of residual graph the remaining value from the edge capacity and the amount of flow that we use so far. How can I do that. How can I keep these two values for each vertex in the graph.
>
> these following questions may are easy for you ..
> 4- How can I determine the last vertex as a sink.
> 5- How can I get the number of all vertexes from the input file .
>
> I know I have written many question.I searched a lot in the Internet, but I did not find any discussion regards to this algorithm
>
> sorry and thank you.I appreciate any help or recommendations
> Rana