giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Pavan Kumar A <pava...@outlook.com>
Subject RE: Can a vertex belong to more than one partition
Date Wed, 16 Apr 2014 07:27:56 GMT
Isn't graph isomorphism NP-Hard in general.I guess you already know that partitions in giraph
does not mean actual "graph partitioning" / "graph clustering" -- for instance http://dl.acm.org/citation.cfm?id=2433461.It
is just a concept of splitting the vertices into different compute segments for parallel &
distributed processing of the graph.
Anyway there are multiple ways where in u can make the query graph available to all vertices
of the big graphFor instance you can have a different inputformat defined for your query graph
file that will read it as one vertex with a fixed id - say "QueryGraph" and any vertex that
needs access to the graph can send it a message and receive the whole graph as response, for
instance.
However, your requirements remind me of the Giraph++ work : http://researcher.watson.ibm.com/researcher/files/us-ytian/giraph++.pdfThis
is not supported in Giraph yet. I guess you want to do some computation on the whole partition
like compare the query graph with the entire partition of the big graph, etc. which is not
so easy to do with the current api.
I might have misunderstood, please correct me if wrong.Thanks
> Date: Wed, 16 Apr 2014 09:55:18 +0530
> Subject: Re: Can a vertex belong to more than one partition
> From: trivedi.akshay3@gmail.com
> To: user@giraph.apache.org
> 
> Hi,
> I am solving graph isomorhism between a large graph and query graph.
> The large graph is partitioned and so the query graph should be
> available to all partitions. Apart from this, some of the large graph
> vertices(such as those which have edges between partitions) also have
> to be duplicated.
> 
> On Mon, Apr 7, 2014 at 9:53 PM, Pavan Kumar A <pavanka@outlook.com> wrote:
> > If you want the vertex.value to be available to all vertices, then you can
> > store it in an aggregator.
> > A vertex can belong to exactly one partition. But please answer Lukas's
> > questions so we can answer more appropriately.
> >
> >> Date: Mon, 7 Apr 2014 11:23:58 +0200
> >> From: lukas.nalezenec@firma.seznam.cz
> >> To: user@giraph.apache.org
> >> Subject: Re: Can a vertex belong to more than one partition
> >
> >>
> >> Hi,
> >>
> >> No, Vertex can belong only to one partition.
> >> Can you describe algorithm you are solving ? How many those vertexes
> >> belonging to all partitions you have ?
> >> Why do you need so strict partitioning ?
> >>
> >> Regards
> >> Lukas
> >>
> >>
> >> On 6.4.2014 12:38, Akshay Trivedi wrote:
> >> > In order to custom partition the graph, WorkerGraphPartitioner has to
> >> > be implemented. It has a method getPartitionOwner(I vertexId) which
> >> > returns PartitionOwner of the vertex. I want that some vertices belong
> >> > to all paritions i.e all PartitionOwners. Can anyone help me with it?
> >> > Thankyou in advance
> >> >
> >> > Regards
> >> > Akshay
> >>
 		 	   		  
Mime
View raw message