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 127E59EB4 for ; Sat, 3 Mar 2012 12:44:18 +0000 (UTC) Received: (qmail 57763 invoked by uid 500); 3 Mar 2012 12:44:17 -0000 Delivered-To: apmail-commons-dev-archive@commons.apache.org Received: (qmail 57592 invoked by uid 500); 3 Mar 2012 12:44:17 -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 57581 invoked by uid 99); 3 Mar 2012 12:44:17 -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 12:44:17 +0000 X-ASF-Spam-Status: No, hits=-0.7 required=5.0 tests=RCVD_IN_DNSWL_LOW,SPF_HELO_PASS,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (athena.apache.org: domain of squarcel@dia.uniroma3.it designates 193.205.219.56 as permitted sender) Received: from [193.205.219.56] (HELO mail3.dia.uniroma3.it) (193.205.219.56) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 03 Mar 2012 12:44:12 +0000 Received: from hyper.local (93-41-226-173.ip83.fastwebnet.it [93.41.226.173]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: squarcel) by mail3.dia.uniroma3.it (Postfix) with ESMTPSA id 774BD63E7A for ; Sat, 3 Mar 2012 13:43:48 +0100 (CET) Message-ID: <4F521202.7010207@dia.uniroma3.it> Date: Sat, 03 Mar 2012 13:43:46 +0100 From: Claudio Squarcella Organization: Roma Tre University User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7; rv:10.0.2) Gecko/20120216 Thunderbird/10.0.2 MIME-Version: 1.0 To: dev@commons.apache.org Subject: Re: [graph] Why the Vertex and Edge interfaces? References: <4F508774.7080905@dia.uniroma3.it> <4F513A1F.1030103@dia.uniroma3.it> <4F5167CB.4060306@dia.uniroma3.it> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Checked: Checked by ClamAV on apache.org Hi, On 03/03/2012 02:21, Simone Tripodi wrote: >> 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 need >> 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 sure :) >> * with the current approach: one interface for edge-weighted graphs >> (EdgeWeightedGraph, renaming the current WeightedGraph?), one for >> vertex-weighted graphs (VertexWeightedGraph) and maybe even one for >> weights on both edges and vertices (EdgeAndVertexWeightedGraph?) -- >> not to talk about their counterparts with labels, etc; >> * with the proposed approach: a Graph would implement >> HasWeightsOnEdges and/or HasWeightsOnVertices -- and maybe also >> 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 that is right. On the other hand with "HasWeightedEdges" we could drop "WeightedEdge" and so on: one interface in, one out. Or we could even save both approaches as alternative implementations. That is: * a set of interfaces: e.g. HasWeightedEdges#getWeight(edge), HasWeightedVertices#getWeight(vertex), etc. * #1 implementation with external properties: the graph keeps the mapping between edge/vertex and weight, so that any type can be used for edges/vertices * #2 classical implementation: we keep markers like WeightedEdge and WeightedVertex but only the graph knows about them. algorithms keep asking the graph for weights of edges/vertices, and the graph in turn asks the edge/vertex itself (passed as parameter). WDYT? >> I know that this kind of "mismatch" is not your favourite ;) but would you >> really call "Operations" something which is just an "Addition" -- or >> viceversa "DoubleWeightAddition" something that might later be expanded with >> other operations? > I am confused now: this is what you did in the concrete implementation! no, trying to be clearer: you propose to rename Monoid into WeightOperation, which is like renaming Addition into Operation. Or alternatively to call the current *WeightBaseOperations something like *WeightMonoid. In both cases I disagree because I would prefer to keep a clear distinction between single well-defined properties/operations (like Addition or Comparator) and the comprehensive implementation (e.g. DoubleWeightBaseOperations) that implements all the operations it can implement with Doubles. Hoping we'll converge somewhere, maybe asymptotically ;) Claudio > > 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 good >> (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 need >> 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: >> >> * with the current approach: one interface for edge-weighted graphs >> (EdgeWeightedGraph, renaming the current WeightedGraph?), one for >> vertex-weighted graphs (VertexWeightedGraph) and maybe even one for >> weights on both edges and vertices (EdgeAndVertexWeightedGraph?) -- >> not to talk about their counterparts with labels, etc; >> * with the proposed approach: a Graph would implement >> HasWeightsOnEdges and/or HasWeightsOnVertices -- and maybe also >> 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 extends Zero and Semigroup - given >>> 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 much >> what happens now with the wrappers for Double, Integer, etc. >> >> I know that this kind of "mismatch" is not your favourite ;) but would you >> really call "Operations" something which is just an "Addition" -- or >> viceversa "DoubleWeightAddition" something that might later be expanded with >> 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 >>> wrote: >>>> Hi, >>>> >>>> >>>>> The weights can be external, too. It's only a function from edge to >>>>> weight. Your algorithm can take a function for its weights. The 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 edges >>>> 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" wrote: >>>>> >>>>>> Having weights on vertices is quite common. Consider any probability >>>>>> transition network. The 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> wrote: >>>>>> >>>>>>> Hi all, >>>>>>> >>>>>>> Claudio is aware also about algorithms where weights are associated >>>>>>> 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 want >>>>>>> to >>>>>>> represent only a subset of info in the label, etc). >>>>>>> >>>>>>> Matthew Pocock suggested an alternative approach back in the days of >>>>>>> weight abstraction: >>>>>>> >>>>>>> * the graph itself is extremely simple and naked: no weights/labels >>>>>>> on >>>>>>> vertices/edges; >>>>>>> * all properties are stored in some external structure, which I >>>>>>> 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 the >>>>>>> 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 > -- 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