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] Weighted as an interface
Date Mon, 05 Dec 2011 12:55:02 GMT
Hi,

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 
Number>}}?
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}} ;-)

Ciao,
Claudio

>
> Looking forward for your contributions, can't wait for them! :)
> Simo
>
> [1] https://issues.apache.org/jira/browse/SANDBOX
>
> http://people.apache.org/~simonetripodi/
> http://simonetripodi.livejournal.com/
> http://twitter.com/simonetripodi
> http://www.99soft.org/
>
>
>
> On Mon, Dec 5, 2011 at 2:00 AM, James Carman<james@carmanconsulting.com>  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"<squarcel@dia.uniroma3.it>
>> 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: squarcel@dia.uniroma3.it
>>> Phone: +39-06-57333215
>>> Fax: +39-06-57333612
>>> http://www.dia.uniroma3.it/~**squarcel<http://www.dia.uniroma3.it/~squarcel>
>>>
>>>
>>> ------------------------------**------------------------------**---------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<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
E-mail address: squarcel@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message