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] On graph weight type(s)
Date Mon, 12 Dec 2011 14:31:48 GMT
Hi,

On 12/12/2011 05:39, James Carman wrote:
> 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.

ok it definitely makes sense, thanks :)

The thing is: in case the weight is actually a number I would really 
like to keep it simple on the user side, i.e. it should be usable with 
something like {{Weighted<Double>}}, or {{Weighted<Integer>}}, etc. On 
the other hand, some of the implemented algorithms would need to expose 
one method per number type: e.g. Dijkstra (which also sums weights, so 
it needs numbers) would need a method for Doubles, one for Integers, 
etc. Alternatively one could use the abstract class {{Number}} once for 
all -- but that would not make things easier, because there is no way to 
do maths directly with it (see e.g. 
http://stackoverflow.com/questions/2721390/how-to-add-two-java-lang-numbers).

Summing up:

  * {{public interface Weighted<W>}} with method {{public W getWeight()}}
  * weighted "things" ({{Edge}}, {{Vertex}}, {{Graph}}, etc) need to
    implement it, e.g. {{public interface WeightedEdge<E,W> extends
    Edge<E>, Weighted<W>}}
  * each algorithm specifies the type of weight needed. E.g. Prim would
    only require edges to have {{Comparable}} weights or a
    {{Comparator}}, while Dijkstra needs edges with weights as real
    numbers (maybe just {{Double}} for now), etc.

How does that sound?

Ciao,
Claudio


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

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