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 B58079757 for ; Sat, 3 Mar 2012 13:58:33 +0000 (UTC) Received: (qmail 1493 invoked by uid 500); 3 Mar 2012 13:58:33 -0000 Delivered-To: apmail-commons-dev-archive@commons.apache.org Received: (qmail 1380 invoked by uid 500); 3 Mar 2012 13:58:33 -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 1372 invoked by uid 99); 3 Mar 2012 13:58:33 -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 13:58:33 +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 13:58:28 +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 522E463E94 for ; Sat, 3 Mar 2012 14:58:06 +0100 (CET) Message-ID: <4F52236C.9000708@dia.uniroma3.it> Date: Sat, 03 Mar 2012 14:58:04 +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> <4F521202.7010207@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, > Apologize but I still don't understand what the benefit is on storing > nodes/arcs data in the Graph data structure back to James' first email: any type could be immediately used as edge/vertex without wrappers, while specific data related to the domain of graphs (weights, labels) would be handled separately. I actually think this is useful: back to my days of "DIY Java graphs" I implemented something similar to what we have now, just to think every time: "why should I wrap my objects with these markers? I already know my Router is a Vertex in the graph..." > - sounds to me like a > Collection where, to know the int value of its elements, have > to query the data structure, i.e. > > Collection integerCollection = ...; > for ( Integer ptr : integerCollection ) > { > int value = integerCollection.getInt( ptr ); > } > > It is weird to me even reading it. > > When I started modeling Graph, I had collections in mind - above all > to simplify its adoption - I would be more than pleased to drop > Weighted* version of graphs and come back to the previous situation, > but with the annoying type inference issue fixed. Here's the way I see it. A Graph implementing HasWeightedEdges would have something like this inside: Map edgeWeights = new HashMap(); [... populate map, other methods, etc ...] // implementing HasWeightedEdges#getEdgeWeight public W getEdgeWeight(E edge) { [... check null etc...] return edgeWeights.get(edge); } >> 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. > OK, concept is clear, I still don't agree on the nomenclature, anyway. > Actually *WeightBaseOperations describe > *WeightAdditionalOrderedMonoid, so *BaseOperations doesn't sound self > explaining. then let's find a better name, but why *OrderedMonoid? Assume we replace the whole set of current interfaces (see my comment to the next paragraph below) with just Addition and Comparable (the latter already exists of course). There is no need to create another interface to merge the two (ComparableAddition? OrderedAddition?). Then we have: public class DoubleWeightOperations implements Addition, Comparator { [...] } I would not rename the class to DoubleWeightAddition or even DoubleWeightComparableAddition. What if later we need to e.g. add a function that normalizes weights by some factor, or returns the reciprocal of a weight, etc? With the above code it would suffice to add new interfaces: public class DoubleWeightOperations implements Addition, Comparator, Normalization, Reciprocal { [...] } > > Moreover, The Zero interface is the *additional* monoid identity > element, if someone has to implement the Multiplication Monoid I > wouldn't expect he implements the One interface wich declares O one() > method. > This is why IMHO in the current algebra model, Zero has to be dropped > and has to be modified in: That is fine for me. I simply followed pure theory while implementing that and used all possible granularity. Now looking at our implementations I think it is save enough to even merge Zero, Semigroup and Monoid (so that's one step further than your example below) and call the result Addition so that its role is clear to everybody. Does that sound good? :) Claudio > > /** > * semigroup is an algebraic structure consisting of a set together > with an associative binary operation. > */ > interface Semigroup > { > > E append( E s1, E s2 ); > > } > > /** > * A {@link Monoid} is a {@link Semigroup} with an identity value. > */ > public interface Monoid > extends Semigroup > { > > E identity(); > > E inverse( E element ); > > } > > that would continue working for every Monoid specialization. Or not? thoughts? > Thanks and best, > -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:43 PM, Claudio Squarcella > wrote: >> 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 >> > --------------------------------------------------------------------- > 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