commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From James Carman <ja...@carmanconsulting.com>
Subject Re: [Graph] On graph weight type(s)
Date Mon, 12 Dec 2011 04:39:49 GMT
Sorry, I was on my phone before when I sent that.  Let me elaborate a
bit more.  I would just allow the weights to be of any type.  However,
you can create two different types of scenarios where you either use a
Comparable derivative or you use whatever you want, but you have to
supply a custom Comparator.

On Sun, Dec 11, 2011 at 8:01 PM, James Carman
<james@carmanconsulting.com> wrote:
> I wouldn't restrict the weight to Comparable.  What if the user wanted to
> provide their own Comparator?
>
> On Dec 11, 2011 7:07 PM, "Claudio Squarcella" <squarcel@dia.uniroma3.it>
> wrote:
>>
>> Hi all,
>>
>> I explored a bit more the (rather philosophical) dilemma that came from a
>> thread from last week, quoted below
>>>
>>> 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 :-)
>>
>>
>> The question is: *what do we mean by weight when dealing with graphs?*
>>
>> "Real number" is a standard answer in graph theory: see, e.g.,
>> http://www.math.jussieu.fr/~jabondy/books/gtwa/pdf/chapter1.pdf (pag. 15).
>> What we have now in the code is a {{getWeight()}} method that returns a
>> double. That serves well for all the algorithms currently implemented, and
>> probably for many more to come. However it is also true that:
>>
>>  * some domains of interest and/or algorithms might be more restrictive
>>   on the type and sign of "real number" for the weights: integers,
>>   non-negative rationals, etc.
>>  * strictly speaking, the basic operations associated with weights are
>>   usually just a few. Comparison and sum are enough at least for the
>>   algorithms implemented so far in the project (please correct me if I
>>   am wrong). Maybe scaling? Additive inverse?
>>  * each algorithm is aware of the subset of required operations. E.g.
>>   Prim's algorithm for minimum spanning trees only requires edge
>>   weights to be comparable, so they could even be Strings or whatever...
>>  * some very abstract user might want to use a new class (not
>>   necessarily a number) as a weight, provided that it meets the
>>   requirements of the domain.
>>
>> So here is a high-level view of what I propose:
>>
>>  * the basic weight is nothing more than a {{Comparable}}, which is
>>   hopefully generic enough;
>>  * where needed, algorithms define more specific constraints on the
>>   input graph in their signature (e.g. Dijkstra can use {{Double}}).
>>
>>
>> Looking forward for comments,
>> Claudio
>>
>> --
>> 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
>>
>

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


Mime
View raw message