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 Fri, 02 Mar 2012 22:02:16 GMT
Hola,

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

> 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

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

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


Mime
View raw message