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
