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 22:07:49 GMT
Well if you wanna get all mathematical about it, what you're actually
talking about is in addition operation.  In functor-speak it would be a
binary function.
On Dec 12, 2011 12:35 PM, "Simone Tripodi" <simonetripodi@apache.org> 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?
> 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
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message