commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <>
Subject Re: [Graph] Weighted as an interface
Date Mon, 05 Dec 2011 12:55:02 GMT

thanks to both for your words! Please find comments below.

On 05/12/2011 10:01, Simone Tripodi wrote:
> Hi Claudio,
> what a pleasant surprise! :) I was hoping commons-graph would have
> caught the interest of researchers on that field, I'm really happy you
> would like to contribute!
> I agree with your observations, please fill new issues on JIRA[1] and
> feel free to provide patches, I'll process them ASAP :)

Alright, I'll find time later this week.

As for my suggestion on types, should I go for {{Weighted<N extends 
Note that I am also concerned about domain-specific requirements (e.g. 
all weights must be positive) that I would like to see implemented as 
"statically" as possible in the code. {{Number}} should give us quite 
enough freedom in that direction (e.g. one could later extend it with 
something like {{PositiveInteger}}).

A more platonic alternative would be to have an abstract type of weight 
which 1. is comparable and 2. can be aggregated in some way (e.g. the 
weight of a path is the sum of weights of its edges). But I am probably 
going too far...

> Moreover, I start having the feeling the {{WeightedGraph}} is a
> useless interface: it is enough marking the vertices/edges as weighted
> depending on the problem... or not? At the end of the day,
> {{WeightedGraph}} does nothing than having the the edges marked as
> weighted, so Dijkstra signature changed as:
> <V extends Vertex, WE extends WeightedEdge, G extends DirectedGraph<V,
> WE>>  WeightedPath<V, WE>  findShortestPath( G graph,  V source, V
> target )
> still define well the input type, a graph wich relations are directed
> edges and edges are weighted... WDYT?

I agree, as long as there are no specific features of the graph that are 
independent on its vertices and edges. Another advantage: I won't bother 
later to add more speficic interfaces like {{EdgeWeightedGraph}} or 
{{VertexWeightedGraph}} ;-)


> Looking forward for your contributions, can't wait for them! :)
> Simo
> [1]
> On Mon, Dec 5, 2011 at 2:00 AM, James Carman<>  wrote:
>> Welcome!  Contributions (and the contributor) are always welcome.  In my
>> past life, I did quite a bit of graph programming to solve "business"
>> problems.  We used yfiles, though.  I hope to get around to playing with
>> [graph] someday too.  Please do submit a patch!
>> On Dec 4, 2011 6:43 PM, "Claudio Squarcella"<>
>> wrote:
>>> Hello,
>>> I have been reading the source in the past days and I found that the
>>> concept of "weight" (e.g. weighted edge, graph, etc) could benefit from a
>>> bit of abstraction.
>>> The basic idea would be to have an interface called Weighted with an
>>> obvious method getWeight(). Changes in the code would easily derive from
>>> that. As a side effect it would be easy to implement new stuff like
>>> weighted vertices: not as glorious as weighted edges, but still needed in
>>> some problems (e.g. all-pairs bottleneck paths) and therefore desirable for
>>> a general purpose graph API.
>>> One step further. A weight is not necessarily a double: in some cases not
>>> even a number, but rather a "comparable" of some sort. So I would suggest
>>> to make use of generics in some way, possibly the smartest. Suggestions are
>>> welcome :-)
>>> If my thoughts meet some interest I will work on a patch.
>>> Ciao,
>>> Claudio
>>> P.S.
>>> I am a first-timer here, so what follows is a short introduction.
>>> I am doing a PhD in Graph Drawing and Information Visualization. I always
>>> looked for a standard, unified way to represent and handle graphs when
>>> developing prototypes. So my interest in this project is quite natural, and
>>> I am willing to help and see it become a robust project.
>>> --
>>> Claudio Squarcella
>>> PhD student at Roma Tre University
>>> E-mail address:
>>> Phone: +39-06-57333215
>>> Fax: +39-06-57333612
>>> ------------------------------**------------------------------**---------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.**<>
>>> For additional commands, e-mail:
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

Claudio Squarcella
PhD student at Roma Tre University
E-mail address:
Phone: +39-06-57333215
Fax: +39-06-57333612

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

View raw message