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" <simonetrip...@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 > <ja...@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" <squar...@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 > >>> <ja...@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<squar...@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: squar...@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-unsubscr...@commons.apache.org> > >>>>> For additional commands, e-mail: dev-h...@commons.apache.org > >>>>> > >>>>> ------------------------------**------------------------------** > >>> --------- > >>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org< > dev-unsubscr...@commons.apache.org> > >>> For additional commands, e-mail: dev-h...@commons.apache.org > >>> > >>> > >> -- > >> Claudio Squarcella > >> PhD student at Roma Tre University > >> E-mail address: squar...@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-unsubscr...@commons.apache.org> > >> For additional commands, e-mail: dev-h...@commons.apache.org > >> > >> > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > >
