commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <simonetrip...@apache.org>
Subject Re: [graph] Why the Vertex and Edge interfaces?
Date Sat, 03 Mar 2012 01:21:10 GMT
> 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 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

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


Mime
View raw message