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 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
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 welldefined 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
> <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
>

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
