Hi, I have tended to find that edge weights always follow the following laws:
They have a monoid: There is a zero (0) constant and a |+| operator for combining two weights. They have an equivalence and (compatible) ordering relations (>, =): The ordering is compatible with the monoid. For example, a |+| 0 = 0 a |+| b >= a a |+| b = b |+| a a >= 0 a != 0, b != 0 => a |+| b > a Taken together, the algorithms for things like shortest-path or weighted-k-neighbourhood can all be expressed, abstracted away from the weight datatype, the operations for combining weights, and the operations for comparing weights. If you choose your ordering then you can derive the compatible min monoid where a |+| b = min(a, b). If you use the natural ordering on numbers then you commonly use the monoids (0, +) or (1, *). However, I've had cases where the individual weights and accumulated path-traversal weights are complex structures. This isn't a problem, as long as there's a zero and |+| for these 'weight' structures, and a well-behaved ordering over these structures. On 12 December 2011 04:39, James Carman <ja...@carmanconsulting.com> 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. > > 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" <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 (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 > >> > >> > >> --------------------------------------------------------------------- > >> 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 > > -- Dr Matthew Pocock Integrative Bioinformatics Group, School of Computing Science, Newcastle University mailto: turingatemyhams...@gmail.com gchat: turingatemyhams...@gmail.com msn: matthew_poc...@yahoo.co.uk irc.freenode.net: drdozer skype: matthew.pocock tel: (0191) 2566550 mob: +447535664143
