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 <squar...@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 >> <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 >> > > -- > 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 > > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: 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
