Graph partitioning algorithm

[Phalguni Mukherjee <ph...@gmail.com>]

Can someone help me out with the algorithm to assign node to the worker, in
Giraph.

I read somewhere that, master selects the number of partition i.e N and
than do a
hash(Vertex_ID)/N on each vertex to know its partition.

will be thankful if someone can explain what this N means and what this
hash function actually is.

Also kindly correct my thought process if my understanding is wrong
regarding the same or provide me some link where I can get the details.



-- 
*Thanks & Regards*
*Phalguni Mukherjee*

RE: Graph partitioning algorithm

[Pavan Kumar A <pa...@outlook.com>]

If you are comfortable looking at the code then the files you need to look at areHashMasterPartitioner (giraph/giraph-core/src/main/java/org/apache/giraph/partition/HashMasterPartitioner.java)HashWorkerPartitioner (giraph/giraph-core/src/main/java/org/apache/giraph/partition/HashWorkerPartitioner.java)
Master computes the number of partitions by usingcreateInitialPartitionOwners which calls into PartitionUtils#computePartitionCount methodin most cases the partition count is just numAvailableWorkers*numAvailableWorkers (you can see for yourself in the code in PartitionUtils.java)
The hash function is nothing fancy it is just vertexId.hashCode() -> u can see in code at HashWorkerPartitioner#getPartitionOwner
Hope that helps.
> Date: Fri, 28 Nov 2014 11:24:40 +0530> Subject: Graph partitioning algorithm
> From: phalgunimukherjee1007@gmail.com
> To: dev@giraph.apache.org
> 
> Can someone help me out with the algorithm to assign node to the worker, in
> Giraph.
> 
> I read somewhere that, master selects the number of partition i.e N and
> than do a
> hash(Vertex_ID)/N on each vertex to know its partition.
> 
> will be thankful if someone can explain what this N means and what this
> hash function actually is.
> 
> Also kindly correct my thought process if my understanding is wrong
> regarding the same or provide me some link where I can get the details.
> 
> 
> 
> -- 
> *Thanks & Regards*
> *Phalguni Mukherjee*