commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <>
Subject Re: [graph] Why the Vertex and Edge interfaces?
Date Fri, 02 Mar 2012 21:22:39 GMT

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


> On Mar 2, 2012 3:08 PM, "Ted Dunning"<>  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<
>>>  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
>>> ------------------------------**------------------------------**---------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.**<
>>> For additional commands, e-mail:

Claudio Squarcella
PhD student at Roma Tre University

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message