Hi,
first of all: yes, I will play with this stuff as soon as I find the time :)
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
