commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From James Carman <>
Subject Re: [Graph] On graph weight type(s)
Date Mon, 12 Dec 2011 01:01:02 GMT
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" <>

> 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.,
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:
> Phone: +39-06-57333215
> Fax: +39-06-57333612
> ------------------------------**------------------------------**---------
> To unsubscribe, e-mail: dev-unsubscribe@commons.**<>
> For additional commands, e-mail:

  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message