> 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 > * 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 > 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. > you cheater always know how to confuse me :P > 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! 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 <squar...@dia.uniroma3.it> 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 >> <squar...@dia.uniroma3.it> 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"<ted.dunn...@gmail.com> 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< >>>>> squar...@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<Edge, Weight>, 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-unsubscr...@commons.apache.org> >>>>>> >>>>>> For additional commands, e-mail: dev-h...@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-unsubscr...@commons.apache.org >>> >>> For additional commands, e-mail: dev-h...@commons.apache.org >>> >> --------------------------------------------------------------------- >> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org >> For additional commands, e-mail: dev-h...@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-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
