Return-Path: X-Original-To: apmail-commons-dev-archive@www.apache.org Delivered-To: apmail-commons-dev-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id AA75190B4 for ; Sat, 3 Mar 2012 01:21:35 +0000 (UTC) Received: (qmail 18202 invoked by uid 500); 3 Mar 2012 01:21:35 -0000 Delivered-To: apmail-commons-dev-archive@commons.apache.org Received: (qmail 18107 invoked by uid 500); 3 Mar 2012 01:21:35 -0000 Mailing-List: contact dev-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: "Commons Developers List" Delivered-To: mailing list dev@commons.apache.org Received: (qmail 18098 invoked by uid 99); 3 Mar 2012 01:21:35 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 03 Mar 2012 01:21:35 +0000 X-ASF-Spam-Status: No, hits=-0.7 required=5.0 tests=RCVD_IN_DNSWL_LOW,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (athena.apache.org: domain of simone.tripodi@gmail.com designates 209.85.216.179 as permitted sender) Received: from [209.85.216.179] (HELO mail-qy0-f179.google.com) (209.85.216.179) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 03 Mar 2012 01:21:31 +0000 Received: by qcha6 with SMTP id a6so917677qch.38 for ; Fri, 02 Mar 2012 17:21:10 -0800 (PST) Received-SPF: pass (google.com: domain of simone.tripodi@gmail.com designates 10.229.114.222 as permitted sender) client-ip=10.229.114.222; Authentication-Results: mr.google.com; spf=pass (google.com: domain of simone.tripodi@gmail.com designates 10.229.114.222 as permitted sender) smtp.mail=simone.tripodi@gmail.com; dkim=pass header.i=simone.tripodi@gmail.com Received: from mr.google.com ([10.229.114.222]) by 10.229.114.222 with SMTP id f30mr1825140qcq.13.1330737670335 (num_hops = 1); Fri, 02 Mar 2012 17:21:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:content-type :content-transfer-encoding; bh=nREevEO2gq+ug/bplSQXvsyM1UATr+AfX61lB4uCVHE=; b=DO9JRC1c+mvHJAmybAdUd+OFnC0sy4f2oIfkc6zuxaz8rSzBzvkWxWMdbaww1XE0rh OYnjJJFqqYd0wb+JvAucQPDSeQakkcDcRQA5y0KD3rGqj4fN4YTM+G3XKYvOT+mISVYi qStaSMgOhiBIM1NXoGg6cCt9v6vuEDUnYx7kjPOWGVeSPuBAagGPkY/qrWyZ4F4ZdTnH +1V1RRiGnVHlomSJjmkufLaRDRLH2+f/nfXdx6gEzPYqcEooPlfHnh5Df0/ShnlvsCj9 JizvG6+4rnfsEjmBLe33qAgmFWVp4JuZoqqlfjU5rWL2/qoi2NXMooKfn0qhrTsGLDXS KrAA== MIME-Version: 1.0 Received: by 10.229.114.222 with SMTP id f30mr1545447qcq.13.1330737670247; Fri, 02 Mar 2012 17:21:10 -0800 (PST) Sender: simone.tripodi@gmail.com Received: by 10.224.195.73 with HTTP; Fri, 2 Mar 2012 17:21:10 -0800 (PST) In-Reply-To: <4F5167CB.4060306@dia.uniroma3.it> References: <4F508774.7080905@dia.uniroma3.it> <4F513A1F.1030103@dia.uniroma3.it> <4F5167CB.4060306@dia.uniroma3.it> Date: Sat, 3 Mar 2012 02:21:10 +0100 X-Google-Sender-Auth: Nhh6O207mxC7YfNuxe20KVcNhx8 Message-ID: Subject: Re: [graph] Why the Vertex and Edge interfaces? From: Simone Tripodi To: Commons Developers List Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Virus-Checked: Checked by ClamAV on apache.org > first of all: yes, I will play with this stuff as soon as I find the time= :) this is scaring... go Orb.io, go! :) > constant), but still there is one more step of indirection. So we would n= eed > to test and compare performances, hopefully with acceptable results. sounds it would be better if you implement that stuff in a branch to keep both implementations, IMHO > =C2=A0* with the current approach: one interface for edge-weighted graphs > =C2=A0 (EdgeWeightedGraph, renaming the current WeightedGraph?), one for > =C2=A0 vertex-weighted graphs (VertexWeightedGraph) and maybe even one fo= r > =C2=A0 weights on both edges and vertices (EdgeAndVertexWeightedGraph?) -= - > =C2=A0 not to talk about their counterparts with labels, etc; > =C2=A0* with the proposed approach: a Graph would implement > =C2=A0 HasWeightsOnEdges and/or HasWeightsOnVertices -- and maybe also > =C2=A0 HasLabelsOnEdges if needed. do you remember that we reintroduced the WeightedGraph just for the type inference issue on fluent APIs in Eclipse, do you? ;) It would have been worked otherwise as well dropping the WeightedGraph and expressing types only on Vertex/Edges > I can agree with most of what you say but I would still call the result > Monoid, or maybe even better Addition -- because that is what it is, a > Monoid representing the sum operation. "WeightOperation" sounds more like= a > general "container" which can include Addition, Comparator, and maybe in = the > near future Multiplication or who knows what -- which again is pretty muc= h > what happens now with the wrappers for Double, Integer, etc. > you cheater always know how to confuse me :P > I know that this kind of "mismatch" is not your favourite ;) but would yo= u > really call "Operations" something which is just an "Addition" -- or > viceversa "DoubleWeightAddition" something that might later be expanded w= ith > other operations? I am confused now: this is what you did in the concrete implementation! time to sleep, cannot reply anymore, read tomorrow -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Sat, Mar 3, 2012 at 1:37 AM, Claudio Squarcella wrote: > Hi, > > > >>> what if that mapping function becomes a responsibility of WeightedGraph >>> itself? >>> And more generally, what if any property of vertices and/or edges is >>> moved to the containing graph? >> >> that would imply that Graph implementations have to implement vertices >> and/or edges metadata indexing, that would be anyway less performant >> than accessing directly on metadata contained in current node/arc - >> just count the number of time you should have to touch the adapted >> data structures, of course will be at least one more than the actual. > > > that is absolutely right. Not asymptotically if the implementation is goo= d > (hashmaps are already good enough with their read time which is basically > constant), but still there is one more step of indirection. So we would n= eed > to test and compare performances, hopefully with acceptable results. > > >>> We could externalize all different graph properties to appropriate >>> interfaces (HasWeightsOnEdges, HasLabelsOnVertices, etc) and then each >>> algorithm specifies the needed input graph including the subset of >>> interfaces it needs to implement. We do something like that with weight >>> operations already. >> >> I am worried that with that approach the number of interfaces would >> proliferate like pollen during Spring, users - and devs - would get >> easily lost > > > but that would happen anyway as soon as we implement an algorithm with > weights on vertices, right? Here are the options I see: > > =C2=A0* with the current approach: one interface for edge-weighted graphs > =C2=A0 (EdgeWeightedGraph, renaming the current WeightedGraph?), one for > =C2=A0 vertex-weighted graphs (VertexWeightedGraph) and maybe even one fo= r > =C2=A0 weights on both edges and vertices (EdgeAndVertexWeightedGraph?) -= - > =C2=A0 not to talk about their counterparts with labels, etc; > =C2=A0* with the proposed approach: a Graph would implement > =C2=A0 HasWeightsOnEdges and/or HasWeightsOnVertices -- and maybe also > =C2=A0 HasLabelsOnEdges if needed. > > > >> weights are something already complicated for being a simple concept, >> please apologize for the little offtopic: >> >> Zero, name of an element, contains `zero` method to get the zero (it >> is still confusing to me), Monoid =C2=A0extends Zero and Semigroup - giv= en >> the use inside graph math, Zero#zero and Semigroup#append can be moved >> directly to Monoid and rename it as WeightOperation - does it remind >> you something? :P > > > I can agree with most of what you say but I would still call the result > Monoid, or maybe even better Addition -- because that is what it is, a > Monoid representing the sum operation. "WeightOperation" sounds more like= a > general "container" which can include Addition, Comparator, and maybe in = the > near future Multiplication or who knows what -- which again is pretty muc= h > what happens now with the wrappers for Double, Integer, etc. > > I know that this kind of "mismatch" is not your favourite ;) but would yo= u > really call "Operations" something which is just an "Addition" -- or > viceversa "DoubleWeightAddition" something that might later be expanded w= ith > other operations? > > Ciao and thanks for your feedback! > Claudio > > >> >> best, >> -Simo >> >> http://people.apache.org/~simonetripodi/ >> http://simonetripodi.livejournal.com/ >> http://twitter.com/simonetripodi >> http://www.99soft.org/ >> >> >> >> On Fri, Mar 2, 2012 at 10:22 PM, Claudio Squarcella >> =C2=A0wrote: >>> >>> Hi, >>> >>> >>>> The weights can be external, too. =C2=A0It's only a function from edge= to >>>> weight. =C2=A0Your algorithm can take a function for its weights. =C2= =A0The files >>>> library does it similar to this. >>> >>> >>> what if that mapping function becomes a responsibility of WeightedGraph >>> itself? And more generally, what if any property of vertices and/or edg= es >>> is >>> moved to the containing graph? >>> >>> We could externalize all different graph properties to appropriate >>> interfaces (HasWeightsOnEdges, HasLabelsOnVertices, etc) and then each >>> algorithm specifies the needed input graph including the subset of >>> interfaces it needs to implement. We do something like that with weight >>> operations already. >>> >>> Claudio >>> >>> >>> >>>> On Mar 2, 2012 3:08 PM, "Ted Dunning" =C2=A0 = =C2=A0wrote: >>>> >>>>> Having weights on vertices is quite common. =C2=A0Consider any probab= ility >>>>> transition network. =C2=A0The weight on each node is the probability = of >>>>> being >>>>> in >>>>> that state and the weights on the edges are conditional probabilties. >>>>> >>>>> Page rank is a related example of having weights on nodes. >>>>> >>>>> On Fri, Mar 2, 2012 at 12:40 AM, Claudio Squarcella< >>>>> squarcel@dia.uniroma3.it> =C2=A0 =C2=A0wrote: >>>>> >>>>>> Hi all, >>>>>> >>>>>> =C2=A0Claudio is aware also about algorithms where weights are assoc= iated >>>>>> to >>>>>>> >>>>>>> Vertex - he's preparing his PhD research on graphes - maybe he can >>>>>>> show us a more long-vision roadmap and evaluate benefits on >>>>>>> simplifying the design. >>>>>>> >>>>>> yes there are algorithms with weights on vertices. Of course those >>>>>> with >>>>>> weighted edges (like the ones already implemented) are much more >>>>> >>>>> widespread >>>>>> >>>>>> and frequently used, but still we cannot forget about that. Also, >>>>> >>>>> although >>>>>> >>>>>> on a secondary level, labels on vertices/edges are kind of important >>>>>> in >>>>>> many situations (including testing, debugging) where I think it is >>>>>> good >>>>> >>>>> to >>>>>> >>>>>> keep them distinct from the standard "toString" method (you might wa= nt >>>>>> to >>>>>> represent only a subset of info in the label, etc). >>>>>> >>>>>> Matthew Pocock suggested an alternative approach back in the days of >>>>>> weight abstraction: >>>>>> >>>>>> =C2=A0* the graph itself is extremely simple and naked: no weights/l= abels >>>>>> on >>>>>> =C2=A0 vertices/edges; >>>>>> =C2=A0* all properties are stored in some external structure, which = I >>>>>> =C2=A0 imagine composed of associative maps (Map, etc = etc). >>>>>> >>>>>> He motivated the idea with a "personal use case": often graphs are >>>>>> used >>>>>> and reused with the same structure but different weights (and/or >>>>>> labels, >>>>>> etc). Now if James' question becomes a second use case, maybe it's t= he >>>>>> right time to exhume that idea ;) >>>>>> >>>>>> Ciao, >>>>>> Claudio >>>>>> >>>>>> -- >>>>>> Claudio Squarcella >>>>>> PhD student at Roma Tre University >>>>>> http://www.dia.uniroma3.it/~**squarcel< >>>>> >>>>> http://www.dia.uniroma3.it/~squarcel> >>>>>> >>>>>> http://squarcella.com/ >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> ------------------------------**------------------------------**----= ----- >>>>>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org< >>>>> >>>>> dev-unsubscribe@commons.apache.org> >>>>>> >>>>>> For additional commands, e-mail: dev-help@commons.apache.org >>>>>> >>>>>> >>> -- >>> Claudio Squarcella >>> PhD student at Roma Tre University >>> http://www.dia.uniroma3.it/~squarcel >>> http://squarcella.com/ >>> >>> >>> --------------------------------------------------------------------- >>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org >>> >>> For additional commands, e-mail: dev-help@commons.apache.org >>> >> --------------------------------------------------------------------- >> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org >> For additional commands, e-mail: dev-help@commons.apache.org >> > > -- > Claudio Squarcella > PhD student at Roma Tre University > http://www.dia.uniroma3.it/~squarcel > http://squarcella.com/ > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org > For additional commands, e-mail: dev-help@commons.apache.org > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org For additional commands, e-mail: dev-help@commons.apache.org