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 Tue, 13 Dec 2011 17:35:40 GMT
Hey Simone,

On 12/12/2011 18:35, Simone Tripodi wrote:
> 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?

trying to put it all together (thanks James, Matthew):

  * Weighted<W> is fully generic without restrictions on the type of
    weight W
  * different properties of weights are specified with interfaces: e.g.
    Summable, HasZero, Comparable...
  * each algorithm requires the weights to implement one or more of the
    above interfaces based on needs, and only works with related methods
    abstracting from the actual type of weight. For example sum(W
    weight) for Summable.

Now, IFF you like that... what shall we do with Double, Integer, etc?

Claudio


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

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