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 17:27:18 GMT
Why do you need doubles for Dijkstra?  Accumulating the total path
weights?  Why not introduce an Accumulator interface?
On Dec 12, 2011 9:32 AM, "Claudio Squarcella" <squarcel@dia.uniroma3.it>
wrote:

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

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