Yes code will speak volumes. Perhaps a couple proposal branches if we have incompatible ideas? On Mar 3, 2012 10:47 AM, "Simone Tripodi" <simonetrip...@apache.org> wrote:
> Cloud.io, > > > 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..." > > I already showed be open on dropping elements, do I have to copy my > first reply as well so we start again? :) > OK, I started collecting various thoughts and trying to converge them > to a common path: Vertex is something we can safety drop because we > know its nature at priori, markers are unnecessary.This is fine. > > > > > Here's the way I see it. A Graph<V,E> implementing HasWeightedEdges would > > have something like this inside: > > > > Map<E, W> edgeWeights = new HashMap<E, W>(); > > > > [... populate map, other methods, etc ...] > > > > // implementing HasWeightedEdges#getEdgeWeight > > public W getEdgeWeight(E edge) > > { > > [... check null etc...] > > return edgeWeights.get(edge); > > > > } > > > > what is the sense, at that point, on keeping the Edge?!! It would be > more than enough to know which is the Head and which is the Tail in > the Edge to get the W! > > > then let's find a better name, but why *OrderedMonoid? > > maybe because they implement 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: > > > > how much would Addition and Multiplication interface differ each other? > > > 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 > > { > > [...] > > > > } > > > > > > that would be fine, what is not clear is that Monoids expose the same > interface, so *Operations class implementation canot declare same > method multiple times > > > > > That is fine for me. I simply followed pure theory while implementing > that > > and used all possible granularity. > > questionable, that is why we are still speaking about it > > > 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? :) > > Sounds more than good, it is what I already proposed messages ago: > > > 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 > > despite the rename, I still like the Monoid :P > > enough talk IMHO, time to code and make concrete proposals > > 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 2:58 PM, Claudio Squarcella > <squar...@dia.uniroma3.it> wrote: > > 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<Integer> where, to know the int value of its elements, have > >> to query the data structure, i.e. > >> > >> Collection<Integer> 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<V,E> implementing HasWeightedEdges would > > have something like this inside: > > > > Map<E, W> edgeWeights = new HashMap<E, W>(); > > > > [... 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> > >> { > >> > >> E append( E s1, E s2 ); > >> > >> } > >> > >> /** > >> * A {@link Monoid} is a {@link Semigroup} with an identity value. > >> */ > >> public interface Monoid<E> > >> extends Semigroup<M> > >> { > >> > >> 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 > >> <squar...@dia.uniroma3.it> 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 > >>>> <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 > >>>> > >>> -- > >>> 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 > >