> 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 edgeweighted graphs
> (EdgeWeightedGraph, renaming the current WeightedGraph?), one for
> vertexweighted 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
<squarcel@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 edgeweighted graphs
> (EdgeWeightedGraph, renaming the current WeightedGraph?), one for
> vertexweighted 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
>> <squarcel@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.dunning@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<
>>>>> 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 longvision 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, email: devunsubscribe@commons.**apache.org<
>>>>>
>>>>> devunsubscribe@commons.apache.org>
>>>>>>
>>>>>> For additional commands, email: devhelp@commons.apache.org
>>>>>>
>>>>>>
>>> 
>>> Claudio Squarcella
>>> PhD student at Roma Tre University
>>> http://www.dia.uniroma3.it/~squarcel
>>> http://squarcella.com/
>>>
>>>
>>> 
>>> To unsubscribe, email: devunsubscribe@commons.apache.org
>>>
>>> For additional commands, email: devhelp@commons.apache.org
>>>
>> 
>> To unsubscribe, email: devunsubscribe@commons.apache.org
>> For additional commands, email: devhelp@commons.apache.org
>>
>
> 
> Claudio Squarcella
> PhD student at Roma Tre University
> http://www.dia.uniroma3.it/~squarcel
> http://squarcella.com/
>
>
> 
> To unsubscribe, email: devunsubscribe@commons.apache.org
> For additional commands, email: devhelp@commons.apache.org
>

To unsubscribe, email: devunsubscribe@commons.apache.org
For additional commands, email: devhelp@commons.apache.org
