commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <simonetrip...@apache.org>
Subject Re: [Graph] On graph weight type(s)
Date Mon, 12 Dec 2011 17:35:29 GMT
Hi James!
yes, actual Dijkstra implementation[1] uses Double number to
accumulating the total path weights...
I think Having an accumulator would be helpful! How do you would
modify the current implementation - even with pseudo-code?
TIA, all the best,
-Simo

[1] https://svn.apache.org/repos/asf/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/



On Mon, Dec 12, 2011 at 6:27 PM, James Carman
<james@carmanconsulting.com> wrote:
> 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
>>
>>

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


Mime
View raw message