commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <squar...@dia.uniroma3.it>
Subject Re: [graph] Why the Vertex and Edge interfaces?
Date Sat, 03 Mar 2012 12:43:46 GMT
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
> <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 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
>>> <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 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-unsubscribe@commons.apache.org>
>>>>>>> For additional commands, e-mail: dev-help@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-unsubscribe@commons.apache.org
>>>>
>>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> For additional commands, e-mail: dev-help@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-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message