Terrific feedback Matthew, thanks a lot! and glad to see researchers here :) best, -Simo
http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Mon, Dec 12, 2011 at 3:27 PM, Matthew Pocock <turingatemyhams...@gmail.com> wrote: > 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 --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
