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 Wed, 14 Dec 2011 11:34:44 GMT
I don't like the idea of pushing the adding, comparing, etc. into the
weights.  I like the idea of having operations external to the weights
that take care of that stuff.

On Tue, Dec 13, 2011 at 12:35 PM, Claudio Squarcella
<squarcel@dia.uniroma3.it> wrote:
> 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
>

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


Mime
View raw message