Hola, > 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. > 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 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 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
