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
<turingatemyhamster@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 shortestpath or
> weightedkneighbourhood 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
> pathtraversal weights are complex structures. This isn't a problem, as
> long as there's a zero and + for these 'weight' structures, and a
> wellbehaved ordering over these structures.
>
> On 12 December 2011 04:39, James Carman <james@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
>> <james@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>
>> > 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,
>> >> nonnegative 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 highlevel 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
>> >> Email address: squarcel@dia.uniroma3.it
>> >> Phone: +390657333215
>> >> Fax: +390657333612
>> >> http://www.dia.uniroma3.it/~squarcel
>> >>
>> >>
>> >> 
>> >> To unsubscribe, email: devunsubscribe@commons.apache.org
>> >> For additional commands, email: devhelp@commons.apache.org
>> >>
>> >
>>
>> 
>> To unsubscribe, email: devunsubscribe@commons.apache.org
>> For additional commands, email: devhelp@commons.apache.org
>>
>>
>
>
> 
> Dr Matthew Pocock
> Integrative Bioinformatics Group, School of Computing Science, Newcastle
> University
> mailto: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@yahoo.co.uk
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143

To unsubscribe, email: devunsubscribe@commons.apache.org
For additional commands, email: devhelp@commons.apache.org
