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" <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 > >
